一个较好的方法计算Choose(n,k)可以用下面的等价公式：
| Choose(n,k) = (n * (n-1) * (n-2) * ... * (n-k+1)) / ( 1 * 2 * ... * k) |
| Choose(7,3) = (7 * 6 * 5) / (1 * 2 * 3) |
这样就避免了直接计算n的阶乘，在运算中，你也可以先做一部分除法以减小运算量，例如Choose(7,3)，你可以先计算7*6，再除以2，得到24，然后*5在除以3，得到最终结果35。
第二个优化是利用下面的等价公式：
| Choose(n,k) = Choose(n, n-k). |
例如Choose(10,8)=Choose(10,2)。这个关系可能不容易想象，但是你可以自己举几个简单的例子计算，结果确实如此。计算Choose(10,8)需要计算7次乘法以及7次除法，而Choose(10,2)则只需1次乘法和1次除法。
把这些想法结合起来，我们便可以优化以前的Choose(n,k)方法，如图5。在Choose函数中，我判断了如果n等于k则直接返回1。这在之前的理论并没有提到，但是这可以有效提高程序的性能。
图5 优化的Choose方法：
| public static long Choose(long n, long k) { if (n < 0 || k < 0) throw new Exception("Invalid negative parameter in Choose()"); if (n < k) return 0; if (n == k) return 1; long delta, iMax; if (k < n-k) // ex: Choose(100,3) { delta = n-k; iMax = k; } else // ex: Choose(100,97) { delta = k; iMax = n-k; } long ans = delta + 1; for (long i = 2; i <= iMax; ++i) { checked { ans = (ans * (delta + i)) / i; } } return ans; } |
