这个题目是编程之美一书中给出的题目。
给定一个整数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 * 10M其中K不能被10整除,则N!末尾有M个0。
对N!进行质因数分解: N!=2X*3Y*5Z…,因为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/52] + [N/53] + …
[N/5] 表示不大于N的的数中5的倍数贡献一个5, [N/52] 表示不大于N的数中52的倍数在贡献一个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
相关推荐
NULL 博文链接:https://z-jls03.iteye.com/blog/830994
C++版本计算n阶乘末尾0的个数原理讲解及代码实现
的末尾零的个数。例如10!=3628800,则Z(N)=2。 编写计算机程序有效的确定Z的值。 【输入说明】 输入的第一行是一个单个的确定的正整数T,他指名接下来的数字的个数,然后是 T 行,每一行包括一个确定的正整数N,1,...
题解:求n的阶乘末尾0的数量。因为n的阶乘容易爆整数范围,所以普通算法不合适。用高精度容易超时,这里直接给出数学求解过程
Python编程题--整数阶乘
判断阶乘末尾有几个零 阶乘 不计算阶乘 不计算阶乘
递归分治-1-阶乘.cpp
java源代码--实现阶乘的计算。。。。。。。。。。。。。
ARM汇编语言程序设计实例解析-阶乘操作
C1-阶乘和.cpp
c语言-阶乘算法(迭代和递归).docx
Java 实例 - 阶乘源代码-详细教程.zip
ARM汇编语言程序设计实例解析-阶乘操作终版.pdf
算法-阶乘和(信息学奥赛一本通-T1173)(包含源程序).rar
无论您是Java编程的初学者还是有经验的程序员,该资源都将为您提供有价值的指导和支持,帮助您掌握Java中计算阶乘之和的方法。我们相信,该资源将成为想提高算法设计技能的Java程序员的宝贵参考资料。
1-10的阶乘 #include"stdio.h" void main() { long a=1,n,s=0; for(n=1;n;n++) { a*=n;/*求阶乘*/
数的阶乘定义为 N!=1 x 2 x 3 x ... x N。 编写计算机程序确定 N!并用科学记数法输出结果,精确到小数点后4位。 【输入说明】 输入的第一行是一个单个的确定的正整数T,他指名接下来的数字的个数,然后是T行,每...
python零基础初学者 体验程序
ARM汇编语言程程序设计精讲,ARM汇编语言程序设计实例解析。求阶乘
昆明理工大学信息工程与自动化学院学生实验报告 ( 2010 —2011 学年 第 一学期 ) 课程名称:汇编与微机接口 开课实验室: 2010年12月10日 "年级、专业、 "计科083 "学号 " " "班 " " " " "教师评" " "语 " " " ...