c++ - Was ist das Prinzip dieser hochpräzisen faktoriellen Operation?

Question

#include <iostream>
#include <string.h>
#include <stdio.h> 
using namespace std;
const int max=3000;
int f[3000];
int main()
{ 
    int i,j,n;
    scanf("%d",&n);
    memset(f,0,sizeof(f));
    f[0]=1;
    for(i=2;i<=n;i++)            //从i乘到n 
    {
        int c=0;
        for(j=0;j<3000;j++)     //每一位在乘法时的调整 
        {
            int s=f[j]*i+c;     
            f[j]=s%10;
            c=s/10;
        }
    }
    for(j=3000-1;j>=0;j--)              
    if(f[j]) break;
    for(i=j;i>=0;i--)
    cout<<f[i];
    
     
        return 0;
}

Ich möchte einen Kommentar schreiben, um mir das Verständnis zu erleichtern, aber ich kann nicht mittendrin weiterschreiben. Warum sind die drei Zeilen in der Mitte so geschrieben?

Answer 1

好像就是普通的竖式计算乘法吧，没啥好说的

Answer 2

#include <iostream>
#include <string.h>
#include <stdio.h> 
using namespace std;
const int maxn = 3000;//3000意指结果最多含3000个数字
int f[maxn];//结果存储器.下标大的元素对应结果的高位.即f[0]对应结果的个位.
//每次运行,f[]的每个元素初始值都是0.
//这里为了便于理解修改成了maxn,且避免与<algorithm>以及<cmath>库中的同名函数重复.
int main()
{ 
    //初始化开始
    int i,j,n;
    scanf("%d",&n);
    f[0]=1;
    //memset(f,0,sizeof(f)); //f声明在main外头,初始值都为0,不需要memset
    //初始化结束

    //开始计算阶乘
    for(i=2;i<=n;i++)//从2乘到n.
    {
        int c=0;//进位存储器.
        for(j=0;j<maxn;j++)//每一位都乘个i.
        {
            int s=f[j]*i+c;//f[j]是当前被乘i的那一位上的数字,"+c"是进位;s的值最大是9*9=81,最小是0,不会超过两位数
            f[j]=s%10;//模10,意在取计算结果个位上的数字,赋值给f[j]
            c=s/10;//除10,意在取十位上数字.
            //若无十位上的数字,则c为0;因为c++中,整型除法向0取整(理解起来等价于舍去小数部分),如9/10=0;
        }
    }
    //计算结束

    //输出开始
    for(j=maxn-1;j>=0;j--)              
        if(f[j]) break;
    for(i=j;i>=0;i--)
        cout<<f[i];
        /*这两句的意思很简单，假设f[]是这样的：(这边是f[2999]->)0000000...(省略若干个0)...00123123123(<-f[0]在这边)
         *先从高位开始往低位找，找到第一个不为零的数字，记下标为j,
         *然后再从j到0依次输出f[]中每一位的值
         */

    //输出结束
    return 0;
}

Answer 3

由于乘法会超过int甚至long long，所以要用高精度。
高精度的思路是用数组来存数字的每一位，然后模拟人计算乘法的竖式乘法方法。
你可以考虑如何计算一个长度为n的数组a乘以一个数x，假设a是从低位到高位存储的（比如数字12345，数组就是a[1]=5,a[2]=4,a[3]=3,a[4]=2,a[5]=1）。
首先各位就是a[1]x%10，但是十位是什么呢，应该是(a[2]x+上一位的进位)%10
所以这里，c表示的就是上一位的进位，f[j]在循环到j之前表示的是(i-1)!的第j位，循环到j后是i!的第j位。