一个阶乘中末尾零的个数

分手后的思念是犯贱 2022-01-05 23:19 292阅读 0赞

//给定一个正整数n，请计算n的阶乘n！末尾所含有“0”的个数。

*  5！=120，其末尾所含有的“0”的个数为1；
 *  10！= 3628800，其末尾所含有的“0”的个数为2；
 *  20！= 2432902008176640000，其末尾所含有的“0”的个数为4。
 *  //分析：
 *  两个数相乘尾数0的个数其实就是依赖于2和5因子的个数
 *  每两个连续数字就会有一个因子2
 *  只需要关心5因子的个数
 *  n = 5\*K + r（0<= r <= 4）
 *  n! = (5\*K) \* (5\*(K-1)) \* (5\*(K-2)) \* ... \* 5 \* A
 *  **f(n!) = g(n!) = g(5^K \* K! \* A) = K + g(K!) = K + f(K!)，其中K=n / 5（取整数）。**
 *  **0 <= n <= 4时，f(n!)=0**
 *   *  f(5!) = 1 + f(1!) = 1
     *  f(10!) = 2 + f(2!) = 2
     *  f(20!) = 4 + f(4!) = 4
     *  f(100!) = 20 + f(20!) = 20 + 4 + f(4!) = 24
     *  f(1000!) = 200 + f(200!) = 200 + 40 + f(40!) = 240 + 8 + f(8!) = 248 + 1 + f(1) =249

1 #include <iostream>
     2 using namespace std;
     3 
     4 int GetN_1(int n)
     5 {
     6 if (n < 5)
     7 {
     8 return 0;
     9 }
    10 else
    11 {
    12 return (n / 5 + GetN_1(n / 5));//利用递归找一个阶乘中末尾零的个数
    13 }
    14 }
    15 int GetN_2(int n)//采用循环的方式找一个阶乘中末尾零的个数
    16 {
    17 int m, count=0;
    18 for(int i=1;i<=n;i++)
    19 {
    20 m=i;
    21 while(m%5==0)
    22 {
    23 count++;
    24 m/=5;
    25 }
    26 
    27 }
    28 return count;
    29 }
    30 int main()
    31 {
    32 cout << GetN_1(1000) << endl;
    33 cout << GetN_2(1000) << endl;
    34 
    35 return 0;
    36 }

转载于:https://www.cnblogs.com/delongzhang/p/11027442.html

发表评论取消回复

表情：

评论列表（有 0 条评论，292人围观）

还没有评论，来说两句吧...

相关阅读

相关阶乘尾部0的个数

阶乘尾部0的个数输入输入数据有若干行，每行上有一个非负整数n，对应一种情形。输出对于每一种情形，直接输出结果、换行。样例输入 8 16

素颜马尾好姑娘i/ 2023年03月04日 06:54/ 0 赞/ 33 阅读

相关设计一个算法，计算出n阶乘中尾部零的个数

设计一个算法，计算出n阶乘中尾部零的个数样例 1: 输入: 11 输出: 2 样例解释: 11! = 39916800, 结尾的0有2个。

冷不防/ 2023年02月22日 13:39/ 0 赞/ 17 阅读

相关 C\C++求N的阶乘！的值中末尾0的个数实践小记

C\\C++求N的阶乘！的值中末尾0的个数实践小记一、问题描述二、问题解决思路三、实践源码方法一：测试数据1

秒速五厘米/ 2022年12月28日 07:26/ 0 赞/ 143 阅读

相关求n的阶乘末尾有几个零

通过因数分解知道，10是由2和5相乘得到的，而在n的阶乘中，因子2的数目总是比5多的，所以最终末尾有几个零取决于其中有几个5。1到n中能够整除5的数中有一个5，能整除

布满荆棘的人生/ 2022年08月22日 13:28/ 0 赞/ 195 阅读

相关计算n阶乘中尾部零的个数

今天开始算法练习，刚开始感觉挺简单的一个题，怎么就让自己乱了手脚。题目：设计一个算法，计算n阶乘中尾部零的个数结果： 11! = 39916800，因此应该

ゝ一世哀愁。/ 2022年06月01日 09:36/ 0 赞/ 232 阅读

相关算一算N阶乘的尾随零个数

问题描述很简单: 求解N阶乘的尾随零个数而所谓尾随零个数,即是从个位数开始,数字连续为0的个数. 譬如: 3!(阶乘符号,下同) = 3 \ 2 \ 1 = 6, 尾

r囧r小猫/ 2022年05月23日 07:34/ 0 赞/ 211 阅读

相关尾部的零（设计一个算法，计算出n阶乘中尾部零的个数）

这里我们知道，大家最平常的思维就是用一个数来接收n阶乘后的数，然后再来判断那个和的尾部的0的个数，这样的算法算得上O（n）级，还有一个隐患，就是就算用long来存储数据，也不会

桃扇骨/ 2022年05月19日 07:21/ 0 赞/ 189 阅读

相关尾部的零设计一个算法，计算出n阶乘中尾部零的个数

思路：一个n的阶乘未尾有多少个 0 取决于 1 到 n 的各个因子中 2 和 5 的个数，而2的个数是远远多于5的个数的，因此求出5的个数即可。题解中给出的求解因子 5

待我称王封你为后i/ 2022年03月06日 02:26/ 0 赞/ 186 阅读

相关一个阶乘中末尾零的个数

//给定一个正整数n，请计算n的阶乘n！末尾所含有“0”的个数。 5！=120，其末尾所含有的“0”的个数为1； 10！= 3628800，其末尾所含有的“

分手后的思念是犯贱/ 2022年01月05日 23:19/ 0 赞/ 293 阅读

相关阶乘N!的末尾有多少个0

思路：5\2=10,即每个5与2都能产生一个0，而在阶乘中，偶数很多，即2比5多 1-N中有N/5个数，每个数能贡献一个5,1-N有N/5^2个数，每个数又能贡献一个5等等

川长思鸟来/ 2021年09月26日 14:48/ 0 赞/ 481 阅读