现在的位置: 首页 > 综合 > 正文

如何求阶乘末尾0

2013年08月28日 ⁄ 综合 ⁄ 共 434字 ⁄ 字号 评论关闭
30元程序员衣装优惠券,仅剩3天!点击领取

   这是看同学博客总结的:

f(n!) = 0;

f(n!) = k + f(k!);  n >=5; k = n/5 (取下整)

原因:首先是对于10进制来所,0的个数取决于5的个数(因为10 = 2 *5,而且5的个数一定比2的个数要少)。

证明:令n = 5 * k + r(0 <= r <= 4)那么:n! = [5k * 5(k - 1) * ……*10 * 5]* a;

近似可以认为是:

1, 2, 3 ,4, 5,1,2,3, 4, 5, 1, 2, 3, 4, 5;

1                                   2                                3

如此即可完成递归运算。 

举例:

f(5!) = 1 + f(1! ) = 1;

f(10!) = 2 + f(2!) = 2;

f(20!)  = 4 + f(4!) = 4;

f(100!) = 20 + f(20!) = 20 + 4 + f(4!) = 24;

拓展:如果是求n阶乘是k的多少倍,那么可以先将k进行因式分解:

k = A^a * B^b * C^c……

然后求的n!中A质因子的个数_A, 同理求得B,C质因子个数_B,_C……

那么答案就是min(_A/a , _B/b, _C/c……);

30元程>序员衣装优惠券,仅剩3天!点击领取

抱歉!评论已关闭.