大数量级组合数的快速计算方法
转自:大数量级组合数的快速计算方法,保存在此以学习。 计算组合数最大的困难在于数据的溢出,对于大于150的整数n求阶乘很容易超出double类型的范围,那么当C(n,m)中的n=200时,直接用组合公式计算基本就无望了。另外一个难点就是效率。 ? ? 为了避免直接计算n的阶乘,对公式两边取对数,于是得到: ? 进一步化简得到: ? 这样我们就把连乘转换为了连加,因为ln(n)总是很小的,所以上式很难出现数据溢出。 ? ? 这样,上式右边第一项就可以被抵消掉,于是得到: ? 上式直接减少了2m次对数计算及求和运算。但是这个公式还可以优化。对于上面公式里的求和,当m<n/2时,n-m是一个很大的数,但是当m>n/2时,n-m就会小很多。我们知道: 那么通过这个公式,我们可以把小于n/2的m变为大于n/2的n-m再进行计算,结果是一样的,但是却能减少计算量。 ? 这样就完成了组合数的计算。 ? ? 而计算时间只需要0.01ms。当然,如果要取对数得到最终的组合数的话,n的取值就不能达到这么大了。但是这种算法仍然可以保证n取到1000以上,而不是开头说的150这个极限值。例如: ? 计算时间仍然小于0.01ms。 ? ? double lnchoose(int n,int m) ? ? ? ? ? ? ? double choose(int n,255)">? ????} ????return exp(lnchoose(n,m)); } 【免责声明】本站内容转载自互联网,其相关言论仅代表作者个人观点绝非权威,不代表本站立场。如您发现内容存在版权问题,请提交相关链接至邮箱:bqsm@foxmail.com,我们将及时予以处理。 |