题目名称
eggs
题目描述
Erin买了不少鸡蛋，她发现一天吃不完这么多，于是决定把n个同样的鸡蛋放在m个同样的篮子里，允许有的篮子空着不放，请问共有多少种不同的放法呢？
注意：2，1，1和1，2，1 是同一种分法。
第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数m和n，以空格分开。1<=m，n<=10。
对输入的每组数据m和n，用一行输出相应的结果。
例如：
Input:
4
3 8
4 7
2 4
4 2
Output:
10
11
3
2
(注意结尾有换行)
HINT
尝试利用递归去分析解题，即不同情况下应该怎么返回。
可以尝试用树状图（然而我觉得用处不大）。
注意篮子可以空着不放，请先想明白示例中最后两个例子再做题。
题目难度
1
我的思路
（摘录自另一个同学）因为数据比较小，可以用回溯的方法生成【不严格上升的、和为n的m个数的数列】的个数，就是答案。（因为篮子都是一样的，那么按篮子里的鸡蛋个数从小到大排序后得到的序列只要是一样的，就是相同的情况，比如1 2 1与2 1 1，排序后都是1 1 2，那么就是两个一样的方案。）
所以每一次从小开始产生后面的篮子必须装比前面篮子多或者相等的鸡蛋，很显然这样的话就不会产生重复的情况，然后产生到了m次，鸡蛋总和为n，那么就出一种方案数。
方法&解释
利用递归调用每一层相当于一个篮子，然后在里面有循环——鸡蛋个数从上一层鸡蛋个数到总数减去目前放下的鸡蛋个数，这样保证了不严格上升序列，最后到达m时目前放下的鸡蛋个数==n则出一种方案数。
我的代码
1 #include<stdio.h> 2 int num = 0;//老师说最好不要用全局变量==以后会改进，把这个用函数返回值来代替 3 void egg(int m, int n, int pos, int tot) {//pos：the number of eggs in the current basket；tot：the total number of eggs now 4 int i = 0; 5 if (m == 0) {//这个判断可以看最后一步，最后我们m==1的时候我们还要往下面去分配那一个篮子，所以不是m==1而是m==0 6 if (tot == n) { 7 num++;//如果m==0并且tot==n那么才方案数加一，因为m==0,tot不一定等于n，这个递归是将所有的可以取1-n的不严格递增序列全部列举了 8 return; 9 } else { 10 return; 11 } 12 } 13 for (i = pos; i <= n - tot; i++) { 14 egg(m - 1, n, i, tot + i);//剩下m-1了篮子；n total number；i the current...；tot + i the total now... 15 } 16 } 17 int main() { 18 int t, i, m, n; 19 scanf("%d", &t); 20 for (i = 1; i <= t; i++) { 21 num = 0;//每一次都需要初始化 22 scanf("%d%d", &m, &n); 23 egg(m, n, 0, 0);//m baskets and n eggs the first zero就是当前的篮子是第几个，后面一个零是当前装下了多少个鸡蛋总共 24 printf("%d ", num); 25 } 26 }
标程代码
1 #include<stdio.h> 2 int egg(int m, int n); 3 4 int main() { 5 int t; 6 // m for baskets, n for eggs 7 int m, n; 8 int result = 0; 9 scanf("%d", &t); 10 while (t--) { 11 scanf("%d %d", &m, &n); 12 result = egg(m , n); 13 printf("%d ", result); 14 } 15 return 0; 16 } 17 18 int egg(int m, int n) { 19 if (m == 1 || n == 0) 20 return 1; 21 if (n < 0) 22 return 0; 23 return egg(m-1, n) + egg(m, n-m); 24 }
标程解释
要么往现在所有的篮子里全放个鸡蛋，要么舍弃掉一个篮子不再往里面放鸡蛋，这样也类似保证了比前面的多或者相等（摘录自TA）；
即要么往所有目前还没有遍历到的篮子里面装一个鸡蛋，然后继续往装当前这一个篮子走，要么这个篮子不装，往下一个篮子走；这样的话，要么后面的篮子与前面的篮子里面鸡蛋数量相等，要么后面的篮子比前面的篮子的鸡蛋数要多，因为每一次往所有剩下的篮子里面装鸡蛋，所有的都顾及到了，所以这样所有的都是相等，其实改变不同篮子的鸡蛋个数就只有这个篮子里面不装，而后面一个篮子要么比前面一个多要么相等；当m==1时则把剩下的鸡蛋全部放到最后一个篮子里面，这样的话也保证了最后面一个篮子要么比前面的多要么相等，因为最后面一个篮子在前面所有的所有篮子都加一个鸡蛋的操作中也被操作了，方案数加一；当n==0时，鸡蛋被放完了，方案数也加一，这个方案也保证了不严格单调上升序列；其实这是另一种构造不严格单调递增序列的方法，也可行，它每一次都是一层一层的加一；
我觉得可以类似于这样的阶梯型上升第一步全部装，然后一不装，二全部装，二不装...，然后m==1装剩下所有的，这样形成了不严格单调递增，因为每一层都可以一次不加或者加很多次，所以所有的不严格单调递增序列均被遍历到了，不会有遗漏。
问题
①C语言函数返回值还不太会利用，以及各种返回形式，要加强使用，避免使用全局变量；
②思路最重要...本题思路也比较巧妙，转化为不严格单调序列，以后要多发现；
③思路不够严谨，交了两次，忽略了tot==n才方案数加一。
需要学习的地方
①把函数返回值，函数相关的问题弄清楚，总结出一篇随笔；
②将全局变量局部变量这些看一下，总结；
③将全局变量用函数返回值替换；
④多练题。