java - 如何找到n选择r而不溢出

Question

我需要找到n Choose r的值——从n中选择r个对象的方法数。

如果我先找到分子，然后找到分母。我遇到了异常。

我正在使用java。

如何做到这一点，例如 44 选择 42

Answer 1

您可以使用 NcR 等于 Nc(N-R) 的事实。公式为:

 N * (N - 1) * ... * (N - R + 1)
---------------------------------
         1 * 2 * ... * R

您可以观察到 K 个连续数字的乘积始终可以被 K 整除。所以，循环看起来像

• 将提名者的两个数字相乘
• 除以 2
• 乘以提名人的第三个数字
• 除以 3
• ...
• 乘以提名者的最后一个数字
• 除以R

或者，只需使用java.math.BigInteger。