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

秒速五厘米 2022-12-28 07:26 128阅读 0赞

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

*  一、问题描述
 *  二、问题解决思路
 *  三、实践源码
 *   *  方法一：
     *  测试数据1
     *  测试结果1
     *  方法二：
     *  测试数据2
     *  测试结果2
 *  四、小结

***叮嘟！这里是小啊呜的学习课程资料整理。好记性不如烂笔头，今天也是努力进步的一天。一起加油进阶吧！***  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center]

# 一、问题描述 #

给定一个正整数n，那么n的阶乘n！的值的末尾中有多少个0呢？

例如：n=10，n！=3628800,则n！的末尾有两个0；

# 二、问题解决思路 #

首先，很容易想到的就是：求0的个数就是求5的个数。

一个数尾部有多少个0，先看这个数的因子，也就是因子分解。  
如 10 分解为2 5，20 分解为2 2 5，100 分解为 2 2 5 5。

多找几组数据，发现**尾部0的个数**为`min{2的个数，5的个数}`。

为什么会这样呢？因为尾部的0是由2*5得出的，当然也可以是4*5，但是4=2\*2呀，最终0还是由2和5造出来的。一对2和5造出来一个0，n对2和5造出n个0，如果有10个2，8个5，则只能凑出8对，所以是min\{…\}.  
**阶乘也就是因子分解的过程，而且因子从小到大排好了。**  
**2的个数肯定比5多，因为5大。**

所以这个题，看因子中5出现的次数就可以啦。

接下来，如何求5的个数呢？如果遍历一遍的话，那显然太慢了！因为这种计算题太有规律了！

算法思想如下：
    
    对于任意一个正整数N！，都可以化为N！= （2^X)  * （3^Y）* （5^Z）......的形式，要求得末尾0的个数只需求得min(X, Z)即可，
    
    由于是求N！，则X >= Z; 即公约数5出现的频率小于等于2出现的频率，即Z=min（X, Z），即出现0的个数等于公约数5出现的次数；

这里n阶乘用n!表示。

5！ –> 1 2 3 4 5 有一个5 
    10! –> 1 2 3 4 5 6 7 8 9 10 有2个5（10=2*5） 
    ...
    25! –> 1 2 3 4 5 …10 ..15 ..20 ..24 25 有6个5（25=5*5）
    ...
    125！ = 5 10 15 …25 ..50 ..75 ..100 ..125 有多少个5呢？ 
    
    我们发现每隔5个数出现一个5，隔25个数多出来1个5..隔125个数再多出一个5 
    也就是从n个抽出5 
    5 10 15 20 25 30 … = 5（*1 2 3 4 5 ） 
    然后从上面序列中再隔5抽 
    25 50 75 100 125 … = 5*5*（1 2 3 4 5 ） 
    再隔5抽 
    125 250 375 500 625 .. = 5*5*5（1 2 3 4 5 ）
    ...

规律很明显了。

# 三、实践源码 #

## 方法一： ##

#include <stdio.h>
    int main()
    { 
        int N;                      
        int sum = 0; 
        scanf("%d", &N);          // 输入N
        for(int i = 1; i <= N; i++)
        { 
            int j = i;
            while(0 == j % 5)
            { 
                sum++;            // 统计公约数5出现的频次
                j /= 5;
            }
        }
        printf("%d\n", sum);
        return 0;
    }

## 测试数据1 ##

25! –> 1 2 3 4 5 …10 ..15 ..20 ..24 25 有6个5（25=5*5）

## 测试结果1 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70]

## 方法二： ##

#include <stdio.h>
    int main()
    { 
    	int N;
    	int sum = 0;
    	scanf("%d", &N);
    	while(N)
    	{ 
    		sum += N / 5;
    		N /= 5;
    	}
    	printf("%d\n", sum);
    	return 0;
    }

第一次除以5表示5的倍数的个数，  
第二次除以5表示5的平方的倍数的个数，（显然，5的平方暗含了两个0）  
…依此类推  
最后当N<5了，结束。

## 测试数据2 ##

25! –> 1 2 3 4 5 …10 ..15 ..20 ..24 25 有6个5（25=5*5）

## 测试结果2 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70 1]

# 四、小结 #

末尾0的个数就是指这个数`总共有几个10因子`，而10又能表示成`2和5的乘积`。假设m=n!，那么m中2的因子个数肯定大于5的因子个数，所以`m中5的因子个数`即是所要求结果；

显然`n除以5`可得到`1~n中包含有一个因子5的个数`，但是，`1~n中有的数可以被5整除好几次`，所以必须`将这个数再除以5`，得到`1~n中包含有两个因子5的个数`，**依次循环进行累加**即可得到`全部5的因子个数`；

**Ending！**  
更多课程知识学习记录随后再来吧！

就酱，嘎啦！

![在这里插入图片描述][20200207152559955.png_pic_center]

注：  
人生在勤，不索何获。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/07bc3e616c3e4f19a8321883f8e760ad.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70]: /images/20221120/b65432a531ac4b82bfaea851af57f7cd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70 1]: /images/20221120/8a313c9bd00641499bf0d2ff29b227aa.png
[20200207152559955.png_pic_center]: https://img-blog.csdnimg.cn/20200207152559955.png#pic_center