计算二项式系数的算法
我需要一种计算组合的方法，而不会耗尽内存。 这是我到目前为止所拥有的。
public static long combination(long n, long k) // nCk { return (divideFactorials(factorial(n), ((factorial(k) * factorial((n - k)))))); } public static long factorial(long n) { long result; if (n <= 1) return 1; result = factorial(n - 1) * n; return result; } public static long divideFactorials(long numerator, long denominator) { return factorial(Math.Abs((numerator - denominator))); } 我已将其标记为C＃，但理想情况下，解决方案应与语言无关。
public static long combination(long n, long k) { double sum=0; for(long i=0;i
我所看到的计算二项式系数的最好方法之一是Mark Dominus 。 与其他方法相比，N和K的值越大，溢出的可能性就越小。
public static long GetBinCoeff(long N, long K) { // This function gets the total number of unique combinations based upon N and K. // N is the total number of items. // K is the size of the group. // Total number of unique combinations = N! / ( K! (N - K)! ). // This function is less efficient, but is more likely to not overflow when N and K are large. // Taken from: http://blog.plover.com/math/choose.html // long r = 1; long d; if (K > N) return 0; for (d = 1; d <= K; d++) { r *= N--; r /= d; } return r; }
这是一个与Bob Byran非常相似的解决方案，但是检查了另外两个前提条件来加速代码。
/// /// Calculates the binomial coefficient (nCk) (N items, choose k) /// /// the number items /// the number to choose /// the binomial coefficient public static long BinomCoefficient(long n, long k) { if (k > n) { return 0; } if (n == k) { return 1; } // only one way to chose when n == k if (k > n - k) { k = n - k; } // Everything is symmetric around nk, so it is quicker to iterate over a smaller k than a larger one. long c = 1; for (long i = 1; i <= k; i++) { c *= n--; c /= i; } return c; }
看看你的代码，难怪你会很快耗尽内存。 您的方法divideFactorials调用方法factorial并使用差异“ divideFactorials -denominator”作为参数。 根据你的代码，这种差异很可能非常大，你将在你的阶乘方法中陷入很长的循环。
如果它真的只是找到nCk（我假设因为你的代码中的注释），只需使用：
public static long GetnCk(long n, long k) { long bufferNum = 1; long bufferDenom = 1; for(long i = n; i > Math.Abs(nk); i--) { bufferNum *= i; } for(long i = k; i => 1; i--) { bufferDenom *= i; } return (long)(bufferNom/bufferDenom); }
当然使用这种方法你会超出范围非常快，因为long实际上不支持很长的数字，所以n和k必须小于20。
假设你实际上使用非常大的数字，你可以使用双倍而不是长，因为权力变得越来越重要。
编辑：如果你使用大数字你也可以使用斯特林的公式：
随着n变大ln（n！） – > n * ln（n） – n。
把它放到代码中：
public static double GetnCk(long n, long k) { double buffern = n*Math.Log(n) - n; double bufferk = k*Math.Log(k) - k; double bufferkn = Math.Abs(nk)*Math.Log(Math.Abs(nk)) - Math.Abs(nk); return Math.Exp(buffern)/(Math.Exp(bufferk)*Math.Exp(bufferkn)); }
我只提出这个答案，正如你所说的独立语言，C＃代码只是用来演示它。 由于你需要使用n和k的大数来实现这一点，我建议将其作为查找大组合的二项式系数的一般方法。
对于n和k都小于200-300的情况，你应该使用Victor Mukherjee提出的答案，因为它确切。
Edit2：编辑了我的第一个代码。
仅仅为了完成：标准C数学库具有Γ和lnΓ（称为tgamma和lgamma ）的实现，其中
Γ（n）=（n-1）！
库计算肯定比求和对数更快，更准确。 有关更多信息，请参阅Wikipedia和Mathworld 。