阶乘算法之一N! 末尾有多少个零

                                                                                题：给定一个整数N，求出N!末尾有多少个零，比如N=10，N!=3628800，10！末尾有两个零。

 

首先温固一下阶乘的相关知识！

阶乘(factorial)是基斯顿·卡曼(Christian Kramp, 1760 – 1826)于1808年发明的运算符号。阶乘，也是数学里的一种术语。
任何大于1的自然数n阶乘表示方法：n!=1×2×3×……×n 或n!= n×(n-1)! 
0！=1，注意(0的阶乘是存在的).
双阶乘：
    当n为奇数时表示不大于n的所有奇数的乘积 如：7!!=1×3×5×7
     当n为偶数时表示不大于n的所有偶数的乘积(除0外） 如：8!!=2×4×6×8
     小于0的整数-n的阶乘表示：
   （-n）！= 1 / (n+1)!

   双阶乘是怎么提出来的，是根据阶乘推导出来的吗？这点百思不解？

 

然后理一下本题的解题思路：

      N个自然数相乘，结尾0的个数，依赖有多少个10相乘（有两个10相乘，结尾0的个数就为2），10=2×5，则可以理解为结尾0的个数依赖因子中2的个数和5的个数，而对于连续的自然数来说，2出现的频率比5高的多，所以最终只需要计算出因子中5的个数，即为答案。

 

   把想法整理为JAVA代码，如下所示：

 解题思路一：分析阶乘因子中的每一个数，计算其包含5的个数，最后求总和

   

private int zeroNum(int n){
      int ret = 0;
      for(int i=1;i<=n;i++){
        int j=i;
        while(j%5 == 0){
           ret++;
           j/=5;
        }
      }
      return ret;
}

 

    时间复杂度为：Nlog₅N     

 

解题思路二：

令f(x)表示正整数x末尾所含有的“0”的个数，则有： 
      当0 < n < 5时，f(n!) = 0; 
      当n >= 5时，f(n!) = k + f(k!), 其中 k = n / 5（取整）

 

     下面对这个结论进行证明： 
    (1) 当n < 5时, 结论显然成立。 
    (2) 当n >= 5时，令n！= （5k * 5(k-1) * ... * 10 * 5） * a，其中 n = 5k + r (0 <= r <= 4)，a是一个不含因子“5”的整数。 
    对于序列5k, 5(k-1), ..., 10, 5中每一个数5i(1 <= i <= k)，都含有因子“5”，并且在区间 [5(i-1), 5i] (1 <= i <= k)内存在偶数，也就是说，a中存在一个因子“2”与5i相对应。即，这里的k个因子“5”与 n！末尾的k个“0”一一对应。 

n！= （5k * 5(k-1) * ... * 10 * 5） * a = (5^k * k!) *a

 

令f(x)表示正整数x末尾所含有的“0”的个数, g(x)表示正整数x的因式分解中因子“5”的个数，则利用上面的的结论有： 

 f(n!) = g(n!) = g(5^k * k!* a) =g(5^k * k!)= k + g(k!) = k + f(k!) 
所以，最终的计算公式为： 
    当0 < n < 5时，f(n!) = 0; 
    当n >= 5时，f(n!) = k + f(k!), 其中 k = n / 5（取整）。 

 

 

public int method02(int n){
      int ret = 0;
      if(n<5){
        return ret;
      }
      int k = n/5;
      return k + method02(k);
}

  时间复杂度为：log₅N 

 

 解题思路三：

    乘积末尾的0的个数依赖于因子中的2的个数和5的个数。对于阶乘来说，每2个数字就至少有一个2的因子，所以2的因子是足够的。5的因子相对少些，至少连续5个数才能保证一定出现一个。注意，这里连续5个书保证出现一个5的因子是指最少的情况。比如1，2，3，4，5，这就只会出现一个。但是考虑 21，22，23，24，25，25 = 5 * 5,所以如果乘以25那就能得到2个5的因子。依次会有3个5的因子…

    所以n!中5的个数的计算是：[n/5]+[n/(5*5)]+[n/(5*5*5)]+....

 

public int method03(int n){
       int ret = 0;
       int baseNum = 5;
       while (n >= baseNum)
       {
           ret += n/baseNum;
           baseNum *= 5;
       }
       return ret;
}

时间复杂度为：log₅N 

 

       对于解法二和解法三，我这里写的时间复杂度都为log₅N  ,但实际验证，解法三比解法二更高效，所以不知道是否时间复杂度写的有问题？高人求解！！！

 

后记（顿悟）：

    算法三之所以优于算法二，因为算法二是用到递归算法，递归一系列的函数调用，而函数的调用开销是很大的，系统要为每次函数调用分配存储空间，并将调用点压栈予以记录。而在函数调用结束后，还要释放空间，弹栈恢复断点。所以说，函数调用不仅浪费空间，还浪费时间。所以算法三在时间复杂度和空间复杂度上是优于算法二的。

                                                                    2013.6.20

 

参考资料：

  http://blog.csdn.net/chn_cf/article/details/6541281

  http://www.chinaunix.net/old_jh/23/926848.html

  http://www.pureweber.com/article/recursive-power-4/

 《编程之美》

  

评论

2 楼 cherami 2017-05-15  

解法3有问题，在n很大的时候会导致baseNum溢出使得结果不对
需要把baseNum的类型改成long型
例如n的值是1808548330时，算出来是452137079，但是正确答案是452137077

1 楼 yygymmmmsee 2013-06-09  

第二和第三两个算法本质应该是一致的吧

只不过第二个使用了递归，第三个是一个循环

这也有可能是造成第二个效率比第三个低的原因