当前位置:首页 > 开发 > 编程语言 > 算法 > 正文

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

发表于: 2013-06-07   作者:周凡杨   来源:转载   浏览:
摘要:                                  &n

                                                                                题:给定一个整数N,求出N!末尾有多少个零,比如N=10N!=362880010!末尾有两个零。

 

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

阶乘(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;
}

 

    时间复杂度为:Nlog5N     

 

解题思路二:

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时,令n5k * 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”一一对应。 

n5k * 5(k-1) * ... * 10 * 5 * a = (5k * k!) *a

 

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

 f(n!) = g(n!) = g(5k * k!* a) =g(5k * 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);
}

  时间复杂度为:log5

 

 解题思路三:

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

    所以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;
}
时间复杂度为:log5

 

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

 

后记(顿悟):

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

                                                                    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/

 《编程之美》

  

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

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
考虑这么一个 14 位数 02565413989732 ,如图所示,它的数字先逐渐变大,然后开始变小,再变大,再
/* 02.* 程序的版权和版本声明部分 03.* Copyright (c)2012, 烟台大学计算机学院学生 04.* All righ
/* 烟台大学计算机学院 作者:任子仪 日期:2013年11月20日 问题描述: 样例输入: 样例输出: 问题
我的程序: 01./* 02.* 程序的版权和版本声明部分: 03.* Copyright (c) 2013, 烟台大学计算机学院 0
我的程序: 01./* 02.* 程序的版权和版本声明部分: 03.* Copyright (c) 2013, 烟台大学计算机学院 0
/* 02.02.* Copyright (c) 2012, 烟台大学计算机学院 03.03.* All rights reserved. 04.04.* 作 者
/* * Copyright (c) 2012, 烟台大学计算机学院 * All rights reserved. * 作 者: 刘同宾 * 完成日
大数阶乘 问题描述:编写程序,对给定的n(n <= 100),计算并输出k的阶乘k!的全部有效数字。 注意
import java.util.HashMap; import java.util.Iterator; import java.util.Map; public class lzwCo
一串首尾相连的珠子(m 个),有N 种颜色(N<=10), 设计一个算法,取出其中一段,要求包含所有N 中
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号