学步园

64、淘宝校园笔试题
goengine
N 个鸡蛋放到 M 个篮子中，篮子不能为空，要满足：对任意不大于 N 的数量，能用若干个
篮子中鸡蛋的和表示。
写出函数，对输入整数 N 和 M，输出所有可能的鸡蛋的放法。
比如对于 9 个鸡蛋 5 个篮子
解至少有三组：
1 2 4 1 1
1 2 2 2 2
1 2 3 2 1

/*
64、淘宝校园笔试题
goengine
N 个鸡蛋放到 M 个篮子中，篮子不能为空，要满足：对任意不大于 N 的数量，能用若干个
篮子中鸡蛋的和表示。
写出函数，对输入整数 N 和 M，输出所有可能的鸡蛋的放法。
比如对于 9 个鸡蛋 5 个篮子
解至少有三组：
1 2 4 1 1
1 2 2 2 2
1 2 3 2 1

1、(n,m,min)表示当前状态，按照篮子里蛋的数目从小到大搜索。
搜到了第m个篮子，1..m 个篮子面共放了n个蛋，当前的篮子放了min个蛋。
下一个扩展(n+t,m+1,t),for t=min...n+1。

2、当n+(M-m)*min>N (鸡蛋不够时)或者 2^(M-m)*n+2^(M-m)-1<N （鸡蛋太多）时把这个枝剪掉…… 
n+(M-m)*min>N (鸡蛋不够时)：
   因为按从小到大搜索 当前min个，后面至少min个,前面m个框总和n个，所以总和至少n+(M-m)*min>N时，鸡蛋不够 
2^(M-m)*n+2^(M-m)-1<N （鸡蛋太多）： 
  假如当前所有篮子放的鸡蛋总合为n,则下一个篮子最多可以放n+1（因为假设前面可以表示1--n，若放n+2，无法表示n+1）
  下下个篮子2n+2（n,n+1可以表示2n+1，无法表示2n+2）,在下下个篮子4n+4,8n+8....
如此类推，如果鸡蛋总和比这些个数相加还大，则表示鸡蛋太多了 ； 
3、太多时的情况如下：n,n+1,2n+2,4n+4,8n+8....。=n,n+1,2*(n+1),4*(n+1)...
最多情况为：1，2，4，8，16。。。。。（1+2+4+..）=2^n-1 
	求和，2^(M-m)*（n+1)-1: 表示前面n个，后面最多起始：n+1个，累增和 
*/
#include <iostream> 
using namespace std; 
long pow2[20]; 
int N,M; 
int ans[1000]; 
void solve( int n,int m,int Min ) //第m个篮子放min个 前m共放了n个 
{ 
	if(n==N&&m==M) 
	{ 
		for(int i=1;i<=M;i++) 
			cout<<ans[i]<<" "; 
		cout<<endl; 
		return ; 
	} 
	else if(n+(M-m)*Min>N||N>pow2[M-m]*n+pow2[M-m]-1) 
		return ; 
	else
	{ 
		for(int i=Min;i<=n+1;i++) 
		{ 
			ans[m+1]=i; 
			solve(n+i,m+1,i); //前面m+1个篮子共放n+i个 
		}
	} 
}
int main() 
{ 
	pow2[0]=1; 
	for(int i=1;i<20;i++)  //计算2^i次 
		pow2[i]=pow2[i-1]<<1; 
	cin>>N>>M; 
	if(M>N||pow2[M]-1<N)  
		cout<<"没有这样的组合"<<endl;
	solve(0,0,1); 
	return 0; 
} 

参考转自：http://blog.csdn.net/qq675927952/article/details/6290131