一个阶乘问题的简便算法
在网上看到一篇文章（http://www.blogjava.net/Jack2007/archive/2008/10/18/235152.html），发现其算法过于糟糕。我想到一个很简单的算法，但那个帖子无法回帖，故记于此处。
问题：求n的阶乘n!末尾有多少个零。据说这是微软的面试题。
分析：阶乘的增长速度极快，远远高于指数函数，例如5!=120，28!=304888344611713860501504000000。因此直接计算阶乘是不可能的。若以A表示所有2和5以外的因子之积，则n!=A*2a*5b。2出现的频率大于5出现的频率，故而可表示为n!=A*2a-b*2b*5b=A*2a-b10b，所以n!末尾的0的个数就是n!中因子5的个数。
算法:
public int ZeroNumber(int N)
{
int num=0;
for(int i=5;i<=N;i*=i)
num+=N/i;
return num;
}
事实上，可以有更快的算法。
转载请注明：来自奇幻旅程
本文地址：http://kingmq.appspot.com/201008factor.html
2 条评论
我要留言云在天边 发表于 2010-08-25 at 19:15 回复 引用
乐衣网 发表于 2010-09-17 at 11:29 回复 引用