黑马程序员技术交流社区

标题: N的阶乘末尾有多少零 [打印本页]

---

作者: iWilliam    时间: 2014-7-2 23:01
标题: N的阶乘末尾有多少零


刚才逛论坛，一不小心又看到了这个问题，发现貌似没有解释的很清楚的，一时心血来潮，写一哈我认为最高效的解决方案

1.         public static int countZero(int n)
   
2.         {
   
3.                 int result = 0;
   
4.                 while (n > 0)
   
5.                         result += n /= 5;
   
6.                 return result;
   
7.         }

复制代码

其实最核心的，就是这一行

1. result += n /= 5;

复制代码

搞清楚算法的思路，上面这行代码就能搞明白了
1.明确两点：
A从[1,N]中，有大约一半是偶数(能被2整除)
B末尾为零，只能是乘以10，而10只能是2*5，所以，这个问题等价于找到N！里有多少个因子5

任意小于N的数，能被5整除的话，一定存在下述关系：
N>=5*M(M=1,2,3...)
那好了，M的最大值=(int)N/5
于是得到一个数列：1,2,3,4... ... M
这个数列就是含有至少一个5的所有因数

然后，再从这个数列中找含有一个5的所有因数（实际上是找含有5*5的所有因数）得到一个新的数列：1,2,3... ...(int)N/25

以此类推，可以得到含有最多个5的数，所以要反复的除以5，于是便得到了这行代码
n /= 5
每次得到的数列项数累加：便有了result += n /= 5;

OK，这个算法本身没有问题，但是上面的代码并非完美，当N足够大时，由于N/5直接取整，反复的取整之后，丢失的余数累计会超过5，于是，会造成丢失若干“边界值”，那么最终得到的结果会偏小，如Integer.MAX_VALUE，就会丢失5个这样的边界值，只要对上面的代码略加修改便可：

1.         public static int countZero(int n)
   
2.         {
   
3.                 int result = 0;
   
4.                 int temp = 5;
   
5.                 while (0 < temp && temp <= n)
   
6.                 {
   
7.                         result += n / temp;
   
8.                         temp *= 5;
   
9.                 }
   
10.                 return result;
    
11.         }

复制代码

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2