1.实验目的
(1)掌握递归与分治法的处理思路与算法框架。
(2)掌握应用递归与分治法解决具体问题的方法。
(3)掌握分治法的广泛应用。
2.实验内容
(1)问题描述
(2)输入
n:运动员人数。
(3)输出
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人循环赛，可以先设计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函数。
| 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.算法描述及说明
5.算法正确性分析
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); }
