循環賽日程表生成算法：分治遞歸 Java 實現

問題描述

給定 n（隊伍數為 2^n），生成循環賽日程表，使每隊與其餘所有隊恰好交手一次。經典解法採用分治遞歸構造 2^n × 2^n 矩陣。

算法核心思想

1. 基礎情況：n=1 時，2 隊交手，矩陣為 [[1,2],[2,1]]。
2. 遞歸構造：將 n-1 階矩陣複製到左上、右上、左下、右下四個象限，右上象限元素加 2^(n-1)，最後對整個矩陣做鏡像翻轉（上下、左右），保證對稱性與無重複對戰。
3. 時間複雜度：O(4^n)，空間複雜度同階，適合 n ≤ 6（64 隊）以內場景。

完整 Java 代碼

public class RoundRobinSchedule {

    public static int[][] generate(int n) {
        int size = 1 << n;  // 2^n
        int[][] table = new int[size][size];

        if (n == 1) {
            table[0][0] = 1; table[0][1] = 2;
            table[1][0] = 2; table[1][1] = 1;
            return table;
        }

        // 遞歸獲取 n-1 階子表
        int[][] sub = generate(n - 1);
        int half = sub.length;
        int offset = 1 << (n - 1);  // 2^(n-1)

        // 1. 複製左上、右上（+offset）
        for (int i = 0; i < half; i++) {
            for (int j = 0; j < half; j++) {
                table[i][j] = sub[i][j];
                table[i][j + half] = sub[i][j] + offset;
            }
        }

        // 2. 鏡像生成下半部分（上下翻轉 + 左右翻轉）
        for (int i = 0; i < half; i++) {
            for (int j = 0; j < size; j++) {
                table[size - 1 - i][size - 1 - j] = table[i][j];
            }
        }
        return table;
    }

    // 測試主函數
    public static void main(String[] args) {
        int n = 3;  // 8 隊
        int[][] schedule = generate(n);
        for (int[] row : schedule) {
            for (int v : row) System.out.printf("%3d", v);
            System.out.println();
        }
    }
}

代碼關鍵點註解

• 1 << n 利用位運算快速計算 2^n，比 Math.pow 更高效且無浮點誤差。
• 鏡像賦值 table[size-1-i][size-1-j] = table[i][j] 一次性完成上下左右翻轉，巧妙滿足循環賽對稱性要求。
• 遞歸出口 n==1 直接硬編碼 2×2 矩陣，避免過度遞歸開銷。

擴展應用

若需輸出具體輪次對陣列表，可遍歷矩陣上三角區（i < j），table[i][j] 即為第 j 輪第 i 場比賽的對手編號。結合隊伍名稱映射表，即可生成可讀性強的賽程表。

總結

分治遞歸利用矩陣自我相似性，以極簡代碼解決循環賽日程生成問題。理解「複製→偏移→鏡像」三步驟，即可舉一反三應用於其他對稱矩陣構造任務。