📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 3695| 回复: 13
跳转到指定楼层
上一主题 下一主题
收起左侧

Taobao : 分鸡蛋问题

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
N个鸡蛋分到M个篮子里(N>M),不能有空篮子,对于任意不大于于N的数,保证有几个篮子的鸡蛋数和等于此数,编程实现输入N,M两个数,输出所有分鸡蛋的方法

上一篇:face book : Divide a list of numbers into group of consecutive numbers
下一篇:Microsoft : 二叉树子结构
🔗
4T-Shirt 2011-5-9 21:42:50 | 只看该作者
全局:
N和M的规模有多大呢
回复

使用道具 举报

🔗
4T-Shirt 2011-5-9 22:30:19 | 只看该作者
全局:
/*
我用的方法可能还有地方可以剪枝,不知道n和m的范围多少,如果n>=1000的话,就不大行了
Problems:N个鸡蛋分到M个篮子里(N>M),不能有空篮子,对于任意不大于于N的数,
保证有几个篮子的鸡蛋数和等于此数,编程实现输入N,M两个数,输出所有分鸡蛋的方法

Solutions:搜索+剪枝
*/
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int maxm = 20;
int n,m;
int num[maxm]={1};

void search(int cnt,int curSum)
{
        if(cnt>=m)
        {
                if (curSum == n)
                {
                        for (int i=0;i<m;i++)
                        {
                                printf("%d%c",num[i],i==(m-1)?'\n':' ');
                        }
                }
        }
        else
        {
                int tmp = std::min(n-curSum,1<<cnt);
                tmp = std::min(tmp,curSum+1);
                for(int i=num[cnt-1];i<= tmp;i++)
                {
                        num[cnt] = i;
                        search(cnt+1,curSum+num[cnt]);
                }
        }
}
int main()
{
        scanf("%d %d",&n,&m);
        if( ((1<<m)-1) <n || n<=m)
        {
                cout << "There is no answer" << endl;
        }
        else
        {
                search(1,1);
        }
        return 0;
}
回复

使用道具 举报

🔗
darksteel 2011-5-10 01:12:20 | 只看该作者
全局:
这题如果不加上后面的限制条件并且要求输出方法的数目,就是典型的DP问题了。不过加上后面的条件之后难了不少,一时想不出太好的方法。ls的方法非常棒!,要输出所有结果的话,我觉得搜索是唯一可行的办法了
回复

使用道具 举报

🔗
darksteel 2011-5-10 02:34:18 | 只看该作者
全局:
回复 3# 4T-Shirt
想了半天觉得也没什么太多可优化的地方了,唯一能想到的就是在每次搜索的时候剪掉一些不必要的尝试:
  1.        int tmp = std::min(n-curSum,curSum+1);
  2.                 for(int i=num[cnt-1];i<= tmp;i++)
  3.                 {
  4.                         if((curSum+i+1)*(1<<(m-1-cnt))<n-curSum-i) continue;
  5.                         if((m-cnt)*i+curSum>n) break;
  6.                         num[cnt] = i;
  7.                         search(cnt+1,curSum+num[cnt]);
  8.                 }
复制代码

这题的复杂度基本上是指数的,我觉得当n >> m时,接近2^m,所以m稍大一点就要跑很久。测试了下,优化之后效率能提升几倍,但没有本质提升。对于大于30的m就要几十秒,再大估计就出不来了。这题作为面试题还挺难的,不太容易想到点子上。
回复

使用道具 举报

🔗
4T-Shirt 2011-5-10 08:56:40 | 只看该作者
全局:
回复 5# darksteel
那LS觉得我的思路可行吗
回复

使用道具 举报

🔗
4T-Shirt 2011-5-10 09:12:32 | 只看该作者
全局:
回复 5# darksteel

谢谢LS的优化了~非常好了
回复

使用道具 举报

🔗
4T-Shirt 2011-5-10 09:48:14 | 只看该作者
全局:
回复 6# 4T-Shirt

  1.                 int tmp = std::min(n-curSum,1<<cnt);
  2.                 tmp = std::min(tmp,curSum+1);
  3.                 for(int i=num[cnt-1];i<= tmp;i++)
  4.                 {
  5.                         //if((curSum+i+1)*(1<<(m-1-cnt)) < (n-curSum-i))        continue;
  6.                         if(((1<<m)-(1<<(cnt+1))) < (n-curSum-i)) continue;
  7.                         if((m-cnt)*i+curSum > n)        break;
  8.                         num[cnt] = i;
  9.                         search(cnt+1,curSum+num[cnt]);
  10.                 }
复制代码
我新做了一个优化,在判断 n=2^m -1 的情况下,能比你的优化快很多,如(1023,10)(2047,11),(4095,12)

   
回复

使用道具 举报

🔗
darksteel 2011-5-10 11:18:37 | 只看该作者
全局:
本帖最后由 darksteel 于 2011-5-10 11:30 编辑

回复 8# 4T-Shirt
开始的时候我百思不得其解,因为我原来的做法应该是判断了每次能做到的最大值,不会剪不掉那些情况的,后来一看原来是写法上出错了,应该改成这样:
if((curSum+i+1)*(1<<(m-1-cnt))<=n) continue;
或:
if((curSum+i+1)*((1<<(m-1-cnt))-1)<n-curSum-i) continue;
这样一来跟你的优化就完全是一回事了,测试证明了这一点。我估计是倒腾关系的时候弄错的,你的写法还是更好,只有移位而没有乘法。我想的是从当前情况出发,计算能达到的最大值,你似乎是直接从最大值判断,就是全都是2的指数的那个情况,前面每个数都是满的,相当于后面就是和最小的情况,考虑问题的角度很值得借鉴
回复

使用道具 举报

🔗
darksteel 2011-5-10 13:13:56 | 只看该作者
全局:
又写了个程序计算方法的数目,复杂度还是有点大,但至少是多项式了,为了简练几个搜索中的优化没有加:
  1. #include <iostream>
  2. #include <numeric>
  3. using namespace std;
  4. int dp[35][1024][1024];
  5. int main()
  6. {
  7.         int n, m;
  8.         cin >> n >> m;
  9.         int i, j, k, p;
  10.         dp[1][1][1] = 1;
  11.         for(i = 1; i <= m; i++)
  12.                 for(j = i; j < (1<<m) && j <= n; j++)
  13.                         for(k = (j+i-1)/i; k <= j-i+1; k++) {
  14.                                 if(!dp[i][j][k]) continue;
  15.                                 for(p = k; p <= n-j && p <= j+1; p++)
  16.                                         dp[i+1][j+p][p] += dp[i][j][k];
  17.                         }
  18.         int ans = accumulate(dp[m][n]+1, dp[m][n]+n+1, 0);
  19.         cout << ans << endl;
  20.         return 0;
  21. }
复制代码
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表