POJ 2084 Game of Connections：卡特蘭數遞推與 Java 大整數實現

POJ 2084 Game of Connections：卡特蘭數遞推與 Java 大整數實現

題目鏈接：POJ 2084

核心洞察：圓周上 2n 個點兩兩連線且線段不相交的方案數，即為第 n 個卡特蘭數（Catalan Number）。

一、 數學模型與遞推關係

定義 h(n) 為 2n 個點合法連線方案數：

• h(0) = 1（空集視為 1 種方案）
• h(1) = 1（2 個點僅 1 條連線）
• h(n) = Σ h(i) * h(n-1-i)，其中 i = 0..n-1，n ≥ 2

等價閉形式：h(n) = C(2n, n) / (n+1) = (2n)! / (n! * (n+1)!)

前幾項：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862... 增長極快，n=200 時已超過 10¹¹⁵，必須用大整數。

二、 Java 實現：打表預計算 + BigInteger

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 1. 預計算 h[0..200]
        BigInteger[] h = new BigInteger[201];
        h[0] = h[1] = BigInteger.ONE;
        for (int n = 2; n <= 200; n++) {
            h[n] = BigInteger.ZERO;
            for (int i = 0; i < n; i++) {
                h[n] = h[n].add(h[i].multiply(h[n - 1 - i]));
            }
        }

        // 2. 讀入多組測試用例，-1 結束
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            if (n == -1) break;
            System.out.println(h[n]);
        }
    }
}

三、 關鍵點解析

四、 優化與變體

• 空間優化：僅需一維數組，無法進一步降維（需歷史所有值）
• 時間優化：利用閉形式 h(n) = h(n-1) * (4n-2) / (n+1) 可降為 O(n) 預計算，但需精確整除，BigInteger 除法較慢，實測遞推更快
• 輸出格式：直接 System.out.println(h[n])，BigInteger 默認十進制無前導零，符合要求

五、 測試用例自驗

輸入：
1
2
3
-1

輸出：
1
2
5

與卡特蘭數序列完全吻合。

此題是「識別模型 → 寫出遞推 → 大整數實現 → 打表優化」的經典練習，適合鞏固組合數學與 Java 高精度計算基本功。