趣味 C 程序：兩種方法繪製楊輝三角（迭代法與遞歸法）

楊輝三角生成雙解法：迭代數組翻滾 vs 遞歸組合數公式

楊輝三角（Pascal's Triangle）是二項式系數的幾何排列，第 n 行第 k 個數 (0-based) 為 C(n,k)。本文展示兩種 C 語言實現：
1. **迭代雙數組翻滾** —— O(n²) 時間，O(n) 空間，適合打印前 N 行。
2. **遞歸組合數公式** —— 直接計算 C(n,k)，代碼極短但重複計算多，適合單點查詢。

方法一：迭代雙數組（推薦打印全三角）

#include 
#include 

int main() {
    int rows;
    printf("請輸入行數：");
    scanf("%d", &rows);

    int *prev = calloc(rows, sizeof(int));
    int *curr = calloc(rows, sizeof(int));
    prev[0] = 1;

    for (int i = 0; i < rows; i++) {
        // 打印前導空格對齊
        for (int s = 0; s < rows - i - 1; s++) printf("   ");

        curr[0] = 1;
        for (int j = 1; j <= i; j++)
            curr[j] = prev[j-1] + prev[j]; // 核心遞推

        for (int j = 0; j <= i; j++)
            printf("%-4d", curr[j]); // 左對齊 4 寬度

        printf("\n");
        int *tmp = prev; prev = curr; curr = tmp; // 指針交換，無需拷貝
    }
    free(prev); free(curr);
    return 0;
}

輸出示例 (rows=6)：

               1
            1   1
         1   2   1
      1   3   3   1
   1   4   6   4   1
1   5   10  10  5   1

方法二：遞歸組合數（教學演示組合數性質）

#include 

int C(int n, int k) { // 組合數 C(n,k)
    if (k == 0 || k == n) return 1;
    return C(n-1, k-1) + C(n-1, k); // 遞歸定義
}

int main() {
    int n;
    printf("N="); scanf("%d", &n);
    for (int i = 0; i <= n; i++) {
        for (int s = 0; s < n - i; s++) printf("  ");
        for (int k = 0; k <= i; k++)
            printf("%-4d", C(i, k));
        printf("\n");
    }
    return 0;
}

性能警告： 遞歸版重複計算極多，`n>13` 明顯卡頓，`n>20` 棧溢出風險。實際生產**禁止使用**，僅作數學定義演示。

數學性質速查

• 第 n 行有 n+1 個數（0-based 行號）。
• 兩邊恒為 1：`C(n,0) = C(n,n) = 1`。
• 內部元素：`C(n,k) = C(n-1,k-1) + C(n-1,k)`。
• 行和為 2ⁿ：`Σ C(n,k) = 2^n`。
• 對稱性：`C(n,k) = C(n,n-k)`。

工程優化方向

1. 單數組逆序更新：`for (j=i; j>0; j--) a[j] += a[j-1];` 省去雙數組交換。
2. 大數支持：用字符串/大整數庫存儲 C(100,50) 等超長整數。
3. 格式化輸出：動態計算最大數字寬度，自動調整列距。