HDU 2032 楊輝三角 組合數計算

題目

輸出 n 行（n≤30）楊輝三角，每行數字空格分隔，每個三角形後空一行。

數學性質

第 i 行第 j 個數（0-based）為組合數 C(i, j)。利用遞推 C(n,k) = C(n-1,k-1) + C(n-1,k) 或直接計算 C(n,k) = n!/(k!(n-k)!)。

遞推法（推薦，無溢出風險）

#include <cstdio>
#include <vector>
using namespace std;

int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        vector<vector<long long>> tri(n);
        for (int i = 0; i < n; ++i) {
            tri[i].resize(i+1);
            tri[i][0] = tri[i][i] = 1;
            for (int j = 1; j < i; ++j)
                tri[i][j] = tri[i-1][j-1] + tri[i-1][j];
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= i; ++j) {
                if (j) printf(" ");
                printf("%lld", tri[i][j]);
            }
            printf("\n");
        }
        printf("\n");
    }
    return 0;
}

組合數直接計算法（原代碼思路）

利用 C(n,k) = Π_{i=1..k} (n-k+i)/i，邊乘邊除防溢出：

long long C(int n, int k) {
    if (k > n-k) k = n-k;
    long long res = 1;
    for (int i = 1; i <= k; ++i) {
        res = res * (n - k + i) / i; // 整除保證無餘數
    }
    return res;
}

複雜度

• 遞推法：O(n²) 時間，O(n²) 空間（可優化至 O(n) 滾動數組）
• n≤30 時長整型足夠（C(30,15) ≈ 1.5e8）