在解决一些数学问题时,我们可能会用到组合数的计算,本文介绍一种计算组合数的快速和安全的方法。
最基本的,组合数的数学计算公式为:
那么,最基础的思路即为分别计算出分子分母中的三个阶乘,进一步计算出组合数。这种思路的问题显而易见:阶乘的增长率太大。64 位无符号整数的最大值为 ,而 ,已经超过了前者,更不要说分母还要相乘了。
容易想到,我们可以参考人类手算组合式的模式来减少不必要的计算:
可以观察一下上面的结果。分子共有 项,分母也有 项,我们把上式改写成:
容易看出来,对于每一项,分子总是分母加 ,且分母的范围为 。
基于以上结论,我们容易写出代码:
function combination(m: number, n: number): number
{
let result = 1;
for (let i = 1; i <= m - n; i++)
{
result /= i;
result *= i + n;
}
return result;
}