《算法竞赛入门经典》计算组合数问题

计算组合数

编写函数，参数是两个非负整数n和m，返回组合数 其中m<=n<=25。例如，n=25,m=12时的答案为5200300。

代码及算法分析

程序4-1 组合数（有问题）

#include  long long factorial(int n) { long long m=1; //不要忘记初始化，不然的出来的结果惊人。 for(int i=1;i<=n;i++) { m*=i; } return m; } int main () { int n,m; scanf("%d %d",&n,&m); printf("%lld",factorial(n)/(factorial(m)*factorial(n-m))); return 0; } 

这个代码的问题显而易见，阶乘容易溢出，所以不可取。 所以，套用刘汝佳老师的一句话：”即使最终答案在所选择的数据类型范围之内，计算的中间结果仍然可能溢出“。

汝佳老师也给出了相应的解决方案，虽然不能完全避免中间结果溢出，但是对于题目给出的范围已经可以保证得到正确的结果了。 先来分析一下组合数的公式： n! ———— m!(n-m)! 展开之后： n *(n-1) *(n-2)……3 *2 *1 —————————————————————————————（1） m *(m-1) *(m-2)……3 *2 *1 *(n-m) *(n-m-1) *(n-m-2)…… *3 *2 *1 因为n>=m，所以m在1~n之间，这样可以把n!除以m!约分： n *(n-1) *(n-2)……(m+2) *(m+1) ————————————————（2） (n-m) *(n-m-1) *(n-m-2)…… *3 *2 *1

然后汝佳老师给了一道思考题：为什么当m