文档章节

计算n的阶乘有多少个尾随零

borey
 borey
发布于 2014/09/11 00:29
字数 537
阅读 793
收藏 0

思路一:

    计算出n!= nValue,然后 nValue % 10 == 0 则nCount自增1,nValue /= 10 直到条件为否,最后nCount就是我们想要的结果,代码如下:

C\C++

int CountZero(int n)
{
    unsign long long nValue = 1;
    for (int i = 2; i <= n; i ++)
    {
        nValue *=i;
    }
    int nCount = 0;
    while(0 == nValue % 10)
    {
        nCount ++;
        nValue /= 10;        
    }
    return nCount;
}

    代码简洁易懂,看上去还不赖,但是这里要考虑一个问题就是在求n!整数溢出了怎么办?  显然我们使用_int64也同样会有溢出的时候,所以上面的代码实际上是不可行的。

思路二:

    不知道怎么办,不妨先举例分析:

1! = 1
2! = 1 * 2 = 2
3! = 1 * 2 *3 = 6
4! = 1 * 2 * 3 * 4 = 24
5! = 1 * 2 * 3 * 4 * 5 = 120
........
1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13
* 14 * 15 * 16 * 17 * 18 * 19 * 20 * 21 * 22 *23 * 24 * 25

我们会发现一个因子2和因子5组合产生一个0,这样我们只需统计1到n有多少个因子对,即n!的尾随零个数,因子2的个数比因子5的个数多,因此我们只需统计出因子5的个数即可,如

5,10,15,25,30,35,40.......

需要注意的是,以100!为例:

统计一次5的倍数 (5,10,15,20,25,30,35,40,45,50,55,60,65,70,75,80,85,90,95,100)= 20

统计一次25的倍数(因为25的倍数有两个5的因子,所以再统计一次)(25,50,75,100) = 4

统计一次125的倍数(125的倍数由3个5的因子,所以再统计一次,以此类推)(nil)

所以100!的尾随零个数为24个

实现代码如下:

C\C++

int CountZero(int n)
{
    int count = 0;
    if (n < 0)
        return -1;
    for (int i = 5; n / i > 0; i *= 5)
        count += n / i;
    return count;
}

运行结果:

1 1 0 0
2 2 0 0
3 6 0 0
4 24 0 0
5 120 1 1
6 720 1 1
7 5040 1 1
8 40320 1 1
9 362880 1 1
10 3628800 2 2
11 39916800 2 2
12 479001600 2 2
13 6227020800 2 2
14 87178291200 2 2
15 1307674368000 3 3
16 20922789888000 3 3
17 355687428096000 3 3
18 6402373705728000 3 3
19 121645100408832000 3 3
20 2432902008176640000 4 4
21 14197454024290336768 0 4
22 17196083355034583040 1 4
23 8128291617894825984 0 4
24 10611558092380307456 0 4

 当n=21时,21!已经溢出。Done!

© 著作权归作者所有

borey
粉丝 28
博文 55
码字总数 31182
作品 0
深圳
程序员
私信 提问
LeetCode算法题-Factorial Trailing Zeroes(Java实现)

这是悦乐书的第183次更新,第185篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第42题(顺位题号是172)。给定一个整数n,返回n!中的尾随零数。例如: 输入:3 输出:0 说明...

小川94
2018/11/26
0
0
写一个算法计算n的阶乘末尾0的个数

解答 首先,算出n的阶乘的结果再去计算末尾有多少个0这种方法是不可取的, 因为n的阶乘是一个非常大的数,分分种就会溢出。我们应当去分析, 是什么使n的阶乘结果末尾出现0。 n阶乘末尾的0来...

一贱书生
2016/11/26
78
0
学算法有啥子用? 一亿的阶乘 末尾有几个零?

如果有人问你, 计算机的能力已经这样强了,算法有啥用? 你可以问他,一个亿的阶乘后面有几个零? 这个问题不是常规计算能解决的,即使交给计算机也要花好长时间... 阶乘 阶乘是一种特殊的运算,随...

木子昭
2018/01/27
0
0
ALGO-83 算法训练 阶乘

问题描述   一个整数n的阶乘可以写成n!,它表示从1到n这n个整数的乘积。阶乘的增长速度非常快,例如,13!就已经比较大了,已经无法存放在一个整型变量中;而35!就更大了,它已经无法存放在...

xnh_565175944
2018/04/23
0
0
JavaScript实现LeetCode第172题:阶乘后的零

首文发表在 172. 阶乘后的零 题目描述 给定一个整数 n,返回 n! 结果尾数中零的数量。 示例 1: 示例 2: 思路 这个问题可以用数学的方法简单分析; 10 = 2 * 5(质因数分解) 从最末尾开始连续...

funnycoderstar
2018/09/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

读书笔记:深入理解ES6 (五)

第五章 解构:使数据访问更便捷 第1节 为什么使用解构功能?   在ES5中,开发者们从对象、数组中获取特定数据并赋值给变量,编写了很多看起来同质化的代码。例如: 1 let options = {2 ...

张森ZS
12分钟前
10
0
CentOS7 yum方式安装MySQL5.7

在CentOS中默认安装有MariaDB,这个是MySQL的分支,但为了需要,还是要在系统中安装MySQL,而且安装完成之后可以直接覆盖掉MariaDB。 1 下载并安装MySQL官方的 Yum Repository [root@localho...

roockee
21分钟前
7
0
Allegro三种自定义设置快捷键的方法

Allegro自定义设置快捷键的三种方法: 1、在Allegro PCB editor 命令窗口直接定义 2、通过修改用户变量env文件来设置快捷键 3、定义笔画为快捷键 1、在Allegro PCB editor 命令窗口直接定义 ...

demyar
25分钟前
12
0
如何做一张能让人眼前一亮的大屏?

作为在职场驰骋的社会人,提到数据可视化大家应该都不陌生了。数据可视化的作用也不用我多说,主要是利用图形化手段,更清晰直观地将数据展示。多层次、交互式的可视化分析能够方便决策者理解...

朕想上头条
26分钟前
7
0
TL138/1808/6748-EthEVM开发板硬件CPU、FLASH、RAM

TL138/1808/6748-EthEVM是广州创龙基于SOM-TL138/1808/6748核心板开发的一款开发板,具有三个网络接口。由于SOM-TL138/1808/6748核心板管脚兼容,所以此三个核心板共用同一个底板。开发板采用...

Tronlong创龙
30分钟前
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部