C語言實現楊輝三角：數學規律與高效演算法

楊輝三角數學規律

第 n 行（從 1 計）有 n 個數。首尾為 1，中間每個數等於上一行同位置與前一位置之和。組合數公式：C(n-1, k-1)（k=1..n）。遞推關係：C(n, k) = C(n, k-1) * (n-k+1) / k。

高效列印演算法（O(n²) 時間，O(1) 額外空間）

#include <stdio.h>

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

    for (int i = 1; i <= n; i++) {
        long val = 1;  // 使用 long 防止中間溢位
        for (int j = 1; j <= i; j++) {
            printf("%ld ", val);
            val = val * (i - j) / j;  // 遞推計算下一個組合數
        }
        printf("\n");
    }
    return 0;
}

關鍵點解析

• val 初始為 1（首項 C(i-1, 0)）
• 每輪更新：val = val * (i - j) / j 對應 C(i-1, j) = C(i-1, j-1) * (i-j) / j
• 整數除法精確，因組合數必為整數
• 避免階乘運算與大數溢位，效率極高

執行示例（n=6）

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

進階考量

• 大數處理： 行數超過 20 時 long 會溢位，需用大整數庫或字串模擬加法。
• 對齊列印： 計算最大值寬度，配合 printf("%*ld", width, val) 實現等寬對齊三角形狀。
• 遞迴實現： 教學用可用遞迴 C(n,k)=C(n-1,k-1)+C(n-1,k)，但效率極低（重複計算），不建議實務使用。