循环赛日程表(递归实现)

题目说明：

设有n=2k（k为上标）个选手要进行循环赛，要求设计一个满足以下要求的比赛日程表：

（1）每个选手必须与其他n-1个选手各赛一次；

（2）每个选手一天只能赛一次。

按此要求，可将比赛日程表设计成一个 n 行n-1列的二维表，其中，第 i 行第 j 列表示和第 i 个选手在第 j 天比赛的选手。

此题采用分治策略，通过在k=1和k=2时找到打印规律:

k=1：        1 2           k=2：  1 2 3 4 

                  2 1                      2 1 4 3

                                             3 4 1 2

                                             4 3 2 1

第一列为所有选手，每一行的除了第一列外，剩下的每一列都是该选手在接下来的n-1天要面对的比赛对手。通过观察，可以发现，左上角和右下角的数字相同，左下角和右上角的数字相同（对于k=2,以k=1的规模为整体观察）。

程序设计思路(c++实现)：因为C++不能按指定行打印，所以先创建一个足够大的二维数组将结果先存入其中，如a[N][N]。在n=2*k个选手比赛时，先确定左上角的数据和左下角的数据，在利用对称复制，将左下角的数据复制到右上角，将左上角的数据复制到右下角。详细说明请查看代码注释。

#include <iostream>
using namespace std;
const int N = 50;
int a[N][N];  //定义足够大的数组void dim(int i, int j, int n) {int k1, k2;int mid = n / 2;if (n == 2) {    //当递归到只有两个选手时，i=1,j=2,n=2a[i][n] = j;   //右上角为2a[j][n] = i;   //右下角为1a[i][n - 1] = i; //左上角为1a[j][n - 1] = j; //左下角为2} else {dim(i, i + mid - 1, mid); //递归一半mid，开始为i，结束为i到mid的个数，即i+mid-1，规模为middim(i + mid, j, mid); //递归另一半mid，开始为i+mid，j，规模为mid//此for循环中，需要复制规模为mid行mid列，一趟循环先复制第n列，再一趟循环复制第n-1列，直到第mid+1列//对于复制的下标的确定，可以想象n=2*2个选手时的下标跟着下面的循环走一遍for (k1 = n; k1 > mid; k1--) {//以下for循环的边界的确定k2 <= i + mid - 1和k2 <= i + n - 1，//可以用k2的初始值+mid的大小确定。循环次数为midfor (k2 = i; k2 <= i + mid - 1; k2++) { //此for循环将左下角的数据复制到右上角a[k2][k1] = a[k2 + mid][k1 - mid];}for (k2 = i + mid; k2 <= i + n - 1; k2++) { //此for循环将左上角的数据复制到右下角a[k2][k1] = a[k2 - mid][k1 - mid];}}}
}int main() {int n = 1, i, j, k;scanf("%d", &k);    //输入k,但是选手是n=2k（k为上标），即2的k次方个选手for (i = 1; i <= k; i++)   //所以n是2的k次方，打印的日程表是n×n的表格。n = n * 2;dim(1, n, n);        //第一个参数是第一行，第二个参数是第n行，第三个参数为要处理n行。for (i = 1; i <= n; i++) {      //递归完成，双重for循环打印二维数组cout << endl;for (j = 1; j <= n; j++) {cout << a[i][j] << " ";}}return 0;
}