1 题目
设有n-2个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表:
①每个选手必须与其他n-1个选手各赛一次;
②每个选手一天只能赛一次;
循环赛一共进行n-1天。
按此要求可将比赛日程表设计成有n行和n-1列的表。在表中第i行和第j列处填入第i个选手在第j天所遇到的选手。
2 思路
按分治策略，可以将所有选手对分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用这种一分为二的策略对选手进行分割，直到只剩下两个选手时，比赛日程表的制定就变得简单了。这时只要让这两个选手进行比赛就可以了。
如果是n=2*可以对称分割，则可以这样排:
3 分析
主要是代码太多循环了，有点难分析。
3.1 各个参数的含义：
- n：n=2^k，有n个选手（保证了n为偶数）
- k：划分表，一共会划分k次（每次划分都是把n*n的表化成四个（n/2）*（n/2）嘛，很好理解）
3.2 四个循环：
- 里面的两个for循环：交叉填m*m大小的日程表（运行一遍我的代码就知道了，每次交叉填完就输出日程表）
- 第二层循环：因为最开始肯定m=1,把第一行的交叉填到第二行，一共会有n/2次这样的交叉填，第二层循环参数 t 就是用来控制这个交叉填次数的。
- 最外层循环：第二行填完了，就是第一次递归完成了；接下来将第一二行填到第三四行，其实这就是递归的第二层了，递归一共会有 k 层，所以原代码是外层是 for 循环 k 控制，我习惯写成 while，感觉更好理解；
3.3 交叉填为啥是那样写的：
我们每次填的时候会发现，他的行其实就是i=m+1 ~ i<=2m(因为每次填mm大小，所以最下行=最上行+m-1)。
但是清注意列虽然也是m宽，这个代码 j 的初始大小永远都是m+1,而列实际上是随着前面的交叉填填完后要后移2*m的，因此代码就是如下所写了。
3.4 建议
看文字确实很难理解，运行一遍我的代码就会清楚很多。
希望能帮到大家。(外加，算法好难，哭)
4 代码
#include<iostream>
using namespace std;
int a[10][10];//日程表 void Table(int k) { //有2^k个选手 a为比赛日程表int n=1;for(int i=1; i<=k; i++) //计算选手人数（n=2^k）n=n*2;for(int i=1; i<=n; i++) //初始化比赛日程表：设置日程表第一行a[1][i]=i;int m=1;//每次填充时，起始填充位置while(k--) { //问题被划分k次n/=2; //n=交叉填的次数//k=3 填第二行： 需要填 原n/2次 交叉填 因此for循环是t<=n //k=2 填第三、四行： 只需要 原n/4次 交叉填//k=1 填五六七八行： 只需要 原n/8次 交叉填 for(int t=1; t<=n; t++) { //交叉填 for(int i=m+1; i<=2*m; i++) { //控制行for(int j=m+1; j<=2*m; j++) { //j和t 和m一起控制列 //每天交叉填完两个m*m大小的方格，列就要往后移动两个m a[i][j+(t-1)*m*2-m]=a[i-m][j+(t-1)*m*2];//左下角等于右上角的值a[i][j+(t-1)*m*2]=a[i-m][j+(t-1)*m*2-m];//右下角等于左上角的值}}
/* i-m j+(t-1)*m*2-m ... i-m j+(t-1)*m*2... ...... ...
待填的部份: i j+(t-1)*m*2-m i j+(t-1)*m*2... i+m+1
*/
//输出日程表方便理解for(int i=1; i<=8; i++) {for(int j=1; j<=8; j++) {cout<<a[i][j]<<" ";}cout<<endl;}cout<<"---------------"<<endl;}m*=2;//下一轮交叉填的大小变为原来的两倍//1*1 -> 2*2 -> 4*4 }
}int main() {Table(3);//调用函数 //输出日程表 for(int i=1; i<=8; i++) {for(int j=1; j<=8; j++) {cout<<a[i][j]<<" ";}cout<<endl;}
}
