循环赛日程表（分治算法）

循环赛日程表是分治算法（Divide and Conquer）的经典应用之一，用于为 $n$ （通常为 $2^{k}$ ）名选手安排比赛日程，确保每位选手与其他所有选手恰好比赛一次且每天仅进行一场比赛。该问题展示了分治算法的核心思想：将大问题分解为小问题，递归求解后合并结果。

问题描述[编辑 | 编辑源代码]

设有 $n = 2^{k}$ 名选手参加循环赛，要求： 1. 每位选手必须与其他 $n - 1$ 名选手各比赛一次； 2. 每位选手每天只能进行一场比赛； 3. 比赛在 $n - 1$ 天内完成。

目标：生成一个 $n \times n$ 的日程表，其中第 $i$ 行第 $j$ 列表示选手 $i$ 在第 $j$ 天的对手。

分治算法设计[编辑 | 编辑源代码]

基本思想[编辑 | 编辑源代码]

1. 分解：将 $n$ 名选手分成两组，每组 $n / 2$ 人； 2. 递归：为每组生成日程表； 3. 合并：将两组日程表合并，填充交叉比赛。

递归关系[编辑 | 编辑源代码]

设 $T (n)$ 为计算 $n$ 名选手日程的时间复杂度： $T (n) = 2 T (n / 2) + O (n^{2})$ 根据主定理，时间复杂度为 $O (n^{2} \log n)$ 。

算法实现[编辑 | 编辑源代码]

以下是Python实现代码：

def schedule_table(n):
    # 初始化日程表
    table = [[0] * n for _ in range(n)]
    
    # 递归填充日程表
    def fill_table(start, size):
        if size == 1:
            table[start][0] = start + 1
            return
        half = size // 2
        fill_table(start, half)  # 填充左上子表
        fill_table(start + half, half)  # 填充左下子表
        
        # 合并子表
        for i in range(half):
            for j in range(half):
                # 右上子表 = 左下子表 + half
                table[start + i][j + half] = table[start + half + i][j] + half
                # 右下子表 = 左上子表
                table[start + half + i][j + half] = table[start + i][j]
    
    fill_table(0, n)
    return table

# 示例：n=4
n = 4
table = schedule_table(n)
for row in table:
    print(row)

输入/输出示例：

输入: n = 4
输出:
[1, 2, 3, 4]
[2, 1, 4, 3]
[3, 4, 1, 2]
[4, 3, 2, 1]

解释： - 第1行表示选手1在第1-4天的对手依次为1（自身）、2、3、4； - 第2行表示选手2的对手为2（自身）、1、4、3。

可视化示例[编辑 | 编辑源代码]

以下是 $n = 4$ 时的日程表：

实际应用[编辑 | 编辑源代码]

1. 体育联赛：如足球、篮球联赛的赛程安排； 2. 棋类比赛：国际象棋循环赛的对手分配； 3. 分布式计算：任务调度中均衡分配计算资源。

扩展思考[编辑 | 编辑源代码]

若 $n$ 不是2的幂次，可通过添加“虚拟选手”调整为 $2^{k}$ ；
优化空间复杂度：利用对称性减少存储。

总结[编辑 | 编辑源代码]

循环赛日程表问题展示了分治算法在组合优化中的高效性，通过递归分解和合并子问题，实现了 $O (n^{2} \log n)$ 的解决方案。理解此问题有助于掌握分治思想的实际应用场景。