编辑“︁循环赛日程表（分治算法）”︁

{{DISPLAYTITLE:循环赛日程表（分治算法）}}

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

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

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

== 分治算法设计 ==
=== 基本思想 ===
1. '''分解'''：将<math>n</math>名选手分成两组，每组<math>n/2</math>人；
2. '''递归'''：为每组生成日程表；
3. '''合并'''：将两组日程表合并，填充交叉比赛。

=== 递归关系 ===
设<math>T(n)</math>为计算<math>n</math>名选手日程的时间复杂度：
<math>
T(n) = 2T(n/2) + O(n^2)
</math>
根据主定理，时间复杂度为<math>O(n^2 \log n)</math>。

== 算法实现 ==
以下是Python实现代码：

<syntaxhighlight lang="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)
</syntaxhighlight>

'''输入/输出示例'''：
<pre>
输入: n = 4
输出:
[1, 2, 3, 4]
[2, 1, 4, 3]
[3, 4, 1, 2]
[4, 3, 2, 1]
</pre>
'''解释'''：
- 第1行表示选手1在第1-4天的对手依次为1（自身）、2、3、4；
- 第2行表示选手2的对手为2（自身）、1、4、3。

== 可视化示例 ==
以下是<math>n=4</math>时的日程表：

<mermaid>
gantt
    title 循环赛日程表 (n=4)
    dateFormat  YYYY-MM-DD
    axisFormat %d
    section 选手1
    第1天 :a1, 2023-01-01, 1d
    第2天 :a2, after a1, 1d
    第3天 :a3, after a2, 1d
    section 选手2
    第1天 :b1, 2023-01-01, 1d
    第2天 :b2, after b1, 1d
    第3天 :b3, after b2, 1d
    section 选手3
    第1天 :c1, 2023-01-01, 1d
    第2天 :c2, after c1, 1d
    第3天 :c3, after c2, 1d
    section 选手4
    第1天 :d1, 2023-01-01, 1d
    第2天 :d2, after d1, 1d
    第3天 :d3, after d2, 1d
</mermaid>

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

== 扩展思考 ==
* 若<math>n</math>不是2的幂次，可通过添加“虚拟选手”调整为<math>2^k</math>；
* 优化空间复杂度：利用对称性减少存储。

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

[[Category:分治算法]]
[[Category:数据结构与算法]]

[[Category:计算机科学]]