高精度阶乘（包括阶乘的加减）

偏执的太偏执、 2023-07-15 02:54 133阅读 0赞

### 高精度阶乘（包括阶乘的加减） ###

*   *  高精度求阶乘
     *   *   *  求n的阶乘
             *  阶乘优化：
             *  求阶乘和：
             *  求俩数的阶乘和

关于高精度，如果不甚了解，可以先看看我的另一篇博客  
[高精度的加减乘除全解][Link 1]  
大概懂点路子之后，我们一起来看看下面的应用

## 高精度求阶乘 ##

#### 求n的阶乘 ####

这一块比较简单，在看过之前的博客之后，这里的些许代码注释应该足以明白代码实现，我就不赘述了。  
可能新手不能理解while循环里的那几句（理解的可以跳过这一段，可以思考一下如何优化解法），我稍微解释一下：  
为啥保留c的副本？

> 因为无论我们是先求该位目前保留的数（取余运算），还是先更新进位（除法运算），其中a\[j\]和c都是在两句代码中需要用到的，所以我们需要把其中一个保留副本（这里我是把进位保留了副本，看起来简洁些）。

为啥要有循环？

> 肯定得有这个循环呀！因为我们的数组中的元素是存储每一位的呀，而俩数相乘是其中一个数的每一位乘以另一个数呀，所以每一趟其实是把每一位乘以阶乘公式的某个因数i（因数的遍历由外循环中的i搞定）。

#include <iostream>
    #include <cstdio>
    #include <string>
    #include <string.h>
    #include <algorithm>
    #include <cstring>
    const int length = 100000;
    
    using namespace std;
    
    int main()
    {
        
        int a[length];  //定义一个数组来存储结果
        for(int i = 1; i < length; i++){
        
            a[i] = 0;
        }
        a[0] = 1;
        long long int n;
        while(~scanf("%lld",&n)){
        
            for(int i = 2; i <= n; i++){
        
                int c = 0;  //存储进位
                int j = 0;
                int temp;  //存储进位的副本
                while(j < length){
        //我感觉有很大的优化空间
                    temp = c;
                    c = (a[j]*i + c) / 10;
                    a[j] = (a[j]*i + temp) % 10;
                    j++;
                }
            }
            int k = length - 1;
            while(!a[k]){
        
                k--;  //高位的（数组后面的）0跳过，不输出
            }
            while( k >= 0){
        
                cout<< a[k];
                k--;
            }
        }
        return 0;
    }

#### 阶乘优化： ####

上述代码每次都要把数组的每个元素都乘一遍，而我们很清楚的知道后面的很多乘法是多余的，如果想要理解此处的优化思路，可以看看我的另一篇文章，通过vector中方法的实现与优化理解如何思考降低复杂度  
[培养优化的思维][Link 2]  
看过文章后，不难知道，这里只需计算1次，2次，…，n-1次；在二维平面里构成一个三角形，而冗余的恰恰是与子对称的n-1次，n-2次,…,1次运算；所以通过算术级数我们知道明明是nlogn的算法，我们活活把它写成了n^2的算法，那么  
有什么办法能优化它呢？

> 每次循环里我们只需要让结果的最高位有所放置就行，后面的暂不需计算；那么一个乘法的结果的最高位是多少呢？或者更清楚点，在每一次外层i的循环中我们要计算的i！的最大涉及到多少位？注意：这里我们不关心最大多大，只关心它有几位！  
> （当然大佬们可以尝试压位，ps我还不会，如果大佬解决可以私信给我，和我交流，谢谢指教！）

我们来考虑最简单的思路：  
一个数 i 的阶乘是 i! = 10m ,那么我们这里关心的是m有多大，高中数学就oK能解了，m >= log10 (n!) = lgn+lg(n-1)+…+lg1 。

int f(int i)
    {
        //求解m
        double a=0.0;
        while(i)
        {
        
            a+=log10(i);
            i--;
        }
        int m = (int) + 1;
        return m;
    }

得到位数的好处是，不用事先定义一个大数组，而是需要多少位就分配多大的数组（堆分配），这是解决**空间**的问题。  
接着，再想着**时间**的问题，假如定义100个元素的数组，每次代码都要从数组的首位一直到末位乘以一个数，假如算到5！=120的时候，数组存储的情况是：  
0　　2　　1　　0　　0　　0　　0　　0　　0…  
现在又要这个数组每位再乘以6，则右边是一连串的0，还有必要再依次乘一遍吗？当然没必要，我们平时手算的时候只数0的个数，而不会带着长长的零，对吧？那么，  
如何实现优化呢？  
如果看来我上面那个vector的链接，应该不难有这样的思路（所以说我觉得**数据结构与算法这门课教会了我们的是思想，很多很有用的思想！**）  
如果把已经得到结果的最末位数做一个监视哨flag，每次循环乘数只要乘到这个监视哨就结束，就可以解决这个问题！

> flag作为监视哨，必定指向每次运算之后的结果的最末位。假如现在j又要乘以6，从第一位0开始，一直移位到监视哨。即：j<=flag。  
> 第二种情况，假如在监视位出现进位了，依然还要继续乘下去，于是，得到另一个条件：f>0，只要有进位也要继续往下乘。  
> 第三种情况：假如现在结果已经是0　　2　　7，（720），再乘以7之后，得到：  
> 0　　4　　0　　5，由于flag现在还指向第三位，所以要把位置提到末位，也就是说，每次循环完成之后，还要提升监视哨的位置.  
> 到此，问题算是解决了！ 这个模型相当于，如何在数组的循环运算中截断到某个位置！（主要判定监视哨的位置和中止的条件）

/*算法改进，效率提升很多！*/
    #include <iostream>
    using namespace std;
    #define max 30000
    int a[max];
    int main()
    {
        
        int n,x;
        cin>>n;
        a[0]=1;
    
        for(int i=2,flag=0;i<=n;i++)/*监视哨初始指向数组首位*/
        {
        
            for(int f=0,j=0;j<=flag || f>0;j++)/*j未到监视哨，或者有进位*/
            {
        
                x=a[j]*i+f;
                f=x/10;/*进位*/
                a[j]=x%10;
            }
            while(a[j]==0)/*提升监视哨的位置,j有两种可能的位置*/
            j--;
            flag=j;
        }
        while(flag>=0) /*输出结果*/
        {
                
        cout<<a[flag];
        flag--;
        }    
        return 0;
    }

#### 求阶乘和： ####

> 问题 I: 【高精度】阶乘和 时间限制: 1 Sec 内存限制: 64 MB 提交: 4 解决: 4 \[提交\] \[状态\] \[讨论版\]  
> \[命题人:外部导入\] 题目描述  
> 已知正整数N(N≤200)，设S=1!+2!+3!+…N!，其中“!”表示阶乘，即N!=1×2×3×…×(N-l)×N，如：3  
> 1=1×2×3…6。请编程实现：输入正整数N，计算结果S的值。 输入 一个正整数N(N≤200)。 输出 阶乘和。 样例输入 4  
> 样例输出 33

阶乘和求和分别放在两个数组里，每个数求阶乘时每循环一次都要判断是否要进位，每个数本身的阶乘求好就先求一下和，也要注意进位。  
最后注意如果测试多组数据，数组要清零。

#include <iostream>
    #include<string>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    int nn,a[100005],b[100005];
    string fun_plus(string s,string t)
    {
        
        string res;
        int len_s=s.size(),len_t=t.size();
        int len=max(len_s,len_t);
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(int i=len_s-1;i>=0;i--) a[len_s-i-1]=s[i]-'0';
        for(int i=len_t-1;i>=0;i--) b[len_t-i-1]=t[i]-'0';
        for(int i=0;i<len;i++)
        {
        
            a[i]+=b[i];
            a[i+1]+=a[i]/10;
            a[i]%=10;
        }
        while(a[len]==0)    len--;
        for(int i=len;i>=0;i--)   res+=a[i]+'0';
        return res;
    }
    string fun_multi(int n)
    {
        
        string res;
        if(n==0)    return "1";
        memset(a,0,sizeof(a));
        int cnt=0,m=n;
        while(m)    a[cnt++]=m%10,m/=10;
        for(int i=n-1;i>=2;i--)
        {
        
            int w=0;
            for(int j=0;j<cnt;j++)
            {
        
                a[j]=a[j]*i+w;
                w=a[j]/10;//此处顺序不能改变
                a[j]%=10;
            }
            while(w)
            {
        
                a[cnt++]=w%10;
                w/=10;
            }
        }
        while(!a[cnt])  cnt--;
        for(int i=cnt;i>=0;i--)
            res+=a[i]+'0';
        return res;
    }
    int main()
    {
        
        cin>>nn;
        string ans,temp;
        for(int i=1;i<=nn;i++)
        {
        
            temp=fun_multi(i);
            ans=fun_plus(temp,ans);
        }
        cout<<ans<<endl;
        return 0;
    }

参考下面大佬的实现：（已经无法出处了，就没有注明哪位大佬，但万分感谢呀）

#include<iostream>
    
    #include<cstdio>
    
    using namespace std;
    
    const int maxn=10000;
    
    int main()
    
    {
        
    
        int n,k,i,j,t;
    
        while(cin>>n){
        
    
            int a[maxn]={
        },sum[maxn]={
        };
    
            sum[0]=0;
    
            k=1,t=1;
    
            for(int e=1;e<=n;e++){
        
    
                a[0]=1;
    
                for(i=1;i<=e;i++){
        
    
                    for(j=0;j<k;j++){
            
    
                        a[j]=a[j]*i;        
    
                    }
    
                    for(j=0;j<k;j++){
        
    
                        if(a[j]>=10){
        
    
                            a[j+1]+=a[j]/10;
    
                            a[j]=a[j]%10;
    
                            if(j==k-1) k++; 
    
                             
    
                        }       
    
                    }
    
                }
    
                for(int p=0;p<k;p++){
        
    
                    sum[p]=sum[p]+a[p];
    
                }   
    
                for(int p=0;p<t;p++){
        
    
                    if(sum[p+1]>=10){
        
    
                        t++;
    
                    }
    
                    if(sum[p]>=10){
        
    
                        sum[p+1]+=sum[p]/10;
    
                        sum[p]=sum[p]%10;
    
                    }       
    
                }
    
                for(int q=1;q<k;q++){
        
    
                    a[q]=0;
    
                }
    
            }
    
            for(i=k-1;i>=0;i--){
        
    
                cout<<sum[i]<<"";
    
            }
    
            cout<<endl;
    
        }
    
    }

#### 求俩数的阶乘和 ####

这题是我们的检测题，哈哈哈！

> 我们知道一般int类型是32位存储，表示的有符号整数数据范围是-231 ~ 231 - 1，而长整数类型可以是64位存储，表示的数据范围是  
> \-263~263 - 1。而计算21!就将超出64位长整数的范围。 请编写程序，实现任意多位整数的四则运算。并以计算n!-m!进行验证。 ★数据输入  
> 输入数据只有一行，两个数字n 和m（0<=m<=n<=100）。 ★数据输出  
> 输出n!-m!的结果 例如： 输入示例 10 5 输出示例 3628680
> 
> 例如: 测试 输入 Result 1 10 5 3628680 2 22 0 1124000727777607679999

[Link 1]: https://blog.csdn.net/qq_16497423/article/details/104064550
[Link 2]: https://blog.csdn.net/qq_16497423/article/details/104857096