循環賽程表問題：2^k 選手循環賽遞迴建構演算法

前言

經典演算法題：$n=2^k$ 選手循環賽，每兩人賽一次、每天每人賽一次、共 $n-1$ 天。需產生 $n \times (n-1)$ 賽程表，`table[i][j]` 為第 i 選手第 j 天對手。採用分治遞迴建構法。

演算法邏輯

1. 基礎情況 $k=1$ ($n=2$)：`table[1][1]=1, table[1][2]=2, table[2][1]=2, table[2][2]=1`。
2. 遞迴步驟：由 $2^{i-1}$ 選手賽程表建構 $2^i$ 選手賽程表。
   • 左上角：原賽程表 (選手 1~$2^{i-1}$)。
   • 左下角：原賽程表選手編號 + $2^{i-1}$ (選手 $2^{i-1}+1$~$2^i$ 互賽)。
   • 右上角：左下角轉置 (前半段選手 vs 後半段選手)。
   • 右下角：左上角複製 (後半段選手互賽)。

完整程式碼

#include 
#include 

int a[100][100];

void match(int k) {
    int n = 2, temp, i, j;
    a[1][1] = 1; a[1][2] = 2;
    a[2][1] = 2; a[2][2] = 1;

    for (i = 1; i < k; i++) {
        temp = n;
        n *= 2;
        /* 左下角 = 左上角 + temp */
        for (i = temp + 1; i <= n; i++)
            for (j = 1; j <= temp; j++)
                a[i][j] = a[i-temp][j] + temp;
        /* 右上角 = 左下角轉置 (對角鏡像) */
        for (i = 1; i <= temp; i++)
            for (j = temp + 1; j <= n; j++)
                a[i][j] = a[i+temp][(j+temp)%n];
        /* 右下角 = 左上角複製 */
        for (i = temp + 1; i <= n; i++)
            for (j = temp + 1; j <= n; j++)
                a[i][j] = a[i-temp][j-temp];
    }
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            printf("%d ", a[i][j]);
            if (j == n) printf("\n");
        }
    }
}

int main() {
    int k; scanf("%d", &k);
    if (k != 0) match(k);
    return 0;
}

範例輸出 (k=2, n=4)

1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1

第 1 選手：Day1 vs 2, Day2 vs 3, Day3 vs 4。滿足所有條件。

複雜度分析

• 時間：$O(n^2)$，必須填寫 $n \times n$ 表格。
• 空間：$O(n^2)$ 陣列。
• 遞迴深度 $k = \log_2 n$。

總結

分治遞迴利用對稱性快速建構循環賽程表，是經典演算法設計範例。