计算二项式系数的算法
我需要一种计算组合的方法,而不会耗尽内存。 这是我到目前为止所拥有的。
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: https://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 。
上述就是C#学习教程:计算二项式系数的算法分享的全部内容,如果对大家有所用处且需要了解更多关于C#学习教程,希望大家多多关注---计算机技术网(www.ctvol.com)!
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/cdevelopment/1011090.html