题解 | N的阶乘

#include <iostream>
using namespace std;

// long long int temp(int x){
//     if(x == 1){
//         return 1;
//     }
//     return x * temp(x-1);
// }

int compute(int x, int *ans);

int main() {

    int n;
    while(cin >> n){
        // 由于longlongint存不下，故用数组来存储
        int ans[3000] = {0}; // 由题知N最大为1000，1000!位数约为2568位

        // 实行函数，并记录返回的实际位数的长度
        int len = compute(n, ans);

        // 反向输出
        for(int i = len; i >= 1; --i){
            cout << ans[i];
        }
        cout << endl;

        
    }
}

int compute(int n, int *ans){

    int len = 1; //设置初始长度为1
    
    ans[1] = 1; // 令第1位为1，无数学意义，仅方便下面for循环规律的代码

    // 开始阶乘计算，数组从左往右存位数从低到高（即与直觉相反）
    for(int i = 2; i <= n; ++i){
        // 两个一位数相乘，结果最多为2位数，取个位数加到当前位，十位数进到下一位

        // PS: 为何要单独开一个进位？
        // —— 保留上一次乘法的进位。因为要等到当前位乘法结算以后，才能加上上次的进位（符合我们手算的先后次序，之前debug发现就是这儿错了!!!）
        // 记录进位
        int record = 0;

        // 模仿人类做乘法运算的逻辑
        // 遍历当前ans[]的每一位
        for(int j = 1; j <= len; ++j){
            // 设立一个变量记录这次乘法的值（记得加上之前可能的进位）
            int temp = ans[j] * i + record; 
            
            record = temp / 10;// 记录除尾数后的进位(十位及以上)

            // 再修改当前位，当前位=相乘过后的尾数+上一位的进位数
            ans[j] = temp % 10;

        }

        // 若最终产生了结果长度变长，记录长度len++（要考虑多位数的情况（如：9*9是2位，9*99是3位）
        while(record){
            len++;
            ans[len] = record % 10;
            record /= 10;
        }

    }

    return len;
}