二项式定理 用pascal怎么算?

问题描述:

二项式定理 用pascal怎么算?
rt,我要算杨辉三角中第n每个数的个位数,但是递归去算杨辉三角会超时(要算到100000层左右),所以我想用二项式定理直接代,可是c(m,n)=n!/m!(n-m)!算阶乘会越界,我现在实在是无语了,
例如:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 0 0 5 1
1 6 5 0 5 6 1
(只算个位数,我现在的方法是把确切得数算出来在mod 10)
1个回答 分类:综合 2014-12-13

问题解答:

我来补答
不要用阶乘,直接算
c(m,n)=n*(n-1)*……*(n-m)/m*(m-1)*……*1
程序计算的时候为了避免乘积会越界,必须采取一些措施
如下:
c(m,n)=a/b
a=n*(n-1)*……*(n-m)
b=m*(m-1)*……*1
在得到累乘的积a和b的过程中判断a能否被b中的项整除,如果能得话就将它们除掉,在用手计算的时候就叫做约分.这样做的代价是牺牲时间.
还有一种是牺牲空间为代价
那就是记录下C(1,1)~C(m,n)
先算得C(i,j),记录下他的值,然后计算C(i+1,j),和C(i,j+1)然后记录下来,一直计算到C(m,n)最后需要那一个就取计算出来的值.
程序就不写了,自己按照这个思路就能够做出来
 
 
展开全文阅读
剩余:2000
下一页:生物 酶