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

计算阶乘末尾0的个数

2013年08月25日 ⁄ 综合 ⁄ 共 536字 ⁄ 字号 评论关闭

这个题目是编程之美上出现的,今年在几个公司笔试的时候都出现了这个题目,之前一直以为 直接用 N  /  5 就是结果,昨天被土豆面试的时候,才发现自己理解错了,思路是这样的,0 的个数就是 1,,2,...,n中n个数中能够分解出5的因子的个数。之前以为 5,10,20,..., n/5 * 5   总共有  n/5个能够提出5的因子的,但是显然这里出现了问题,对于 25 这个数 = 5^2 能提出两个5的因子,所以应该会产生两个0。那我们该怎么解决这个问题呢,我们将5,10,20,....,n/5 * 5
 提出一个因子5 ,5*1,5*2,5*3,5*4,5*5,5*(n/5)
即 5(1,,2,3,4,...,n/5) 后面括号中又会产生5,而且是按照前面同样的方式。 所有能够产生5的个数应该是:n/5+n/5/5+n/5/.../5,一直到某个数/5=0 。如对于n=2000,末尾0的个数为:


 5  2000

 5    400

 5      80

 5      16

            3  ... 1  

所有0的个数为 = 2000/5+ 400/5 + 80/5 + 16/5 = 400+80+16+3 = 499

好了,其实简单的程序如下:

int calcZero(int n)
{ 
   int sum = 0;
   while(n / 5) sum+= n/5;
   return sum;
}

抱歉!评论已关闭.