高精度计算N!

淡淡的烟草味﹌ 2022-06-16 14:18 302阅读 0赞

计算N的阶乘，应用高精度计算，追求一题多解！（N<10000）

由于N是小于10000的，可以输入，则选择用INT型的大数即可，用数值型的高精度。

方法一：

#include <iostream>
    #include <cmath>
    #include <cstring>
    
    using namespace std;
    
    
    int main()
    {
        const int maxn=50000;
        int n,c,k;
        int f[maxn+1];
    
        while(cin>>n)
        {
            memset(f,0,sizeof(f));
            f[0]=1;
            for(int i=1; i<=n; i++)
            {
                c=0;//代表进位
                for(int j=0; j<=maxn; j++)
                {
                    int s=f[j]*i+c;
                    f[j]=s%10;
                    c=s/10;
                }
            }
            for(k=maxn; k>=0; k--)
                if (f[k]!=0) break;
            for(int j=k; j>=0; j--)
                cout<<f[j];
            cout<<endl;
        }
        return 0;
    }

可以把时间缩短为原来的一半的方法二：

在每一位上都存储一个五位数，采用同样的方法进行进位，只是在输出时需要注意即可。

#include <iostream>
    #include <cmath>
    #include <cstring>
    #include <cstdio>
    
    using namespace std;
    
    
    int main()
    {
        const int maxn=20000;
        int n,c,k;
        int f[maxn+1];
        while(cin>>n)
        {
            memset(f,0,sizeof(f));
            f[0]=1;
            for(int i=1; i<=n; i++)
            {
                c=0;//代表进位
                for(int j=0; j<=maxn; j++)
                {
                    int s=f[j]*i+c;
                    f[j]=s%100000;
                    c=s/100000;
                }
            }
            for(k=maxn; k>=0; k--)
                if (f[k]!=0) break;
            cout<<f[k];
            for(int j=k-1; j>=0; j--)
                printf("%05d",f[j]);
            cout<<endl;
        }
        return 0;
    }

速度更快的方法三：

每一次都记录当前数组中的结果的位数，可以使速度更快。

#include <iostream>
    #include <cmath>
    #include <cstring>
    #include <cstdio>
    
    using namespace std;
    
    
    int main()
    {
        const int maxn=50000;
        int n,c,k;
        int f[maxn+1];
        double wei;
        while(cin>>n)
        {
            wei=0;
            memset(f,0,sizeof(f));
            f[0]=1;
            for(int i=1; i<=n; i++)
            {
                c=0;//代表进位
                wei+=log10(i);
                int t=((int)wei+1)/5;
                for(int j=0; j<=t; j++) //控制计算次数
                {
                    int s=f[j]*i+c;
                    f[j]=s%100000;
                    c=s/100000;
                }
            }
            for(k=wei; k>=0; k--)
                if (f[k]!=0) break;
            cout<<f[k];
            for(int j=k-1; j>=0; j--)
                printf("%05d",f[j]);
            cout<<endl;
        }
        return 0;
    }