本文共 938 字,大约阅读时间需要 3 分钟。
N的阶乘N!中的末尾有多少个0?
问题:N的阶乘N!中的末尾有多少个0? 例如:N = 5,N! = 120.末尾有1个0. 分析: 想到这个问题,有人可能第一反应就是先求出N!,然后再根据求出的结果,最后得出N!的末尾有多少个0。但是转念一想,会不会溢出,等等。 其实,从"哪些数相乘可以得到10"这个角度,问题就变得比较的简单了。
(1)首先考虑,如果N的阶乘为K和10的M次方的乘积,那么N!末尾就有M的0。 (2)如果将N的阶乘分解后,那么N的阶乘可以分解为:2的X次方,3的Y次方,4的0次方(2的X次方已计算),5的Z次方.....的乘积。 由于10 = 2 * 5,所以M只能和X和Z有关,每一对2和5相乘就可以得到一个10。 于是M = MIN(X, Z),不难看出X大于Z,因为被2整除的频率比被5整除的频率高的多。所以可以把公式简化为M = Z。 由上面的分析可以看出,只要计算出Z的值,就可以得到N!末尾0的个数 方法一:要计算Z,最直接的方法就是求出N的阶乘的所有因式(1,2,3,...,N)分解中5的指数,然后求和。
int zero(int n){ int num = 0; for (int i = 5; i <= n; i += 5) { int j = i; while (j % 5 == 0) { num++; j /= 5; } } return num;}
方法二: Z = N / 5 + N / (5 * 5) + N / (5 * 5 * 5).....直到N / (5的K次方)等于0 公式中N / 5表示不大于N的数中能被5整除的数贡献一个5,N / (5 * 5)表示不大于N的数中能被25整除的数贡献一个5.......
int zero(int n){ int num = 0; while(n) { num += n / 5; n /= 5; } return num;}
练习题:
原文链接:
转载地址:http://vnkxi.baihongyu.com/