c++ - 這個高精度階乘運算的原理是什麼啊？

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

想寫給註解幫自己懂 寫到一半寫不下去 for中間三行為什麼那麼寫啊？

Answer 1

好像就是普通的垂直運算乘法吧，沒啥好說的

Answer 2

雷雷

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位。