放鸡蛋问题：相同元素分配到相同的空间

标签： C语言 放鸡蛋 相同元素 相同空间

by 小威威

1.引入

放鸡蛋问题就是指将相同元素分配到相同空间这一类问题。具体问题就是：现在有n个相同的鸡蛋，m个相同的篮子，将这n个鸡蛋分配到篮子中，且篮子可以为空，问一共有多少种分配方法？

我们的第一反应就是排列组合，而这一问题很类似于我们高中的隔板法。然而，如果你沿着这条思路，恐怕你就会走近进胡同却又浑然不知。

因为隔板法是针对相同元素分配到不同空间而设计的，注意，是不同空间。倘若篮子是不同的，那么就可以用隔板法来解决这一问题。而如今是相同篮子。也许你会说可以将结果除以某个组合数，但我是试过了，行不通，如果你能做到，欢迎在下面评论，或者私我，不胜感激。

但是，隔板法行不通并不意味着这道题和排列组合毫无关联，因为解这道题还是需要排列组合中的分类思想。

2.问题分析

现在有n个相同的鸡蛋，m个相同的篮子，将这n个鸡蛋分配到篮子中，且篮子可以为空，问一共有多少种分配方法？

拿到这道题，我们首先要进行第一次分类，也就是篮子数与鸡蛋数的大小关系。当鸡蛋数小于篮子数时，无论怎么放，都会有空篮子，并且篮子是相同的，不妨就将这几个篮子删去，即让篮子数等于鸡蛋数。此时，就能将鸡蛋数小于篮子数这一情况归于下面一种情况。当鸡蛋数大于等于篮子数时，此时要进行第二次分类：因为篮子可以为空，所以分为没有空篮子，一个空篮子，两个空篮子….最多可以有m-1个篮子。如此分类保证了除了空篮子以外，其他篮子至少要有一个鸡蛋，这样问题就容易分析多了。我们设F(m, n)为将n个鸡蛋分配到m个篮子，篮子可以为空，设T(m, n)为将n个鸡蛋分配到m个篮子，篮子不可以为空。则F(m, n)＝T(m, n)+T(m,n-1)+T(m,n-2)＋….＋T(m, 1)。显然，要解出这一式子要用递归的思想。但对于这个式子，我们还需要变一下形，使F与T的联系更紧密。

对于1+2+3+…+10，用递归的思想就可以变成1+54=1+2+52=1+2+3+49=…=1+2+3+….+10
那么对于F(m, n)＝T(m, n)+T(m,n-1)+T(m,n-2)＋….＋T(m, 1)，用递归的思想就可以变成：
F(m,n) = T(m,n) + F(m,n-1)
对于T(m, n)，指将n个鸡蛋放到m个篮子，且每个篮子都不为空。即每个篮子至少有一个。所以我们先给每个篮子分一个鸡蛋，剩下n-m个鸡蛋可以任意分配，即以一开始可以为空篮子的规则分配(此时可以将每个篮子里的那个鸡蛋忽略)。那么T(m, n)就变成了F(m, n-m).则F(m, n) = F(m, n-m) + F(m, n-1)。如此，递归原型出现了。如今，我们要设计递归中止的条件。(注意，在递归的过程中，如果出现鸡蛋数少于篮子数，就让篮子数等于鸡蛋数，然后再进行下一步操作。)当篮子数为1时，显然只有一种情况，所以返回1；还有一种情况返回1就是当篮子数为0。如F(2,2)=F(0,2) + F(1,2)。因为当鸡蛋数为0，篮子数不为0时，篮子数会被赋值为鸡蛋数，即为0，由于判断条件，F(0,2)会被忽略，而F(0,2)的原型是T(2,2)，也是属于一种情况，所以要补上。当鸡蛋数为0时，显然不能分配，即0种情况，所以返回0。如此，递归就设计完成了～

此题的关键之一就是将空篮子的个数进行分类，其二就是确定所有篮子都不是空篮子时，先给每个篮子分配一个鸡蛋，剩余的鸡蛋按照原来的规则分配。

3.实例

Erin买了不少鸡蛋，她发现一天吃不完这么多，于是决定把n个同样的鸡蛋放在m个同样的篮子里，允许有的篮子空着不放，请问共有多少种不同的放法呢？

注意：2，1，1和1，2，1 是同一种分法。

Input
第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数m和n，以空格分开。1<=m，n<=10。

Output
对输入的每组数据m和n，用一行输出相应的结果。

例如：

Input:

4

3 8

4 7

2 4

4 2

Output:

10

11

3

2

(注意结尾有换行)

代码：

# include <stdio.h>
int Calculate_ways(int egg_number, int backet);
int main(void) {int T, i, number;scanf("%d", &T);i = 0;while (i < T) {int x1, x2;scanf("%d%d", &x1, &x2);number = Calculate_ways(x2, x1);printf("%d\n", number);i++;}
}
int Calculate_ways(int egg_number, int backet) {if (egg_number < backet) backet = egg_number;if (backet == 1 || backet == 0) return 1;if (egg_number == 0) return 0;return Calculate_ways(egg_number-backet, backet)+ Calculate_ways(egg_number, backet-1);
}

以上内容皆为本人观点，欢迎大家提出批评和指导，我们一起探讨。