分治法解循环赛日程表：从8人赛程到代码实现

先抛一个问题：8个人打单循环赛，每个人要和另外7个人各赛一场，场地够用但每人每天最多只能打一场，到底几天能打完？很多人第一反应是"一共28场，一天安排4场，7天排满"。但真正麻烦的从来不是算总天数，而是怎么把每天的对阵排出来，保证不重不漏。这个就是循环赛日程表问题，也是分治法里最经典的教科书案例之一。

我最初接触这个问题是在算法课上学分治法，当时觉得"不就是填个表嘛"，直到自己动手排才发现，8个人的赛程有太多排列方式，如果靠脑子硬排，排到第5天就开始重复漏人。后来把分治的思路真正吃透，才发现这个问题的漂亮之处：它不只是教你怎么排比赛，而是用构造性思维直接"画"出一张合法赛程表，复杂度还只有O(n²)。这篇文章就把我从理解问题到手写代码、再到被边界条件和各种真实赛制毒打的过程完整捋一遍，希望能帮到正在啃算法或者需要实际排赛程的朋友。

1. 循环赛日程表问题的本质：先搞清楚要排一张什么样的表

1.1 一个具体到可以落地的需求描述

假设有n个选手参加比赛，这里先约定n是2的整数次幂，也就是n=2, 4, 8, 16……这样。赛制是单循环，也就是任意两个选手之间恰好交手一次。每天每个选手最多打一场比赛。问：最少需要多少天，以及每一天到底让哪几对选手对阵？

这个"最少需要多少天"很容易回答：每个选手要和另外n-1个选手各打一场，每天最多打一场，所以每个选手至少需要n-1天。也就是说，整个赛程至少持续n-1天。如果能在n-1天内排出一个合法的赛程，那就说明这个天数就是最优的，不多不少。

但"排出合法赛程"这一件事才是核心难点。什么叫合法？具体有三个约束：

• 完整性：每个选手在n-1天内确实遇到了其余所有n-1个选手。
• 唯一性：同一个对手不能在不同天重复出现。
• 对称性：如果选手A在第d天和B比赛，那么选手B在第d天也必须是和A比赛。这个约束看起来天经地义，但在写程序的时候非常容易出错，因为我只需要在表里填一个方向，另一个方向经常忘了同步。

1.2 为什么n-1天是铁律，而不是n天

这里有个常见的直觉误区。很多人觉得"8个人，每人要打7场，每天打一场，所以要7天"，这个没问题。但也有不少人会想成"循环赛是两两配对，8个人一轮可以安排4场，所有对手组合数是28场，所以需要28÷4=7天"。两个角度最后都指向7天，但前者的推导才是真正的下界证明，因为它基于的是"单个选手的参赛场次上限"，而不是总场次均摊。

这个区别在n=6时更明显。6个人，总场次是15场，每轮3场，似乎是5天。但同时每个选手也要打5场，每天最多打1场，所以下界也是5天。但如果是n=5呢？总场次10场，每轮2场，需要5轮；但每个选手要打4场，每天最多一场，下界是4天。这两个数不相等，说明"按总场次均摊算天数"并不总是准确的。在n等于偶数时碰巧凑上了，在奇数时就会出现轮空。这也是为什么后面要单独聊奇数选手的情况。

1.3 用一张矩阵统一表达赛程

为了让"排赛程"这件事可以被程序处理，最方便的办法是把赛程表示成一张表格：行是选手，列是天数，第i行第d列填的是"第i个选手在第d天的对手编号"。

比如n=4的完整赛程表是这样的：

这张表就满足上面说的三个约束。每一行的数字恰好是1到4除了自己以外的所有编号，且不重复；每一列四个格子正好组成两对合法的比赛，比如第1天是1-2和3-4。

有了这个矩阵视角，"排赛程"就变成了"填好一张n行n-1列的表格"。接下来所有分治的讨论，本质上都是围绕"高效地填这张表"展开。

2. 分治思路从哪来：把n人切成两组，缝合时才见真功夫

2.1 先分解：上下半区各自为战

分治法解决这个问题的第一步非常直觉：把n个选手从中间一切，分成上半区A和下半区B，各n/2人。如果我能先排出n/2个人的内部赛程，那我就可以让上下两个半区在比赛的前半段"同时"打各自内部的小组赛，互不干扰。

这里的关键是：两个半区内部的小组赛，用的赛程结构是完全相同的。唯一区别是选手编号不同，下半区选手编号比上半区对应位置的选手编号大n/2。也就是说，我只需要递归地算出来一个n/2人的赛程表，然后把这张表给上半区直接用，给下半区用的时候把每个格子里的对手编号加上n/2就行。

举个例子，n=4时，上下半区各2人。上半区1和2需要打一场，下半区3和4也需要打一场。这两场比赛完全可以在同一天进行：第1天安排1-2，同时安排3-4。这其实就是把2人的赛程表复制了一份，只是把下半区的选手编号整体偏移了2。

2.2 合并阶段：循环移位配对是核心，也是难点

内部小组赛解决了上半区之间的比赛，但问题还剩一大半：上半区的每个选手还要和下半区的每个选手各打一场，这部分比赛怎么安排？

这一段安排需要占用后半段的天数。具体来说：

• 前半段：上半区和下半区各自打内部赛，需要n/2-1天。
• 后半段：上半区所有人轮流和下半区所有人打，需要n/2天。
• 总天数：(n/2-1) + n/2 = n-1，正好对上。

后半段的配对方式是整个分治算法最精妙的地方。假设下半区内部编号为1到m（m=n/2），对应真实选手编号为m+1到2m。第t个跨组比赛日，让上半区的第i个选手去对阵下半区的第j个选手，其中j=(i+t-1) mod m，也就是让j随着i和t循环移动。

用大白话说：第一个跨组日，上半区1号对阵下半区1号，2号对阵下半区2号，依次对应；第二个跨组日，上半区1号对阵下半区2号，2号对阵下半区3号，最后一个上半区选手回头对阵下半区1号。之后每个跨组日都重复这个"整体错位一位"的规律。

2.3 为什么循环移位不会重也不会漏

这个配对规律背后是一个我很喜欢的数学直觉：想象两张桌子对面各坐m个人，上半区坐一排，下半区坐一排。第一场，上下对应位置的人交手；每打完一天，下半区这一排整体往左挪一个座位，最后一个人挪到最右边，于是每个人第二天都会遇到一个"新面孔"。重复m天之后，每个人恰好和对面每个位置的选手都交手一次。

用公式写会更清楚：上半区第i个选手在跨组第t天面对的对手是j=(i+t-1) mod m（下半区相对编号）。固定i，让t从1变到m，j会取遍1到m的所有值，不多不少。这就是一个完整的轮转覆盖，数学上可以严格证明，完全不依赖运气。

到这里，分治的三个步骤就齐了：分解成上下两个半区，递归地解决半区内部赛程，再通过循环移位把两个半区缝合起来。整个算法的正确性可以用数学归纳法证明：如果n/2人的赛程是合法的，那么按上述方式拼接出的n人赛程也一定是合法的。

3. 递归实现与逐轮验证：写能跑的代码，而不是只背伪代码

3.1 一份可以直接跑的C++实现

理解了原理之后写代码其实非常直接。这里给出一份我习惯用的递归版本，数据结构就是上一节说的矩阵：行表示选手，列表示天数，格子内容是对手编号。

#include <iostream> #include <vector> using namespace std; // 生成 n 个选手的单循环赛程，n 必须是 2 的幂，且 n >= 2 // 返回矩阵 ans，ans[i][d] 表示第 i+1 个选手在第 d 天的对手编号 vector<vector<int>> schedule(int n) { if (n == 2) { // 两个人只需要打一天 return {{2}, {1}}; } int m = n / 2; auto inner = schedule(m); // 递归生成 m 人赛程 vector<vector<int>> ans(n, vector<int>(n - 1)); int innerDays = m - 1; // 前 innerDays 天打半区内战 // 上半区直接用内层赛程，下半区把对手编号整体偏移 m for (int i = 0; i < m; i++) { for (int d = 0; d < innerDays; d++) { ans[i][d] = inner[i][d]; // 上半区 1..m ans[i + m][d] = inner[i][d] + m; // 下半区 m+1..2m } } // 后 m 天打跨组对抗，使用循环移位配对 for (int t = 0; t < m; t++) { int day = innerDays + t; for (int i = 0; i < m; i++) { int j = (i + t) % m; // 下半区相对编号 ans[i][day] = j + m + 1; // 上半区第 i+1 号 vs 下半区第 j+m+1 号 ans[j + m][day] = i + 1; // 对称方向，必须同步填写 } } return ans; }

这个实现有个细节值得注意：我在外层用0-based下标访问矩阵，但格子里的选手编号是1-based。也就是ans[i][d]里的"第i+1个选手"，内部编号是i+1。很多初学者在这里混，导致返回的矩阵第一行全是0或者出现自己打自己的情况。

3.2 手推n=4，把递归过程摊开看

代码写出来是一回事，能徒手推一遍才算真懂。我们来看n=4的时候发生了什么。

先递归到n=2，得到inner为[[2], [1]]，也就是选手1第1天对选手2，选手2第1天对选手1。

回到n=4时m=2，innerDays=1。前1天，上半区选手1和2直接复制inner，所以第1天是1-2；下半区选手3和4的对手分别是inner[0][0]+2=4和inner[1][0]+2=3，所以第1天同时进行3-4。这一天没问题。

后2天是跨组对抗，t从0到1。

• t=0，day=1：i=0时j=0，所以选手1第2天对阵j+2+1=3；选手3第2天对阵i+1=1。i=1时j=1，选手2第2天对阵4，选手4第2天对阵2。这一天的对阵是1-3和2-4。
• t=1，day=2：i=0时j=1，选手1第3天对阵4，选手4第3天对阵1；i=1时j=0，选手2第3天对阵3，选手3第3天对阵2。这一天的对阵是1-4和2-3。

把整张表立起来看：

和前面展示的4人表一模一样。这至少说明在n=4这个最小规模上，递归逻辑是自洽的。

3.3 验证n=8的关键步骤：别只看前4行

我见过很多人验证到n=4就停了，觉得"递归嘛，后面差不多"。但n=8才是真正检验理解度的地方，因为这里会出现8个人、7天、每天4场比赛的完整结构。用上面的schedule(8)跑出来，完整表长这样：

注意看这个表的结构：前3天左上方块是1到4的内部赛，左下方块是5到8的内部赛；后4天全部是跨组对抗。第4天是1-5、2-6、3-7、4-8；第5天整体错位一位，变成1-6、2-5、3-8、4-7；第6天再错位；第7天错到最后。这就是循环移位配对在8人规模上的完整形态。

检查每一行，比如选手5这一行是6、7、8、1、2、3、4，确实把其他7个人都遇了一遍，而且没有重复。这就是完整性和唯一性的最直接证据。

3.4 复杂度与空间优化思路

递归实现的时间复杂度很容易算。设T(n)为生成n人赛程的时间，递归方程是T(n)=2T(n/2)+O(n²)。因为递归生成两个半区各n/2人，合并阶段要把上半区、下半区各n/2行分别填n/2天，还要填跨组对抗的n/2×n/2个格子，总共O(n²)。解这个递推式，结果是O(n²)。考虑到输出本身就有n(n-1)个格子，O(n²)是最优数量级，不存在渐进上更快的算法。

空间上，上面的实现每次递归都返回一个新矩阵，递归深度log n，如果每一层的临时矩阵都不释放，累积空间是O(n² log n)。工程上更好的做法是直接开一个n×n的全局数组，递归时传入行区间和天起始位置，在原始数组上反复填充。这样空间复杂度能压到O(n²)，而且少了很多拷贝开销。为了可读性，我这里保留返回新表的写法，但在实际项目里，我建议改成原地递归版。

下面是一个简化的原地递归思路，能体会一下区别：

vector<vector<int>> table; // 全局表，table[i][d] 表示第 i+1 个选手第 d 天的对手 void fill(int left, int right, int dayBase) { int n = right - left + 1; if (n == 2) { table[left][dayBase] = right; table[right][dayBase] = left; return; } int m = n / 2; int mid = left + m - 1; fill(left, mid, dayBase); // 上半区内战 fill(mid + 1, right, dayBase); // 下半区内战 int startDay = dayBase + m - 1; // 跨组对抗开始的天 for (int t = 0; t < m; t++) { int day = startDay + t; for (int i = 0; i < m; i++) { int j = (i + t) % m; table[left + i][day] = mid + 1 + j; table[mid + j][day] = left + i; } } }

这里的关键是把"天数偏移"和"选手区间偏移"同时处理好，比返回新表的版本稍微难懂一点，但效率更高，也更接近很多教科书代码的表达方式。

3.5 一个能自动排查错误的验证函数

写完赛程生成器之后，最怕的就是看着好像对，实际某一行重复了一个对手。我强烈建议写一个自动验证函数，用代码检查而不是用眼睛检查。

bool validate(const vector<vector<int>>& schedule, int n) { // 检查每行是否是 1..n 的一个排列 for (int i = 0; i < n; i++) { vector<bool> used(n + 1, false); used[i + 1] = true; // 不能和自己比赛 for (int d = 0; d < n - 1; d++) { int opp = schedule[i][d]; if (opp < 1 || opp > n || used[opp]) { return false; } used[opp] = true; } } // 检查对称性：A 在某天遇到 B，B 的同一天也必须遇到 A for (int i = 0; i < n; i++) { for (int d = 0; d < n - 1; d++) { int opp = schedule[i][d]; if (schedule[opp - 1][d] != i + 1) { return false; } } } return true; }

这个函数每次检查都是O(n²)的，跑得很快。配合随机测试，可以把n=2、4、8、16都验一遍，确认算法在各种规模下都正确。我在实际写这个算法的时候，第一次对称性检查就没过，因为跨组对抗时我只填了"上半区选手视角"那一行，忘了同步反向格子。

4. 经典四象限填表法：好看，但容易踩坑

4.1 教科书里常见的那个思路

很多教材讲完分治思想之后，会给出一个看起来更"优雅"的填表方式：直接把赛程表做成一个n×n的方阵，左上角递归生成上半区的内部赛程，然后通过四条简单的赋值把整个方阵填满。大致逻辑是：

• 左上块：递归生成n/2人的赛程。
• 右上块：左上块每个元素加上n/2，表示上半区选手对阵下半区对应选手。
• 左下块：右上块的某种转置，保证下半区选手的反向视角。
• 右下块：直接复制左上块，表示下半区的内部赛程。

这个思路本身没错，而且代码量看起来比我的循环移位版本少很多。但我在实践里踩过坑，也看过不少同学在这个版本上翻车，所以这里单独拎出来说。

4.2 最容易翻车的点：哪个格子是有效天数？

问题出在一个很隐蔽的地方。4个人单循环只需要3天，但方阵是4×4的，第4列如果按"左上角元素+n/2"之类的规律硬填，很容易填出一些怪数，比如某一行出现"3、4、1"这种在第4天重复遇到对手的假数据。

我在最初照着教材代码改写时就遇到过：跑出来的8×8表，第一行是2、3、4、5、6、7、8、1。前7列看着都对，第8列是1，也就是选手1第8天"遇到自己"，这个格子其实是占位用的。真正的n人赛程只需要n-1天，方阵多出的那一列本质上是对角线占位，不应该被当成有效赛程。但很多人在"复制左上块到右下块"的过程中，会把占位列也复制进去，然后某一天就莫名出现选手自己打自己的情况。

还有一个容易踩的坑是四条赋值的坐标关系。左上块是a[i][j]，右上块应该写a[i][j+m] = a[i][j] + m；左下块应该是a[i+m][j] = a[i][j+m]（也就是把右上块转置过来）；右下块是a[i+m][j+m] = a[i][j]。如果哪里坐标写反了，结果不是重复就是越界。这个确实比循环移位版更容易写错。

4.3 我的个人建议

这几种实现各有取舍。循环移位版需要理解轮转思想，但代码结构清晰，跨组配对和内部赛程完全分离开，不容易把占位列搞混。四象限填表法想法很优雅，代码看着短，但必须先在心里建立一个"方阵多一列占位"的心智模型，否则很容易在边角区域写出自以为正确、实际错误的赋值。

我的习惯是：刷题或者理解算法时用循环移位版，因为它和分治思想的对应关系最直白；只有在需要"背出一个最短代码应付考试"时，我才会考虑四象限法。如果你真心想彻底掌握这个问题，我的建议是从循环移位版入手，先手推n=4，再手推n=8，每一步都对照矩阵里的坐标。等彻底想明白了，再去欣赏四象限填表法那种整体美感也不迟。

5. 边界情况与真实赛制：n不是2的幂怎么排

5.1 赛场上几乎不会有16个队这种好事

分治法要求n是2的幂，但真实世界的比赛很少有刚好8个队、16个队的情况。6个队、10个队、12个队才是常态。这时候如果硬套上面的递归分治，就会遇到"切不开"的问题：6个人没法拆成两个相等的整数半区。

一个非常实用的技巧是补虚选手。把报名人数向上补到最近的2的幂，比如6个人就补到8个人，多出来的两个位置填成"轮空"。任何选手抽到和虚选手比赛的那天，就是他的休息日。这样虽然赛程天数变多了，但结构依然可以用经典分治生成。

具体来说，6人比赛补齐成8人后，赛程长度是7天。其中每个真实选手会在某些天遇到"虚选手"，那天的比赛就不存在，等于轮空。7天里每个人实际只打5场，剩下两天休息。这个方案虽然比最优的5天要多两天，但换来的是极其规整的赛程结构，对于小规模比赛完全可接受。

5.2 圆桌轮转法：处理任意偶数n的通用方案

如果你对"多出的轮空天数"不满意，可以换一个更通用的办法：圆桌轮转法，也经常被叫做Berger表或者多边形法。这个办法不要求n是2的幂，只要n是偶数，就能直接排出n-1天的单循环赛程，一天不浪费。

规则是这样的：固定选手1号，把其余n-1个选手编号按顺序排成一个圆圈。第1轮，圆圈尾部的选手对1号，然后圆圈里剩下的偶数个选手按"首尾配对"的方式两两交手。下一轮，让圆圈整体顺时针旋转一步，重复同样的配对逻辑。这样滚动n-1轮之后，每个选手恰好遇到其他所有人一次。

我用n=6给你演示一下，这个直接看表最快：

检查一下，选手1在这5轮里依次遇到6、5、4、3、2，刚好把其他5个人都遇了一遍；选手2遇到5、3、6、4、1，也没有重复。5天结束，每天3场比赛，正好排满。这个方案通用性强，实现也不复杂，我在实际参与组织一次社区羽毛球赛时就用它排过程序，效果很稳。

5.3 奇数人数怎么办？

奇数人数就更好处理了，加一个虚拟的"轮空选手"就行。比如5个人，补成一个虚拟的第6号。每个真实选手在和6号配对的那天休息，其余4天正常比赛。这样5个人需要5天，每天两场比赛加一个轮空。天数比理论下界的4天多一点，这是奇数人数固有的代价，绕不开。

如果你还想压缩天数，那就要引入不同赛制了，比如小组赛加淘汰赛、瑞士轮等。这些赛制已经不追求"任意两人都交手一次"的强约束，而是用积分或者淘汰规则在更少轮次里决出胜负。这类需求在现实中更常见，但它属于另一个话题，和这里的循环赛日程表分治问题已经不是一个量级。

6. 这个算法在真正工程项目里的用处

6.1 不只是作业题：几个可以落地的场景

循环赛日程表生成器最直接的应用就是赛事编排。小到单位内部的羽毛球赛、乒乓球赛，大到围棋联赛、电竞联赛，只要需要"每两个队碰一次"的单循环赛制，这张表就能直接套用。

第二个场景可能有点意外：并行计算中的任务分发。在有些分布式训练或数据分片场景里，需要让n个计算节点两两之间交换数据，而且每一轮每个节点只能参与一次交换。这和循环赛的约束完全同构：把"选手"换成"计算节点"，把"比赛"换成"数据交换任务"，分治法生成的就是一份无冲突的通信调度表。这个应用在某些矩阵转置、全量数据聚合的任务里是真实存在的。

第三个场景是图论和组合设计。循环赛日程表的每一列本质上是一个完美匹配，整个表就是完全图K_n的边集分解成n-1个完美匹配，这在数学上叫1-因子分解。如果对算法背后的组合结构感兴趣，这会是一个很好的切入点。

6.2 构造性思维比答案本身更值钱

我之所以觉得这个算法值得反复咀嚼，是因为它体现了一种"构造性证明"的思维方式：不是搜索一个解，而是直接定义出一个永远合法的解。在很多实际系统里，搜索解空间是不可行的，比如n=16时赛程的排列组合数量是天文数字，暴力回溯根本跑不完，但分治构造法可以瞬间生成一张合法表。

这种"把问题切小、各自搞定、再缝合"的思路，用在项目管理里也一样：一个看起来无从下手的大型任务，先切成两个半区，让每个半区的负责人都能独立推进，最后用一个明确的合并规则把两边接起来。这个合并规则就是整个系统最需要设计精妙的部分，就像循环移位配对一样，看似平淡，实则保证了全局不重不漏。

6.3 给正在啃算法的朋友几句实在话

如果你是为了面试或者考试准备这个题目，我的建议是别背代码，先背过程。面试官问"n=8的赛程表怎么排"，你如果能当着他的面把表画出来，并解释为什么第4到第7天是循环移位，基本就过关了。如果只说得出"用分治法，左上角递归"这种话，大概率会被追问到卡壳。

如果你是为了实际使用，建议直接在现成的轮转法基础上改，别从分治法往上凑。比如用我上面的schedule函数跑一次，把结果输出成表格，再自己写个脚本做轮空替换。很多项目管理工具其实也内置了赛程生成功能，但自己写一遍能让你在改动需求时更有把握。

最后，手推一张n=4的表只需要几分钟，但这几分钟能让你真正理解递归展开的每一步在干什么。这个习惯我一直保留到现在，遇到新的分治类问题，也会先找一个最小的非平凡规模，亲手把递归过程摊开验证一遍。这种笨办法，反而是最省时间的捷径。