Question

C语言中的排列组合问题；

m个黑球，n个白球，排成一行，有多少种排法；
可以使用以下代码来求解；

int f(int m,int n)
{
if(m==0||n==0) return 1;

return f(m-1,n)+f(m,n-1）；

}

怎么理解这个函数？

请给出详细的解释，非常感谢！

Answer 1

f(m, n)表示m个黑球n个白球的排法，那好。
假如这个问题给你了，你会这样想：
1、我先把第一位放黑球，那么后面的排法有多少种：当然是f(m - 1, n)种，因为少了一个黑球。
2、同理，我先放白球，那么有f(m, n - 1)种。
总共就有f(m-1,n)+f(m,n-1）种，后面就递归了。但不能无限递归，需要指定界限，然后就有if(m==0||n==0) return 1;
这个和数学归纳法很相似。

Answer 2

f(m-1,n)就是先放一个黑球的排列数，f(m,n-1）就是先放一个白球的排列数，后面就是如此类推，就很简单了，最后先放完某一种球后面就只能连续放另外一种球所以有 if(m==0||n==0) return 1;

很简单吧，楼上都是坑爹的

Answer 3

这个函数就相当于是把（m+n）*(m-1+n)*(m-1+n-1)*(m-1-1+n-1)*......知道m，n的值均为0
应该是排序的公式吧

Answer 4

这是一个递归函数，f(0,n)=1,f(m,0)=1，你可以简单地代入几个值试试, 如m=1,n=1,f（1,1）=f(0,1)+f(1,0)=2; m=2,n=2，f（2,2）=f(1,2)+f(2,1)=f(0,2)+f(2,0)+2*f(1,1)=2+4=6。m个黑球，n个白球，排成一行，有（m+n）!/ (m!*n!) 种排法。详细了解递归函数请参考《C语言程序设计》谭浩强

追问

我是带入数字算过的，计算机算的结果和我笔算的结果一样。我主要不理解是：f(m-1,n)+f(m,n-1)的意思，为什么可以这样差分？

我也知道是递归调用，另外，我学C语言就是用的谭浩强的书。

感谢你的回答。

追答

这是一种数学算法的问题，当你把这种排列真正理解了就会明白了，你可以自己推导一下加深理解记忆。过程推导过于繁琐，在此不便展现，请谅解。请参阅其他相关书籍。

Answer 5

这是个递归算法，分析如下：
（1）if(m==0||n==0) ;
当m或者n为0时，显然，只能有一种排列方法，故return 1
（2）当m>0 与n>0时，m个黑球的排列方法，等于m-1，n 的排列方法加m , n-1的排列方法，数学理解到位即可。