《算法競賽入門經典》5.22 階乘精確值計算：大數乘法的 C 語言實現詳解

前言：為什麼需要高精度階乘？

在算法競賽與實際開發中，階乘增長極快。13! 已超過 32 位整數範圍，21! 突破 64 位長整數。若輸入 n ≤ 1000，結果將擁有超過 2500 位數字，遠超任何基本類型容量。本文詳細解析《算法競賽入門經典》第 5.22 題——利用「數組模擬手算乘法」求解 n! 精確值的經典算法。

題目回顧

輸入不超過 1000 的正整數 n，輸出 n! = 1×2×3×…×n 的精確結果。
樣例輸入：30
樣例輸出：265252859812191058636308480000000

核心思路：數組模擬豎式乘法

將大整數拆解為個位、十位、百位……分別存入數組 f[0]、f[1]、f[2]…，低位在前、高位在後，完全模擬手算「逐位相乘、進位」的過程。

• 空間估算：1000! ≈ 4×10²⁵⁶⁷，約 2568 位，開 maxn = 3000 足夠。
• 初始化：f[0] = 1 代表 1!，其餘為 0。
• 主循環：對 i = 2 … n，將當前數組代表的大整數乘以 i。
• 進位處理：s = f[j] * i + c; f[j] = s % 10; c = s / 10;
• 輸出：從最高非零位逆序列印。

完整代碼（含詳細註釋）

/* 
 * 算法競賽入門經典 5.22 階乘精確值
 * 數組模擬高精度乘法
 */
#include <stdio.h>
#include <string.h>

#define MAXN 3000          // 1000! 約 2568 位，3000 綽綽有餘
int f[MAXN];               // f[0] 存個位，f[1] 存十位……

int main() {
    int i, j, n;
    scanf("%d", &n);

    memset(f, 0, sizeof(f));
    f[0] = 1;              // 1! = 1

    for (i = 2; i <= n; i++) {      // 從 2! 累乘到 n!
        int c = 0;                   // 進位
        for (j = 0; j < MAXN; j++) { // 低位→高位逐位相乘
            int s = f[j] * i + c;
            f[j] = s % 10;           // 當前位
            c = s / 10;              // 新進位
        }
    }

    // 跳過前導 0
    for (j = MAXN - 1; j >= 0; j--) if (f[j]) break;
    // 逆序輸出
    for (i = j; i >= 0; i--) printf("%d", f[i]);
    printf("\n");
    return 0;
}

關鍵細節深度解析

1. #define vs const：為何選宏？

• #define MAXN 3000 只是編譯期文本替換，不佔用運行時內存，無類型，適合作為數組長度常量。
• const int MAXN = 3000; 有類型、有地址、佔用數據段，某些老舊編譯器不允許作為數組長度。

2. 進位邏輯演示（以 5! 為例）

3. 前導 0 處理

因 n! (n≥1) 必不為 0，直接從高位向低掃描首個非零元素即可；若輸入可能為 0，需單獨處理 0! = 1。

複雜度分析

• 時間：O(n × maxn) ≈ 3×10⁶ 次操作，極快。
• 空間：O(maxn) = 3000 int ≈ 12 KB。

常見坑點與優化建議

1. 數組大小不足：1000! 實際 2568 位，建議留 20% 餘量。
2. 進位未清零：每輪外層循環開始前必須 c = 0。
3. 輸出格式：不得有空格、換行，僅輸出數字串。
4. 優化方向：可改用 base = 10⁴ 或 10⁹ 壓縮數組長度，減少循環次數。

延伸練習

• POJ 1014 / HDOJ 1024 類似高精度題目
• 實現大整數加減乘除通用庫
• 嘗試遞歸 + 分治優化階乘（如 Prime Swing 算法）

掌握「數組模擬手算」是解決所有高精度問題的基石，建議反覆手寫直到肌肉記憶形成。