阶乘末尾0的个数

问题很简单:给定一个整数n,那么n的阶乘末尾有多少个连续的0呢?

那个可以去求这个阶乘吗,大数的代码上去一套?这个大数求出来肯定是很慢的,还有其他方法吗,你可以观察一个产生0,本质是2*5,出现了2一定会出现5,2的个数会大于5的个数,所以我可以直接统计5的个数,统计每个数有几个因子5

数学理解:

阶乘中有多少0,如果N!=K*m,K是一个不能被10整除的数,那么m有多少个就有多少个0
N!进行质因数分解N!=(2^x)*(3^y)*(5^z)···,由于只有2*5=10,所以可以看有多少对
2和5,就有多少个0,M=min(x,z),而能被2整除的比能被5整除的多,M=z

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while (cin >> n)
    {
        int num = 0 ,i;
        for(int m=1;m<=n;m++)
        {
            i=m;
            while (i % 5 == 0)
            {
                i=i/5;
                num++;
            }
        }
        cout << num << endl;
    }
}

当然可以直接关注5

 

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

数学表达

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

递归写法

#include <bits/stdc++.h>
using namespace std;
int f(int x)
{
    if(x<5)return 0;
    return f(x/5)+x/5;
}
int main()
{
    int n;
    while (cin >> n)
    {
        cout << f(n) << endl;
    }
}

每隔5*5,会多产生一个0,比如25,50,75,...(这里的5只在上一种情况算了一个5,因此在这里加上25=5*5上次只算了一个5)

每隔5*5*5又会多出一个0,和第二个同理

循环进制

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while (cin >> n)
    {
        int num = 0;
        while (n > 0) {
            num += n / 5;
            n /= 5;
        }
        cout << num << endl;
    }
}

 

原文链接: https://www.cnblogs.com/BobHuang/p/12245428.html

欢迎关注

微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬

    阶乘末尾0的个数

原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/326205

非原创文章文中已经注明原地址,如有侵权,联系删除

关注公众号【高性能架构探索】,第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处!

(0)
上一篇 2023年3月1日 下午3:43
下一篇 2023年3月1日 下午3:43

相关推荐