Sicily1006. 递归：放鸡蛋

Description

把M个同样的鸡蛋放在N个同样的篮子里，允许有的篮子空着不放，问共有多少种不同的放法？（用K表示）5，1，1和1，5，1是同一种分法。

输入：鸡蛋M，篮子N

输出：鸡蛋的放法（降序，不重复）

Sampleinput：

1

73

Sampleoutput：

700

610

520

511

430

421

331

322

解题思路：

（参考sicily1004整数划分：m表示鸡蛋,n表示篮子数(最深输出栈），depth表示当前放鸡蛋的篮子位置（递归的深度），num数组储存依次放鸡蛋结果.初始化：cin>> m >> n; num为空;depth = 0.~\(≧▽≦)/~啦啦啦，反正这里栈就是篮子，篮子就是栈)

1. m == 0 时，表示没有鸡蛋可以放，此时输出存储结果，跳回上一个栈。

·若此时栈的深度等于篮子数，则正常输出；

·若此时栈的深度大于篮子数，不合题意不输出；

·若此时站的深度小于篮子数，多余的篮子放0个鸡蛋。

2. m > 0 时，首先，第一个篮子可以放i个鸡蛋（其中降序要求i从m到1）

·当处在第0层栈时可直接放i个鸡蛋，num[depth]= i；

·若当前药房的i个鸡蛋小于等于上一层栈的数，则

这一层栈存放i个鸡蛋num[depth]= i;

·若当前i大于上一栈（篮子）则跳过不存（因为要满足降序，

且避免重复）

然后，剩下的m-i个鸡蛋继续向下调用栈继续存放直到鸡蛋放完。

图解：

num:

i(1)

……depth=0……

↓放n-i(1)鸡蛋↑(i(1)--)→……

i(1)

i(2)

……depth=1……

↓放n-i(1)-i(2)↑（i(2)--)→……

i(1)

i(2)

i(3)

……depth=3……

↓放0个鸡蛋↑（i(3)--)→……

i(1)

i(2)

……depth=m……

→符合格式就输出否则跳过，返回上一栈↑（i(m)--）

参考代码：

#include<iostream>usingnamespacestd;voiddisplay(int*num,intn,intdepth){inti;if(depth<=n){for(i=0;i<depth;i++)cout<<num[i];for(;i<n;i++)cout<<0;cout<<endl;}}voidfun(intm,intdepth,intn,int*num){if(m==0){display(num,n,depth);}else{for(inti=m;i>=1;i--){if(depth==0||i<=num[depth-1]){num[depth]=i;fun(m-i,depth+1,n,num);}}}}intmain(){intt,M,N,num[50]={0};cin>>t;for(;t>0;t--){cin>>M>>N;fun(M,0,N,num);}}

【递归】 放鸡蛋