编程之美-阶乘末尾0的个数

这个题目是编程之美一书中给出的题目。

给定一个整数N，那么N的阶乘N！末尾有多少个0？ 比如：N=10，N！=3628800,N！的末尾有2个0。

1) 递推

考虑阶乘的计算很容易溢出，直接计算阶乘肯定不合适。而每次相乘是否会有新的0产生，只和前一个阶乘的最后一位有关。因此只记录前一个阶乘0的个数和最后一位，就可推出后面的。

代码如下：

01	int countZero(int N) {

02	int ans = 0;

03	int lastBit = 1; //上一个阶乘 的最后一位数字

04	for (int i = 2; i <= N; i++) {

05	int cnt = 0;//新增加的0的个数

06	int tmp = lastBit * i;

07	while ((tmp % 10) == 0) {

08	tmp /= 10;

09

cnt++;

10

}

11	while (tmp > 10)

12	tmp = tmp % 10;

13	lastBit = tmp;

14	ans += cnt;

15

}

16	return ans;

17

}

18

19	int main() {

20	cout << countZero(10) << endl;

21	cout << countZero(356) << endl;

22

return 0;

23

}

2）数学解法

编程之美一书给出两个例如质因数的性质的解法。考虑哪些组合可以得到10即可，考虑哪些数相乘能得到10，N!= K * 10^M其中K不能被10整除，则N!末尾有M个0。

对N!进行质因数分解： N!=2^X*3^Y*5^Z…，因为10=2*5，所以M与2和5的个数即X、Z有关。每一对2和5都可以得到10，故M=min(X,Z)。因为能被2整除的数出现的频率要比能被5整除的数出现的频率高，所以M=Z。其实也很好推出，1-9 中两两相乘，末位有0的话必须要有5，其它的数则是2的倍数。

01	int countZero(int N)

02

{

03	int ret = 0;

04

int j;

05	for(int i=1; i<=N; i++)

06

{

07

j = i;

08	while(0==j%5)

09

{

10

ret++;

11

j /= 5;

12

}

13

}

14	return ret;

15

}

当然还有一种解法：

    Z =[N/5] + [N/5²] + [N/5³] + …

    [N/5] 表示不大于N的的数中5的倍数贡献一个5, [N/5²] 表示不大于N的数中5²的倍数在贡献一个5……

01	int countZero(int N)

02

{

03	int ret = 0;

04

while(N)

05

{

06	ret += N/5;

07

N /= 5;

08

}

09	return ret;

10

}

参考：http://blog.sina.com.cn/s/blog_73428e9a0101b3nh.html

原文：http://www.acmerblog.com/factorial-zero-number-5683.html

评论

3 楼 gaotong1991 2014-04-19  

jiang911113 写道

递推那个有问题， 25!你试下

考虑的少了，已更新，参考：http://www.acmerblog.com/factorial-zero-number-5683.html

2 楼 gaotong1991 2014-04-19  

jiang911113 写道

递推那个有问题， 25!你试下

多谢指出

1 楼 jiang911113 2014-04-16  

递推那个有问题， 25!你试下