解答

首先，算出n的阶乘的结果再去计算末尾有多少个0这种方法是不可取的， 因为n的阶乘是一个非常大的数，分分种就会溢出。我们应当去分析， 是什么使n的阶乘结果末尾出现0。

n阶乘末尾的0来自因子5和2相乘，5*2=10。因此，我们只需要计算n的阶乘里， 有多少对5和2。注意到2出现的频率比5多，因此，我们只需要计算有多少个因子5即可。 我们可以列举一些例子，看看需要注意些什么：

 

5!, 包含1*5, 1个5 10!, 包含1*5,2*5, 2个5 15!, 包含1*5,2*5,3*5, 3个5 20!, 包含1*5,2*5,3*5,4*5, 4个5 25!, 包含1*5,2*5,3*5,4*5,5*5, 6个5 ...

1 2 3 4 5 6 7

5!, 包含1*5, 1个5 10!, 包含1*5,2*5, 2个5 15!, 包含1*5,2*5,3*5, 3个5 20!, 包含1*5,2*5,3*5,4*5, 4个5 25!, 包含1*5,2*5,3*5,4*5,5*5, 6个5 ...

 

给定一个n，用n除以5，得到的是从1到n中包含1个5的数的个数；然后用n除以5去更新n， 相当于把每一个包含5的数中的因子5取出来一个。然后继续同样的操作，让n除以5， 将得到此时仍包含有5的数的个数，依次类推。最后把计算出来的个数相加即可。 比如计算25的阶乘中末尾有几个0， 先用25除以5得到5，表示我们从5,10,15,20,25中各拿一个因子5出来，总共拿了5个。 更新n=25/5=5，再用n除以5得到1，表示我们从25中拿出另一个因子5， 其它的在第一次除以5后就不再包含因子5了。

代码如下：

 

int NumZeros(int n){ if(n < 0) return -1; int num = 0; while((n /= 5) > 0){ num += n; } return num; }

1 2 3 4 5 6 7 8

int NumZeros(int n){     if(n < 0) return -1;     int num = 0;     while((n /= 5) > 0){         num += n;     }     return num; }

 

思路一：

    计算出n！= nValue，然后 nValue % 10 == 0 则nCount自增1，nValue /= 10 直到条件为否，最后nCount就是我们想要的结果，代码如下：

C\C++int CountZero(int n){    unsign long long nValue = 1;    for (int i = 2; i <= n; i ++)    {        nValue *=i;    }    int nCount = 0;    while(0 == nValue % 10)    {        nCount ++;        nValue /= 10;            }    return nCount;}

 

    代码简洁易懂，看上去还不赖，但是这里要考虑一个问题就是在求n！整数溢出了怎么办？  显然我们使用_int64也同样会有溢出的时候，所以上面的代码实际上是不可行的。

 

思路二：

    不知道怎么办，不妨先举例分析：

1！ = 12！ = 1 * 2 = 23！ = 1 * 2 *3 = 64！ = 1 * 2 * 3 * 4 = 245！ = 1 * 2 * 3 * 4 * 5 = 120........1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13* 14 * 15 * 16 * 17 * 18 * 19 * 20 * 21 * 22 *23 * 24 * 25

 

我们会发现一个因子2和因子5组合产生一个0，这样我们只需统计1到n有多少个因子对，即n！的尾随零个数，因子2的个数比因子5的个数多，因此我们只需统计出因子5的个数即可，如

5,10,15,25,30,35,40.......

 

需要注意的是，以100！为例：

统计一次5的倍数 （5,10,15,20,25,30,35,40,45,50,55,60,65,70,75,80,85,90,95,100）= 20

统计一次25的倍数（因为25的倍数有两个5的因子，所以再统计一次）（25,50,75,100） = 4

统计一次125的倍数（125的倍数由3个5的因子，所以再统计一次，以此类推）（nil）

所以100！的尾随零个数为24个

实现代码如下：

C\C++int CountZero(int n){    int count = 0;    if (n < 0)        return -1;    for (int i = 5; n / i > 0; i *= 5)        count += n / i;    return count;}

运行结果：

1 1 0 02 2 0 03 6 0 04 24 0 05 120 1 16 720 1 17 5040 1 18 40320 1 19 362880 1 110 3628800 2 211 39916800 2 212 479001600 2 213 6227020800 2 214 87178291200 2 215 1307674368000 3 316 20922789888000 3 317 355687428096000 3 318 6402373705728000 3 319 121645100408832000 3 320 2432902008176640000 4 421 14197454024290336768 0 422 17196083355034583040 1 423 8128291617894825984 0 424 10611558092380307456 0 4

 

 当n=21时，21！已经溢出。Done！

分析：

就是算，阶乘中总共有几个 2*5，又因为2总是比5多，所以算出有几个5相乘就可以。

注意：25算两个，因为5*5， 125算三个，因为5*5*5.

具体算法是这样，

第一遍，算阶乘中5的倍数有几个，即 n/5

第二遍，算阶乘中25的倍数有几个，即n/25，（这里25就不用算两次，因为在算5的倍数时已经算了一次25）

。。。。。。

最后将这些结果相加即为所求。

 

[java]

1. package cci.section17;  
2.   
3. public class CCI_17_3 {  
4.       
5.     public static int zeroNum(int n){  
6.         int num = 0;  
7.         if(n<0) return -1;  
8.         for(int i=5; n/i>0; i*=5){  
9.             num += n/i;  
10.         }  
11.         return num;  
12.     }  
13.   
14.     public static void main(String[] args) {  
15.         // TODO Auto-generated method stub  
16.         System.out.println(zeroNum(30));//6  
17.     }  
18.   
19. }