Posted on 2007-04-19 15:30
kk 阅读(885)
评论(1) 编辑 收藏 引用 所属分类:
Algorithm
终于悟到了。
首先,很容易想到的就是,求0的个数,就是求5的个数(如果这个你都想不明白的话,那就。。。再好好想想吧,呵呵);
接下来,如何求5的个数呢?如果遍历一遍的话,那显然是太慢了!因为这种计算题太有规律了!想了好久,终于想出来了:
Result = 0; // 最后的结果
while ( N >= 5 )
{
N /= 5;
Result += N;
}
// 结束了。
没错,就是这么简单!下面简单说说为什么这样子做是对的(偶小试了一下,没问题,呵呵):
第一次除以5表示5的倍数的个数,
第二次除以5表示5的平方的倍数的个数,(显然,5的平方暗含了两个0)
。。。依此类推
最后当N<5了,结束。
小小的验证一下:
26!
26/5 = 5, 5/5 = 1,那么最后0的个数就是6了。用Google算了一下,结果G大叔直接用有效数字表示了,@$%$%@$%。。。不过应该是没错了。恩。
Sigh,知道结果后才知道原来这么简单的阿,偶土了。