循環賽日程表生成：遞歸構造法

問題描述

給定 2ᵏ 名運動員（k ≥ 1），生成循環賽日程表：每輪每位運動員恰好比賽一次，共 2ᵏ-1 輪，任意兩人僅交手一次。日程表為 2ᵏ × 2ᵏ 矩陣，第 i 行第 j 列表示第 i 輪第 j 場比賽的運動員編號（或按特定規則填充）。

遞歸構造思路

利用分治：2ᵏ 規模問題分解為四個 2ᵏ⁻¹ 子問題。

1. 左上角：遞歸構造 2ᵏ⁻¹ 日程表。
2. 右上角：遞歸構造 2ᵏ⁻¹ 日程表（運動員編號偏移 2ᵏ⁻¹）。
3. 右下角：複製左上角。
4. 左下角：複製右上角。

初始條件：k=1 時，2×2 表為 [[1,2],[2,1]]（或按題目具體定義）。

參考代碼 (C++)

#include 
#include 
#include 
using namespace std;

void copyBlock(int** a, int sr, int sc, int dr, int dc, int k) {
    for (int i = 0; i < k; ++i)
        for (int j = 0; j < k; ++j)
            a[dr+i][dc+j] = a[sr+i][sc+j];
}

void build(int** a, int r, int c, int k) {
    if (k == 1) return;
    int half = k / 2;
    build(a, r, c, half);                 // 左上
    build(a, r, c + half, half);          // 右上
    copyBlock(a, r, c, r + half, c + half, half);     // 左上→右下
    copyBlock(a, r, c + half, r + half, c, half);     // 右上→左下
}

int main() {
    int k; cin >> k;
    int n = k; // 此處 k 為運動員數，需為 2 的冪
    int** table = new int*[n];
    for (int i = 0; i < n; ++i) {
        table[i] = new int[n];
        table[0][i] = table[i][0] = i + 1; // 初始化首行首列
    }
    build(table, 0, 0, n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) cout << table[i][j] << ' ';
        cout << endl;
    }
    return 0;
}

輸出示例 (k=4, 16人)

複雜度

• 時間：O(n²)，n = 2ᵏ，每個單元格填寫常數次。
• 空間：O(n²) 存儲表格。

註記

此構造生成的表格滿足：每行每列為 1~n 的排列，對角線相同，對稱性良好，符合循環賽配對要求。