主题:十万火急,求助30分
ghbxx2004
[专家分:610] 发布于 2007-03-02 20:29:00
哪位大虾知道复杂度为lon2-n的二项式系数算法
回复列表 (共2个回复)
沙发
bpttc [专家分:8790] 发布于 2007-03-03 01:23:00
想了一下,纯属个人意见
先利用 C(m,n)=C(n-m,n)将m变成大于n/2的数
思路1.利用 C(m,n)=C(m,n-1)+C(m-1,n-1),是否可以转化成后序遍历二叉树?
思路2.C(m,n)= n!/[m!*(n-m)!]= n*(n-1)*...*(m+1)/[(n-m)*(n-m-1)*...*1]
= [n/(n-m)]*[(n-1)/(n-m-1)]*...*[(m+1)/1]
不过思路2好像不能整除,麻烦一些
板凳
euc [专家分:4310] 发布于 2007-03-03 18:11:00
这个快速阶乘法能不能用上:
http://maths.diy.myrice.com/florilegium/factorial.htm
我来回复