常见算法之15---求N!末尾有多少个0

题目:求N!末尾有多少个0


方案一:暴力法。
分析:这很容易造成溢出得到错误的结果,并且运算的时间也较长。若是面试的时候你这样解,那么可以say goodbye了。

方案二:其实没有必要求出最后的结果再去数究竟有多少个0。

    我们可对一个数进行分解,分解成尽可能小的数字相乘的形式(其实也就是尽可能小的素数相乘),你会发现0只会来源于2*5。
所以我们可以看看有多少个2和5成对出现。
   而在阶乘之中,显而易见2的个数一定是多于5的个数,所以我们就看看出现了多少个5。
   以1234!为例,末尾为5的数有1234/5 = 246个,但这246个数中其实还有包含5存在的数(因为会包含25,125这种除以5之后,还能被5整除的数字)
故,该方法可总结为:  
       1 将该数用5除,得到的商取整数。  
       2 然后再用所得商当被除数除以5,得到的商取整数。  
       3 持续做到商等于0为止。  
       4 过程中的商加总即为阶乘的尾数0的个数。  


代码:
int f(int n){
        int i = n/5;
       int sum = 0;
       while(i != 0 ){
              sum += i;
              i = i/5;
       }
       return sum;
}

原文地址:https://www.cnblogs.com/xiaoChongUp/p/3355021.html