视频讲解指路:https://www.bilibili.com/video/BV1Xu4y197GL

1.实验目的

(1)掌握递归与分治法的处理思路与算法框架。
(2)掌握应用递归与分治法解决具体问题的方法。
(3)掌握分治法的广泛应用。

2.实验内容

(1)问题描述

设有$n$个运动员要进行网球循环赛。设计一个满足以下要求的比赛日程表：
（1）每个选手必须与其他$n-1$个选手各赛一次
（2）每个选手一天只能赛一次。
（3）当$n$是偶数时，循环赛进行$n-1$天；当$n$是奇数时，循环赛进行$n$天。

(2)输入

$n$:运动员人数。

(3)输出

一个比赛日程表，为有$n$行和$n-1$列的表。在表中第$i$行和第$j$列处填入第$i$个选手在第$j$天所遇到的对手。

3.问题实例分析

    实例：输入参数9。9是一个奇数，需要安排9天的循环赛。循环赛赛程安排表实现效果如下：

1	2	3	4	5	6	7	8	9	10
2	1	5	3	7	4	8	9	10	6
3	8	1	2	4	5	9	10	6	7
4	5	9	1	3	2	10	6	7	8
5	4	2	10	1	3	6	7	8	9
6	7	8	9	10	1	5	4	3	2
7	6	10	8	2	9	1	5	4	3
8	3	6	7	9	10	2	1	5	4
9	10	4	6	8	7	3	2	1	5
其中，表有10列。第1列表示选手编号，之后的2~10列中每一列都表示当天的对手。循环赛要安排9天。表格中的“10”并不是真实的对手，而是表示当前选手在当日轮空没有被安排比赛。
实例中，“9”为奇数。可以加以推广：当我们需要安排$n$人循环赛时，若$n$为奇数，我们可以安排$n+1$人的循环赛，安排表中若有人与第$n+1$号人进行比赛，其实并非真的比赛而表示轮空。若$n$为偶数，则可以将所有选手分为两半，$n$个选手的比赛日程表可以通过设计$n/2$人的循环赛日程表决定。
在设计完成$n/2$人的循环赛日程表后，左上角与左下角分别为选手1至选手$n/2$以及选手$n/2+1$至选手$n$前$n/2-1$天的比赛日程。选手$n/2+1$至选手$n$前$n/2-1$天的比赛日程为左上角选手1至选手$n/2$的比赛日程复制后加上$n/2$得到。将左上角小块中的所有数字按其相对位置复制到右下角，将左下角小块中的数字按其相对位置复制到右上角，这样就分别安排好了。
所以，为了设计9人循环赛，可以先设计10人循环赛。为了设计10人循环赛，可以先设计5人循环赛。为了设计5人循环赛，可以先设计6人循环赛。以此类推，设计3人、4人、2人循环赛。
二人循环赛安排如表所示。
1	2
–	–
2	1
在安排完成2人循环赛后，4人循环赛也可以进行安排。其中，右下角部分与左上角部分是相同的。左下角部分是的设计办法如下：按相对位置，将左上部分的对应值$+n/2$。右上角部分与左下角部分是相同的。右上角部分与左下角部分是相同的。这一过程可以被封装成copyeven函数。
1	2	3	4
–	–	–	–
2	1	4	3
3	4	1	2
4	3	2	1
接下来，将4视为轮空，3人循环赛安排表与4人循环赛安排是一致的。
1	2	3	4
–	–	–	–
2	1	4	3
3	4	1	2
通过3人循环赛安排，可以安排出6人循环赛。但是，奇数人数循环赛的“复制”、“抄”的过程与偶数人数循环赛复制过程有一定区别且较为复杂。这一过程可以被封装成copyodd函数。
对于左下部分，在把左上位置复制到左下并按相对位置加上$n/2$后，还需要安排轮空选手。在例如，1号轮空对应4号也轮空。2号轮空对应5号也轮空。3号轮空对应6号轮空。$i$轮空对应$i+n/2$轮空，则安排这两个选手比赛。可以用一个数组$b_n$记录轮空选手的对应情况。$b_i=(i+2)\mathrm{mod}n$。至此，左上部分与左下部分已经安排完成。
对于右上部分，注意到前$n/2$个选手在前$n/2$天除了与上文所述的对应轮空选手比赛，并未与其他的后$n/2$的选手进行过比赛。所以，第$i$号选手第$n/2+j$天与第$b_{i+j-1}$号选手比赛。例如，1号第4天与5号比赛，第5天与6号比赛；2号第4天与6比赛，第5天与4比赛。以此类推。
对于右下部分，是后$n/2$个选手后$n/2$天的赛程。但在安排右上部分循环赛时，前$n/2$号选手被安排的选手都是后$n/2$号选手。所以右下部分取决于右上部分。
至此，分析了$n/2$为奇数时的循环赛扩展、复制为$n$人循环赛时的办法。注意：是$n/2$为奇数不是$n$为奇数！！！

1	2	3	4	5	6
2	1	5	3	6	4
3	6	1	2	4	5
4	5	6	1	3	2
5	4	2	6	1	3
6	3	4	5	2	1
通过类似的办法，就能安排5人循环赛、10人循环赛了。
1	2	3	4	5	6
–	–	–	–	–	–
2	1	5	3	6	4
3	6	1	2	4	5
4	5	6	1	3	2
5	4	2	6	1	3

1	2	3	4	5	6	7	8	9	10
2	1	5	3	7	4	8	9	10	6
3	8	1	2	4	5	9	10	6	7
4	5	9	1	3	2	10	6	7	8
5	4	2	10	1	3	6	7	8	9
6	7	8	9	10	1	5	4	3	2
7	6	10	8	2	9	1	5	4	3
8	3	6	7	9	10	2	1	5	4
9	10	4	6	8	7	3	2	1	5
10	9	7	5	6	8	4	3	2	1

1	2	3	4	5	6	7	8	9	10
2	1	5	3	7	4	8	9	10	6
3	8	1	2	4	5	9	10	6	7
4	5	9	1	3	2	10	6	7	8
5	4	2	10	1	3	6	7	8	9
6	7	8	9	10	1	5	4	3	2
7	6	10	8	2	9	1	5	4	3
8	3	6	7	9	10	2	1	5	4
9	10	4	6	8	7	3	2	1	5

4.算法描述及说明

    若$n>2$且为奇数，则先安排$n+1$人循环赛。若$n>2$且为偶数，则先递归地安排$n/2$人循环赛。
    在安排完$n/2$人循环赛后，若$n/2$为偶数(注意:是$n/2$为偶!不是n为偶!)，则执行copyeven()函数将$n/2$人循环赛安排表扩展成$n$人循环赛。若$n/2$为奇数(注意:是$n/2$为奇!不是n为奇!此时$n$为偶数!)，则执行copyodd()函数将$n/2$人循环赛安排表扩展。copyeven与copyodd函数见实例分析。算法流程图如下。
    若$n$为2，则直接安排2人循环赛，算法结束。

5.算法正确性分析

    利用数学归纳法。$n=2$时循环赛安排表存在。对于$n=k$，假设$k$人循环赛安排表存在。若$k$为奇数，则$k+1$人循环赛安排表存在。若$k$为偶数，则$2k$和$2k-1$人循环赛安排表存在。
    举例：当2人循环赛安排存在时，3人和4人循环赛也存在。3人循环赛安排存在时，5人和6人循环赛也存在。4人循环赛安排存在时，7人和8人循环赛安排也存在。以此类推。

6.算法时间复杂性分析

设$T(k)$是算法覆盖安排$k$人循环赛所需的时间。$T(k)$满足如下递归方程：

解此递归方程可得$T(k)=O(n^2)$，算法是渐进意义下的最优算法。

7.运行结果展示及其说明

测试样例：根据提示输入人数11，则正确地生成了11人循环赛的安排表。

8.心得体会

9.程序源代码

#include<iostream>
#include<iomanip>
using namespace std;
const int M = 105;
int arr[M][M];
int brr[M];//轮空选手对应情况数组
int N;
void print(int n) {//输出
	if (n % 2 == 0) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n ; j++)
				cout << setw(3) << arr[i][j];
			cout << endl;
		}
		cout << endl;
		return;
	}

	if (n % 2 == 1) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n +1; j++)
				cout << setw(3) << arr[i][j];
			cout << endl;
		}
		cout << endl;
		return;
	}
}
void copyeven(int n) {//偶数人数时的复制
	int m = n / 2;
	for(int i=1;i<=m;i++)
		for (int j = 1; j <= m; j++) {
			arr[i][j + m] = arr[i][j] + m;//复制右上角
			arr[i + m][j] = arr[i][j + m];//复制左下角
			arr[i + m][j + m] = arr[i][j];//复制右下角
		}
}
void copyodd(int n) {//奇数人数时的复制
	int m = n / 2;
	for (int i = 1; i <= m; i++) {//计算轮空选手对应情况
		brr[i] = m + i;
		brr[m + i] = brr[i];
	}
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= m + 1; j++) {
			if (arr[i][j] > m) {//arr[i][j]>=m+1，当前选手轮空
				arr[i][j] = brr[i];
				arr[m + i][j] = (brr[i] + m) % n;//安排轮空选手进行对战
			}
			else
				arr[m + i][j] = arr[i][j] + m;//不轮空的情况，左下角直接复制
		}
		for (int j = 2; j <= m; j++) {
			arr[i][m + j] = brr[i + j - 1];//右上角安排选手
			arr[brr[i + j - 1]][m + j] = i;//右下角安排选手
		}
	}
}
void copy(int n) {
	if (n / 2 > 1 && ((n /2)%2 == 1))//根据n/2为奇数或偶数选择copyodd或copyeven
		copyodd(n);
	else copyeven(n);
}
void work(int n) {
	if (n == 1) {
		arr[1][1] = 1;
		return;
	}//递归边界
	if (n % 2 == 1) {
		work(n+1);//奇数人，安排n+1人循环赛
		return;
	}
	work(n / 2);//安排n/2人循环赛
	copy(n);//复制
}
int main() {
	cin >> N;
	work(N);
	print(N);
}