淘宝笔试的一道题

时间：2011-03-27 来源：绿豆芽33

今天淘宝海笔时碰到的一道题。题目大概是这样叙述的：n个鸡蛋放到m个篮子，每个篮子不能空，要求满足：给定任意一个小于n的数量，几个篮子的鸡蛋数加起来就可以等于它。要求输入n和m，求出满足要求的所有可行的鸡蛋放法。

偶是个小菜鸟，想了10多分钟，效率不怎么高，貌似还算可行，回来后写了下程序。偶的思路大体是这样的。先将问题转换一下描述，就是给定两个正整数n和m，对于任一个小于n的正整数x都可以表示成这m个数的部分和，求出满足这个要求的m个数有多少种。
经过我的分析发现，这m个数的最大值不超过n/2(上取整)，而且除了最后两个数不是1之外其他的m-2个数均是1，可是我当时不会证明这个想法对不对。就采用了这样的思路：用一个不平衡二叉树表示这个过程，二叉树的每个中间节点表示其子树的和，叶子节点表示m个数之一。其中二叉树的左子树为叶子节点，右子树每次扩展成两个节点，根据m值可以确定到底要扩展多少次，扩展过程中，用一个数组记录已经生成的叶子节点，当满足m个叶子节点时，数组中的元素是1，1,1,...，1，n-m+1。调整最后两个元素分别为n/2-m+1,n/2+1，这样做只是为了减少后面循环的次数。剩下的任务就是判断从最后两个元素的父节点开始每个小于等于它的元素是否可以由数组中的某些元素之和来表示，为什么只需从最后两个元素的父节点开始判断呢，因为前面每次扩展时生成的两个节点和都等于其父节点，所以前面的就不用判断了。如果有某个值不能用数组中的元素表示，那么将最后两个元素重新调整，倒数第二个加一，倒数第一个减一。如果都能用数组中的元素表示，那么输出满足要求的这m个数，将最后两个元素重新调整继续判断。不知道我的思路怎么样，粗略地写了一个小程序。

图中n=10，m=4

欢迎大牛们提出更好的算法！！！

#include<iostream>
#include<cassert>
using namespace std;

int isCompose(int x,int *a,int nc)
{
 int i,sum=0;
 for(i=nc;i>=0;i--)
 {  if(x<a[i])continue;
    else if(x==a[i])return 1;
    else{
        break;
        }
 }
 assert(i>=0);
 while(sum<x&&i>=0)
 {
   sum+=a[i];
   if(sum==x)return 1;
   if(sum>x)sum-=a[i];
   i--;
 }
 return 0;
}
void print(int *a,int nc)
{
 for(int i=0;i<nc;i++)
  cout<<*(a+i)<<"\t";
 cout<<endl;
}
void func(int n,int m)
{
 assert(n>=m);
 int *ret=new int[m];
 int i=2,x=n;
 int count=0;
 ret[count++]=1;
 ret[count]=--x;
 while(i<m)
 {
        i-=1;
        ret[count++]=1;//replace last num
        ret[count]=--x;
        i+=2;   
 }
 if(i==m)
 {
        if(m==n){print(ret,m);return;}
        x++;
        ret[count-1]=x-1-n/2;
        ret[count]=n/2+1;       //最大为n/2
start:  
        for(int j=x-1;j>0;j--){
          if(!isCompose(j,ret,count))
          {
                ret[count-1]++;
                ret[count]--;
                if(ret[count]<ret[count-1]||ret[count]<=1)return; 
                goto start;
          }
        }//for
        print(ret,m);
        ret[count-1]++;
        ret[count]--;
        if(ret[count]<ret[count-1]||ret[count]<=1)return;
        goto start;     
 }
}


int main()
{
        int n,m;
        cin>>n;
        cin>>m;
        func(n,m);
        return 0;
}