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

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

一、问题描述

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

二、算法分析

此类问题很显然属于数学问题，一定要找到其中的本质规律才能得到正确的数学模型。

  两个大数字相乘，都可以拆分成多个质数相乘，而质数相乘结果尾数为0的，只可能是2*5。如果想到了这一点，那么就可以进一步想到：两个数相乘尾数0的个数其实就是依赖于2和5因子的个数。又因为每两个连续数字就会有一个因子2，个数非常充足，所以此时只需要关心5因子的个数就行了。

　　对于一个正整数n来说，怎么计算n！中5因子的个数呢？我们可以把5的倍数都挑出来，即：

　　令n! = (5*K) * (5*(K-1)) * (5*(K-2)) * … * 5 * A，其中A就是不含5因子的数相乘结果，n = 5*K + r（0<= r <= 4）。假设f(n!)是计算阶乘n!尾数0的个数，而g(n!)是计算n!中5因子的个数，那么就会有如下公式：

$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

三、代码实现

　　使用递归函数来做，非常的简单，直接套用公式即可：

#include <iostream>
using namespace std;int GetN_1(int n)
{if (n < 5){return 0;}else{return (n / 5 + GetN_1(n / 5));}
}int main()
{cout << GetN_1(1000) << endl;　　// 输出249system("pause");return 0;
}

非递归方式，很快（虽然递归也不是慢，因为递归的次数太少了）

#include <iostream>
using namespace std;
int main() {int n, ans = 0;cin >> n;while (n) {ans += n/=5;}cout << ans << endl;return 0;
}

这篇关于计算阶乘n!末尾0的个数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---