一、循环赛日程表-设计规则

1.每位选手必须与其他 n - 1 位选手各比赛 1 次

2.每位选手每天只能比赛 1 次

3.循环赛一共进行 n - 1 天

4.选手人数为 n =

假设比赛选手为8（满足n = ），则循环赛需要进行7天，如下表1所示：

选手号	第一天	第二天	第三天	第四天	第五天	第六天	第七天
1
2
3
4
5
6
7
8

图表1

为了满足每位选手必须与n-1选手比赛1次，并且每位选手每天只能比赛1次的要求，如表2所示：

选手号	第一天	第二天	第三天	第四天	第五天	第六天	第七天
1	2	3	4	5	6	7	8
2	1	4	3	6	5	8	7
3	4	1	2	7	8	5	6
4	3	2	1	8	7	6	5
5	6	7	8	1	2	3	4
6	5	8	7	2	1	4	3
7	8	5	6	3	4	1	2
8	7	6	5	4	3	2	1

图表2

---

二、循环赛日程表-递归设计思路

        如果将所有选手分为两半（故：n/2），那么就将排好的8×8赛程表割分成4个4×4的赛程表，可以发现左上角4×4的赛程表与右下角4×4的赛程表是一样的，左下角4×4的赛程表与右上角4×4的赛程表也是一样的。

        如果再将选手分为两半（故：n/2/2），那么就会将4×4的赛程表割分4个2×2的赛程表，左上角2×2的赛程表与右下角2×2的赛程表是一样的，左下角2×2的赛程表与右上角2×2的赛程表也是一样的。

      那么就可以将每次排好的左上角的赛程表copy到右下角，将每次排好的左下角的赛程表copy到右上角，那么就可以完成整个赛程表的排列。

      以上符合分治策略的思想，将所有的选手分为两半，n个选手的比赛日程就可以通过分成n/2个选手设计的比赛日程表来决定。采用递归的方式对选手进行割分，直至割分到只剩下1位选手时，比赛日程表就不在需要为其排列。

边界条件：n = 1

分解子问题：

1.递归左上角赛程表

2.递归左下角赛程表

3.将左上角赛程表copy到右下角

4.将左下角赛程表copy到右上角

---

三、循环赛日程表-设计代码（递归）

//C语言编写
#include<stdio.h>

int table[8][8];

//从(行:a~a+n-1,列:b~b+n-1)copy到(行:k~k+n-1,列:h+n-1)
void Copy(int a, int b, int k, int h, int n){    
    int i,j;
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            table[k+i][h+j] = table[a+i][b+j];
        }
    }
}

//循环赛日程表-递归方式
void Table(int a, int b, int n){   //a,b为左上角的行号和列号，n比赛选手位数
    if(n == 1){
        return;
    }
    else{
        Table(a,b,n/2);            //将左上表进行割分
        Table(a+n/2,b,n/2);        //将坐下表进行割分
        Copy(a,b,a+n/2,b+n/2,n/2); //将左上表copy到右下表
        Copy(a+n/2,b,a,b+n/2,n/2); //将左下表copy到右上表
    }
}

//初始化二维数组
void InitTable(int table[8][8], int n){    
    int i = 0;
    int j = 1;
    for(i = 0; i < n; i++,j++){
        table[i][0] = j;
    }
}

//打印二维数组
void PrintTable(int table[8][8], int n){   
    int i,j;
    for(i = 0; i < n; i++){
        for(j = 0; j < n; j++){
            printf("%d\t",table[i][j]);
        }
        printf("\n");
    }
}

//主函数
int main(){
    InitTable(table,8);
    PrintTable(table,8);
    printf("\n");
    Table(0,0,8);
    PrintTable(table,8);
    return 0;
}

---

四、循环赛日程表-递推设计思路

按照上面的要求，通过递推的思想也是很容易的​（如图所示）

图表3

      可以发现想要完成循环赛日程表，那么至少需要执行n-1遍（例如：8个选手，那就需要执行7遍），执行一遍需要将左上表copy到右下表，将左下表copy到右上表。

      那么知道这个规则之后，就需要找出执行一遍的步长（r），比如说图表3上编号1，从左上表的1copy到右下表的1，从左下表的2copy到右上表的2，可以发现从左上表copy到右下表与从左下表copy到右上表两者的步长为1；再比如说图表3上编号5，从左上表的2*2矩阵copy到右下表的2*2矩阵，从左下表的2*2矩阵copy到右上表的2*2矩阵，两者的步长为2；再比如说图表3上编号7，从左上表的4*4矩阵copy到右下表的4*4矩阵，从左下表的4*4矩阵copy到右上表的4*4矩阵，两者的步长为4；

      那么可以发现步长（r）是1，2，4；也就是r=r*2

      如图表3所示，通过数组坐标来分析，如何设计填写从左上表copy到右下表与从左下表copy到右上表：

图表3编号	from 左上表	to 右下表	from 左下表	to 右上表	步长（r）
1	[0][0]	[1][1]	[1][0]	[0][1]	1
2	[2][0]	[3][1]	[3][0]	[2][1]	1
3	[4][0]	[5][1]	[5][0]	[4][1]	1
4	[6][0]	[7][1]	[7][0]	[6][1]	1
5	[0][0]	[2][2]	[2][0]	[0][2]	2
6	[4][0]	[6][2]	[6][0]	[4][2]	2
7	[0][0]	[4][4]	[4][0]	[0][4]	4

左上表copy到右下表

      1.from左上表[纵坐标][横坐标]中，[纵坐标]都是偶数按照2*r增长，[横坐标]都是初始值（0）；

     2.to右下表[纵坐标][横坐标]中，[纵坐标]都是奇数按照from左上表[纵坐标]+r并且2*r增长，[横坐标]都是按照from左上表[横坐标]+r；

copy（from左上表[纵坐标]，from左上表[横坐标]，to右下表[纵坐标]，to右下表[横坐标]，r）

=

copy（from左上表[纵坐标]，初始值（0），from左上表[纵坐标]+r，from左上表[横坐标]+r）

从左下表copy到右上表

      1.from左下表[纵坐标][横坐标]中，[纵坐标]都是奇数按照2*r增长，[横坐标]都是初始值（0）；

      2.to右上表[纵坐标][横坐标]中，[纵坐标]都是偶数按照from左下表[纵坐标]+r并且2*r增长，[横坐标]都是按照from左下表[横坐标]+r；

copy（from左下表[纵坐标]，from左下表[横坐标]，to右上表[纵坐标]，to右上表[横坐标]，r）

=

copy（from左下表[纵坐标]，初始值（0），from左下表[纵坐标]+r，from左下表[横坐标]+r）

---

五、循环赛日程表-设计代码（递推）

//C语言编写
//循环赛日程表-递推方式
void Table(int a, int b, int n){
    int i = 0;
    int r = 1;
    int k = n;
    while(k>1){                         //记录执行次数
        for(i=0;i<n;i=i+2*r){           //i每次增加本次循环的2*步长，因为每次进行两次copy
            Copy(a+i,b,a+i+r,b+r,r);    //左上表copy右下表
            Copy(a+i+r,b,a+i,b+r,r);    //左下表copy右上表
            k--;                        //执行次数减一
        }
        r = r * 2;                      //步长
    }
}