网球循环赛日程表

一、 问题表述：

设有n个运动员要进行网球循环赛。设计一个满足以下要 求的比赛日程表，

(1) 每个选手必须与其他n-1个选手各赛一次； (2) 每个选手一天只能赛一次；

(3) 当n是偶数时，循环赛进行n-1天，当n是奇数时，循环

赛进行n天

二、 分析问题

题目是要n名运动员进行循环比赛。当n为偶数时，正好每天都可以两两一组，与其余的n-1个选手比赛，只需n-1天； 而当n为奇数，每天将有一个选手轮空，比赛将持续n天。 可以采用的算法如下：

1. 算法一：使用分治法

当n为偶数时，可以讲问题分为两个部分n/2; 然后继续划分，知道最后剩余两名选手单独比赛。当n为奇数时，增设一个虚拟选手，运动员为n+1个，将问题转化为是偶数的情形。当选手与虚拟选手比赛时，表示轮空，因此只需要关注n为偶数的情形。 a) 当n/2为偶数时，与n = 2^k情形类此。

b) 当n/2为奇数时，增设一个虚拟的选手，递归返回的将有轮空的选手，可以讲在前面n/2轮比赛的选手与后面n/2轮空的选手进行比赛。

2. 算法二：利用边是奇数的正多边形。

特点：以多边形中的任意一个顶点画对称轴，其余偶数对顶点相互对称。

N名选手编号为1~n，将其画成一个正多边形。 a) 所以当n为奇数时，第一天1号休息，其余以一号为对称轴，两两对称打比赛，第二天开始一次轮流休息，其余一休息的那个人编号为对称轴，两两比赛。这样比赛可进行n天。如图：

对称轴

此时n=9，为奇数，从0开始每天有一个人轮空 876501234

80对称轴 1765423

b) 当n为偶数时，取出编号最大的，其他的组成一个正多边形，n号一次顺序与1,2，。。。n-1号选手比赛，其他与a）相同。如图所示：（图中是从0开始编号）

99 0N=2k时 81726354

9 8765

01234

三、 理论分析算法及实现

1. 算法一：使用分治法

a) 算法的思路：按分治策略，可以将所有的选手对分为两组（如果n是偶

数，则直接分为n/2每组，如果n是奇数，则取（n+1）/2每组），n个选手的比赛日程表就可以通过为（n/2或（n+1）/2）个选手设计的比赛日程表来决定。递归地用这种一分为二的策略对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。

下图给出的是六个选手的比赛日程表，其中第一列表示1-6个选手，第二列到第六列表示各个选手在第一天到第五天的所遇到的选手。 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

在这里算法设计的难点就是分开治理后的合并问题。这里我就结合上面给出的6个选手的示例来进行表述。首先，将6个选手分为对等的两组，每组3个选手。每组增设一个虚拟的选手，然后再递归的将3个选手分为对等两组，每组2个选手。

在2个选手情况下，这两个选手比赛。可以得到两个选手的日程安排表是： 1 2 2 1

接下来的任务是合并这两组2个选手的日程表得到3个选手的日程安排表，这里我先假设有4个选手参加比赛则： 1 2 2 1 3 4 4 3

接下来的比赛里，第二天让1和3比赛，2和4比赛；第三天让1和4比赛，2和3比赛，即让前一组的选手，循环的和后一组的选手比赛，可得到比赛日程安排表是： 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1

这里要得到的是3个选手的日程安排表，则第4个选手是假想的选手将其用0来表示则得到3个选手的日程安排表： 1 2 3 0 2 1 0 3 3 0 1 2

接下来的任务是合并这两个3个选手的日程安排表得到6个选手的日程安排表，这里我们的两组选手前3天的比赛情况如下：

1 2 3 0 2 1 0 3 3 0 1 2 4 5 6 0 5 4 0 6 6 0 4 5

其中第一天选手3和选手6都没有对手，让他们两个比赛；第二天选手2和选手5没有对手，让他们两个比赛，；第三天选手1和选手4没有对手，让他们两个比赛。这就可以得到合并后6个选手前三天的比赛日程安排表： 1 2 3 4 2 1 5 3 3 6 1 2 4 5 6 1 5 4 2 6 6 3 4 5

将在前三天比过赛的两组的选手对应的列出来： 1 2 3 4 5 6

在这里可以看到合并的两组中3和6，2和5，1和4都已经比过了，这里就跳过这些选手的比赛，然后两个组循环比赛即： 1 2 3 5 6 4

和 1 2 3 6 4 5

这样就得到了6个选手的比赛完整的日程安排表： 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

b) 证明算法的正确性：

（1） 在n=2时，就这两个选手比赛，比赛只进行一天，这也是算法的初始情况，算法成立。

（2） 在n=k时，如果k为偶数，则将k个选手分为k/2的两组，这样按问题的要求k个选手共比赛k-1天，k/2个选手如果是偶数则比赛（k/2）-1天，在合并的时候两组k/2个选手循环比赛需要k/2天，则先分组后合并共需要（k/2）-1+（k/2）=k-1天；k/2个选手如果是奇数则比赛k/2天，在合并的时候两组中每个选手都相对应的比赛过了一次，所以两组k/2个选手循环比赛需要（k/2）-1天，则先分组后合并共需要（k/2）+（k/2）-1=k-1天。

（3） k为奇数的情况和k为偶数的情况类似。 c) 算法的描述和架构：

分治法主要就是用 当n=2^k时

void tournament(int n) {

if(n == 1) {

a[1][1] = 1; return; }

Tournament(n/2); Copy(n); }

主要是将左上角的递归计算出的小块中的所有数字按照其相对位置抄写到右下角，将左上角小块中的所有数字加n/2后按照其相对位置抄写到左下角，将左下角小块中的所有数字按照相对位置抄到右上角。 问题：n或者n/2可能不是偶数，此时就要虚拟增加一个队员。 if(odd(n)) //如果是奇数 {

tournament(n + 1); return;

} else {

tournament(n/2); //是偶数时，递归调用，返回时合并 makecopy(n); }

合并环节是最重要的，如果是n偶数的话，如上面的函数copy（n），但是如果是奇数，需要调用copyodd（n） void copyodd(int n) {

int m = n /2; int i,j;

for(i = 1; i <= m; i++) //i的范围是<=m，所以超出m的范围就不算了

{

for(j = 1; j <= m + 1; j++)

if(a[i][j] > m) //如果有轮空的话，就让前n/2轮空的选手去后n/2轮空的选手比赛

{

a[i][j] = m + i; a[m + i][j] = i; } else

a[m + i][j] = a[i][j] +m;

}

}

for(j = 2; j <=m; j++) { int k,r = i; if(i + j - 1 > m) k = i + j -1; else k = m + i + j - 1; a[r][m + j] = k; a[k][m + j] = r; }

其中后n/2天比赛中，是前n/2选手和后n/2的选手比赛，这点很值得推敲。

架构：

输入运动员的个数 n

Tournament（n）

N为偶 N为奇 N = n +1 Tournament（n/2） N ==1 makecopy(n)N为偶 Copy(n) N为奇 Copyodd(n) 2. 算法二：利用边是奇数的正多边形。

在第二部分图解中已经比较详细描述过，最难想到的一个规律是，对称之后如何转换，如下图；

8765012349

以n=10为例子，比如以1对称轴，0和2对称，8和3对称，7和4对称，6和5对称，除了 a[r][j] = k, a[k][j] = r之外，还有什么规律呢？

经过多次画图之后发现，当对称轴变为2时，3和0对称，8和5对称，7和6对称，转变相邻的对称轴，原来对称点的位置改变了两个距离。以前8和3对称，现在8和5对称，增加了两个，以前7和4对称，现在7和6对称； 但是以前3和8对称，现在是和0对称啊，8到1可不是增加了2啊，是

的，但是再想循环的数的个数是9，8+2=10, 10%9 =1啊，所以这样一想就可以豁然开朗了。

所以就有：由第一列可知， a[i][1]=n-i+1;所以对应的 a[i+j][j] = a[i+j][j-1] + 2 = a[i+j][1] + 2*（i-1）=n+i-j-1

于是产生了如下算法： 当n为偶数时：

void tournament_even(int n) {

int i, j, m;

m = n -1; //如上图所示，取出编号最大的数，构成奇多边形

for(i = 1; i <= m; i++) {

a[i][i] = n; for(j = 1; j <= m/2; j++) { a[n][i] = i; int r = (i + j) % m; if(r ==0) r = m; int k = (i + n - j -1) % m; if(k == 0) k = m; a[r][i] = k; a[k][i] = r; } } }

由对称规律，知道对称轴一旁的顶点的对应点，则比赛对手也同样明确了。所以j只需要取m/2一半就够了。 所以对称轴是i时， a[i][i]=n;在需要知道对称轴这侧的一般就可以了 即： j1 to jm/2的 a[i+j][i]就可以了，所以就有了

同理当n为奇数时相似。

void tournament_odd(int n) {

int i, j;

for(i = 1; i<=n; i++) {

a[i][i] = -1;

for(j = 1; j <= n/2; j++) {

int r = (i + j) % n;

}

}

}

if(r == 0) r = n;

int k = (i + n - j) % n; if(k ==0) k = n; a[r][i] = k; a[k][i] = r;

稍微有一些不同，因为奇数时有轮空，所以轮空时的值就是-1； i>1时， a[i][1]= n-i+2. 所以有a[i+j][i] = i + n - j;

四、 实例的演示： 1. 分治法： N=10时：

N=11时

2. 正多边形构造法： N=10时：

N=11时：

Ps:说明，因为使用c++写的，本来想要用MFC来画界面的，但是因为是单人完成这个作业，觉得MFC也过时了，不如学一些有有潜力的知识。所以没有实现。