N的阶乘末尾有多少个零

2024-06-22 22:18
文章标签 阶乘 末尾

本文主要是介绍N的阶乘末尾有多少个零，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题：N的阶乘(N!)中的末尾有多少个0?
例如:N = 5,N! = 120.末尾有1个0.
分析:想到这个问题，有人可能第一反应就是现求出N!,然后再根据求出的结果，最后得出N!的末尾有多少个0。但是转念一想，会不会溢出，等等。

其实，从"那些数相乘可以得到10"这个角度，问题就变得比较的简单了。
首先考虑，如果N的阶乘为K和10的M次方的乘积，那么N!末尾就有M的0。如果将N的阶乘分解后，那么
N的阶乘可以分解为： 2的X次方，3的Y次方，4的5次Z方，.....的成绩。由于10 = 2 * 5,所以M只能和X和Z有关，每一对2和5相乘就可以得到一个10，于是M = MIN(X,Z),不难看出X大于Z，因为被2整除的频率比被5整除的频率高的多。所以可以把公式简化为M=Z.
由上面的分析可以看出，只要计算处Z的值，就可以得到N!末尾0的个数

方法一
要计算Z，最直接的方法就是求出N的阶乘的所有因式(1,2,3,...,N)分解中5的指数。然后求和

int fun1(int n)
{
    int num = 0;
    int i,j;
    
    for (i = 5;i <= n;i += 5)
    {
        j = i;
        while (j % 5 == 0)
        {
            num++;
            j /= 5;
        }
    }
    
    return num;
}




方法二：

Z = N/5 + N /(5*5) + N/(5*5*5).....知道N/(5的K次方)等于0

公式中 N/5表示不大于N的数中能被5整除的数贡献一个5，N/(5*5)表示不大于N的数中能被25整除的数再共享一个5.......




int fun2(int n)
{
    int num = 0;
    
    while(n)
    {
        num += n / 5;
        n = n / 5;
    }
    
    return num;
}


这篇关于N的阶乘末尾有多少个零的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1085565。

相关文章

CGFloat转NSString保持原有的精度，末尾不添加0

CGFloat转NSString保持原有的精度，末尾不添加0

问题阐述： 我们进行CGFloat转NSString可能会遇到一个问题 例如有一个CGFloat的值为2.1，转化成NSString后显示2.1000... 解决办法： 方法一： 如何解决呢，可以使用%g格式符，可以保证传入的不管是2还是2.1都能保持原有的精度 %g格式符可以根据数值的大小自动选择最合适的表示方法，同时避免多余的小数位数。这将确保输入的 2.1 在转换后输出仍然是 2
阅读更多...
Golang | Leetcode Golang题解之第172题阶乘后的零

Golang | Leetcode Golang题解之第172题阶乘后的零

题目： 题解： func trailingZeroes(n int) (ans int) {for n > 0 {n /= 5ans += n}return}
阅读更多...
C语言 | Leetcode C语言题解之第172题阶乘后的零

C语言 | Leetcode C语言题解之第172题阶乘后的零

题目： 题解： int trailingZeroes(int n) {int ans = 0;while (n) {n /= 5;ans += n;}return ans;}
阅读更多...
再来一种求大数阶乘的方法

再来一种求大数阶乘的方法

过多的我就不说了，直接看看代码： java版的： /*** */package Factorial;/*** @author 牟尼（昵称）* @blog：http://blog.csdn.net/u012027907**/public class Factorial {/** 大数阶乘计算类*//** 分析：大数阶乘用数组来存储，如5的阶乘可存在数组cal[]中，表示为* 0
阅读更多...
有关阶乘的两个问题

有关阶乘的两个问题

//(方法一、判定5的个数O(Nlog(5)N))给定一个非负整数N,返回N!结果的末尾为0的数量public static int getZero(int n){if(n<0){return 0;}int res=0;int cur=0;for(int i=5;i<n+1;i+=5){cur=i;while(cur%5==0) //计算有多少个5组成{res++;cur/=5;}}retu
阅读更多...
数据结构之递归小练习（定义，阶乘，求和，汉诺塔）

数据结构之递归小练习（定义，阶乘，求和，汉诺塔）

递归定义；程序直接或间接调用自己，叫做递归。 成为递归的条件：1.要操作的数据规模一直减小，一般而言就是解决n问题必须解决n-1的问题2.必须有一个明确的终止条件。3.每一次的操作都相同，当前的数据和n-1个数据的关系都相同。 小例子： 1.用递归的思想求阶乘： #include<stdio.h> long fn(int n); int main() {     int r;
阅读更多...
计算阶乘n!末尾0的个数

计算阶乘n!末尾0的个数

一、问题描述 给定一个正整数n，请计算n的阶乘n！末尾所含有“0”的个数。例如： 5！=120，其末尾所含有的“0”的个数为1； 10！= 3628800，其末尾所含有的“0”的个数为2； 20！= 2432902008176640000，其末尾所含有的“0”的个数为4。 二、算法分析 此类问题很显然属于数学问题，一定要找到其中的本质规律才能得到正确的数学模型。   两个大数字
阅读更多...
头歌资源库（5）求阶乘问题

头歌资源库（5）求阶乘问题

一、 问题描述          请输入一个50至100之间的整数n，求解n!  二、算法思想  输入一个50至100之间的整数n。声明一个变量result，并将其初始化为1，用于保存n的阶乘。使用一个循环，从1到n，循环变量为i。在循环中，将result与i相乘，将结果保存到result中。循环结束后，result即为n的阶乘。输出result作为n的阶乘的结果。 三、
阅读更多...
python计算给定数字或者数组的阶乘

python计算给定数字或者数组的阶乘

今天做毕业设计的时候遇到了一个级数展开式，里面包含着一个求一个数组的阶乘运算，这里特来记录一下。 # -*- coding:utf-8 -*-"""author: 15025time: 2021/7/18 17:58software: PyCharmDescription:calculate factorial of a given number"""class PythonStudy
阅读更多...
编程之美3——N!末尾有多少个0

编程之美3——N!末尾有多少个0

因为n!是一个非常大的数，所以不能通过常规的方法，求出n!的值之后，再判断它的末尾有多少个0. 这里的关键就是，n!的末尾有多少个0，取决于n!中，质因数 5 的个数。 如：12!=479001600    ，其中，5、10各含有1个质因数5，所以12!末尾有2个0 代码1: #include <iostream>using namespace std;
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2