c++ - Quel est le principe de cette opération factorielle de haute précision?

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;
}

Je veux écrire un commentaire pour m'aider à comprendre, mais je ne peux pas continuer à écrire à mi-chemin. Pourquoi les trois lignes au milieu de for sont-elles écrites comme ça ?

Answer 1

Cela semble être juste un calcul vertical ordinaire de multiplication, il n'y a pas grand chose à dire

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

Étant donné que la multiplication dépassera int ou même long long, une haute précision est requise.
L'idée de la haute précision est d'utiliser un tableau pour stocker chaque chiffre du nombre, puis de simuler la méthode de multiplication verticale du calcul humain de multiplication.
Vous pouvez réfléchir à la façon de calculer un tableau a de longueur n fois un nombre x, en supposant que a est stocké de bas en haut (par exemple, le nombre 12345, le tableau est a[1]=5,a[2]= 4,une [3]=3,une[4]=2,une[5]=1).
Tout d'abord, tout le monde est a[1]x%10, mais quel est le chiffre des dizaines ? Il devrait être (a[2]x+report du chiffre précédent)%10
Donc ici, c représente le report du chiffre précédent, f[j] représente le j-ème bit de (i-1)! avant de boucler sur j, et après avoir bouclé sur j, il représente le j-ème bit de i!.