这个题目是编程之美一书中给出的题目。
给定一个整数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
相关推荐
System.out.println("阶乘末尾0的个数为:" + countTrailingZeros(factorial)); } // 计算阶乘末尾0的个数 private static int countTrailingZeros(long num) { int zeros = 0; while (num % 10 == 0) { ...
本篇文章主要介绍如何使用C++编程语言来计算一个正整数n的阶乘末尾0的数量,并通过示例代码加以说明。该方法不仅阐述了理论基础,还提供了具体的实现思路。 #### 原理讲解 ##### 计算末尾0的数量 为了理解如何计算...
在给定的文件列表中,“n的阶乘末尾有多少个0.cpp”可能是实现这个算法的C++源代码,而“n的阶乘末尾有多少个0.exe”是编译后的可执行文件,用于直接运行程序并得到结果。 通过这种方法,我们可以有效地处理大数...
的末尾零的个数。例如10!=3628800,则Z(N)=2。 编写计算机程序有效的确定Z的值。 【输入说明】 输入的第一行是一个单个的确定的正整数T,他指名接下来的数字的个数,然后是 T 行,每一行包括一个确定的正整数N,1,...
printf("%d的阶乘末尾有%d个0\n", num, zeros); return 0; } ``` 这个程序首先定义了一个`countTrailingZeros`函数,它通过循环计算5的幂并累加n能被这些幂整除的次数来找到零的个数。在`main`函数中,用户输入一...
算法提高-计算超阶乘:挑战极限,探索编程之美! 还在为复杂的数学计算头疼吗?想要在算法领域更上一层楼?那么,你绝不能错过“算法提高-计算超阶乘”这一挑战!这不仅是一个编程题目,更是一次思维的飞跃,一次对...
在Java编程中,计算阶乘并...总结一下,确定阶乘末尾零的个数关键在于找到n中因子5的总数。对于较大的n,这个方法不仅效率高,而且节省了计算资源。在实际编程中,理解和应用这种策略对于优化算法和解决问题至关重要。
### 编程算法练习知识点详解 #### 知识点一:斐波那契数列 - **描述**:斐波那契数列是一系列数字,其中每个数字是前两个数字的和,通常从1和1开始。 - **实现思路**: - 使用循环或递归方法来生成数列。 - 循环...
这种方法不仅适用于1000,对于任何其他数字,只要调整循环的边界,都可以找出其阶乘末尾的零数量。 值得注意的是,素数在计算机科学中扮演着至关重要的角色,特别是在加密算法、数据结构设计和算法优化等方面。素数...
1. **阶乘末尾零的个数**:在计算一个数的阶乘时,我们会遇到末尾零的问题。末尾零的个数由2和5的因子个数决定,因为10=2×5。一个数的因子2总是比因子5多,所以计算因子5的数量就能确定零的个数。 2. **菱形字母**...
- 首先理解阶乘末尾0的个数是由因子5的数量决定的。 - 通过计算1到1000中能够被5、25、125、625整除的数的个数,累加这些数的个数即为1000!末尾0的总数。 - 实现中使用了递归方法来统计因子5的个数。 ### 5. 双向...
- 阶乘尾数零的个数:探究因数5与2的组合如何决定阶乘结果末尾零的数量。 - 求素数:实现一个简单的素数检测算法,如埃拉托斯特尼筛法。 - 歌德巴赫猜想:编程验证数的偶数部分是否可以表示为两个素数之和。 - ...
本问题主要探讨如何通过编程计算一个正整数`n`的阶乘`n!`结果中尾随零的数量。尾随零是指一个数末尾连续的零的数量。例如,`10! = 3628800`,则该阶乘结果中的尾随零数量为2。 #### 基础理论分析 1. **尾随零产生的...
全排列的个数可以用阶乘(n!)来表示,这是因为对于n个不同的元素,第一个位置有n种选择,第二个位置有n-1种选择,以此类推,直到最后一个位置只有1种选择。因此,总的可能性数为n * (n-1) * ... * 1 = n!。 在本程序...
阶乘,一个看似简单的数学概念,却在编程和算法领域中蕴含着丰富的知识。阶乘表示为一个正整数N的阶乘(记为N!),是所有小于及等于N的正整数的乘积。例如,5! = 5 × 4 × 3 × 2 × 1 = 120。阶乘在组合数学、...
具体来说,“0的剔除”算法的关键在于认识到在阶乘过程中,数字末尾的零是由因子2和5的乘积形成的,而且在自然数序列中,2的出现频率远高于5。因此,算法的核心思路转变为预处理,即在实际进行阶乘乘法运算之前,先...
- 这涉及数论中的质因数分解,尤其是2和5的因子个数,因为10=2×5,可以快速计算出阶乘结果末尾有多少个零。 总的来说,这些题目覆盖了编程基础、算法设计、数据结构、数据库、操作系统、计算机网络、数论等多个IT...
4. **阶乘求和**:计算1到20的阶乘之和,使用循环累乘得到每个数的阶乘,再累加至总和。 5. **字符统计**:输入一行字符,统计其中英文字母、空格、数字和其他字符的个数。这需要用到条件判断,如`isalpha()`、`...