循环赛赛程安排
一、问题重述
设有n个运动员要进行网球循环赛。设计一个满足下列条件的比赛日程表：
- 每个选手必须与其他n-1个选手各赛一次；
- 每个选手一天只能赛一次；
- 当n是偶数时，循环赛进行n-1天。
- 当n是奇数时，循环赛进行n天。
二、问题分析
1.当n是2的次幂时
$ n=2^k,k=1,2,3,4… $时，此时问题比较简单。按照==分治==的策略，可将所有参赛的选手分为两部分，$ n＝2k $个选手的比赛日程表可以通过为 $ n/2＝2k-1 $ 个选手设计的比赛日程表来决定。递归地执行这种分割，直到只剩下 2 个选手时，比赛日程表的制定就变得很简单：只要让这 2 个选手进行比赛就可以了。再逐步合并子问题的解即可得到原问题的解。
示意图如下：
此时的分治算法如下所示:void tourna(int n) //基本的分治算法
{
if(n==1){a[0][0]=1;return;}
tourna(n/2); //分治
copy(n); //合并
}
void copy(int n)
{
int m=n/2;
for(int i=0;i<m;i++)
for(int j=0;j<m;j++){
//由左上角小块的值算出对应的右上角小块的值
a[i][j+m]=a[i][j]+m;
//由右上角小块的值算出对应的左下角小块的值
a[i+m][j]=a[i][j+m];
//由左上角小块的值算出对应的右下角小块的值
a[i+m][j+m]=a[i][j];
}
}
我们用a[i][j]表示第i支队伍在第j天遇到的对手。
2.当n不是2的次幂时
下面讨论当n不是2的次幂时的情况。
我们发现当n为奇数时，每天必定有一支队伍轮空。此时我们==假定还有一只不存在的队伍与轮空的队伍比赛==，将我们的奇偶数情况的模型统一。此时n的赛程表与偶数n+1时的赛程表是相似的。
比如，当n=4时
| 0 | 1 | 2 | 3 |
|—-|—-|—-|—-|
| 1 | 0 | 3 | 2 |
| 2 | 3 | 0 | 1 |
| 3 | 2 | 1 | 0 |
当n=3时
| 0 | 1 | 2 | / |
|—-|—-|—-|—-|
| 1 | 0 | / | 2 |
| 2 | / | 0 | 1 |
| / | 2 | 1 | 0 |
(删去最后一行)其中“/”表示轮空。
综上，当遇到n为奇数的情况，我们便可以转化为偶数来考虑。
接下来我们遇到问题的难点==矩阵的合并==
当n/2为偶数时，合并比较容易，就像$ n=2^k $那样。
下面我们来考虑n/2为奇数的情况。
此时合并的过程我参考了猪一戒的博客
我们考虑当n=6时的情况。
我们先将6个人分成2组，每组3个人（[0，1,2],[3,4,5]），然后发现3是个奇数，然后在每组中+1个虚拟人：X和Y；这样，每组就变成了4个人，然后将这4个人在除以2，我们就得到了一个两两组合的小的组。
首先来看[0，1]; [2,x]
| 0 | 1 |
|---|---|
| 1 | 0 |
| 2 | x |
|---|---|
| x | 2 |
将这两组合起来：
| 0 | 1 | 2 | x |
|---|---|---|---|
| 1 | 0 | x | 2 |
| 2 | x | 0 | 1 |
| x | 2 | 1 | 0 |
这里要得到3个选手的比赛安排，所以，我们将假想的X去掉，并将它的位置以/代替：
| 0 | 1 | 2 | / |
|---|---|---|---|
| 1 | 0 | / | 2 |
| 2 | / | 0 | 1 |
然后我们也按照这个规律，安排[3,4,5]的日程，得到表格
| 3 | 4 | 5 | / |
|—-|—-|—-|—-|
| 4 | 3 | / | 5 |
| 5 | / | 3 | 4 |
我们得到了两个3x4的矩阵（其中第一列表示每个队伍，实际上只有三天），我们最终想得到6*6（其中第一列表示每个队伍，实际上只有五天）的矩阵。
我们先将上面两个矩阵合并
| 0 | 1 | 2 | / | ||
|---|---|---|---|---|---|
| 1 | 0 | / | 2 | ||
| 2 | / | 0 | 1 | ||
| 3 | 4 | 5 | / | ||
| 4 | 3 | / | 5 | ||
| 5 | / | 3 | 4 |
前三天的比赛已经基本排完了，我们只需要在斜杠/的地方填上相应的比赛。很显然可以让每天轮空的两支队伍比赛。（在程序中没有斜杠表示，还是假想的队伍，方便进行监测）
| 0 | 1 | 2 | 3 | ||
|---|---|---|---|---|---|
| 1 | 0 | 4 | 2 | ||
| 2 | 5 | 0 | 1 | ||
| 3 | 4 | 5 | 0 | ||
| 4 | 3 | 1 | 5 | ||
| 5 | 2 | 3 | 4 |
上面的矩阵中[0,1,2]和[3,4,5]组内已经比完了，组间比了一次，剩下的只需要轮换两次即可得到后两天的比赛情况。
| 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | 0 | 4 | 2 | 5 | 3 |
| 2 | 5 | 0 | 1 | 3 | 4 |
| 3 | 4 | 5 | 0 | 2 | 1 |
| 4 | 3 | 1 | 5 | 0 | 2 |
| 5 | 2 | 3 | 4 | 1 | 0 |
于是我们便可以得到两个奇数矩阵的合并情况。
在程序中，我们的思路不是严格意义上的所谓的“合并”，而是“扩展”。比如对于“合并2个3x4的矩阵”，我们是“将1个3x4的矩阵扩展为6x6的矩阵”（因为这两个3x4的矩阵规格相同，排序顺序一样，所以只需要做一遍）
三、代码展示
（代码里有一些打印行号的printf语句，不知道为啥一去掉就过不了编译，所以没有删掉。。）#include<stdio.h>
#include<stdlib.h>
#include"Check.cpp"
void copy(int n, int **a)//偶数情况
{
//printf("当前行号%05d\n",__LINE__);
int m=n/2;
for(int i=0;i<m;i++){
for(int j=0;j<m;j++){
//由左上角小块的值算出对应的右上角小块的值
a[i][j+m]=a[i][j]+m;
//由右上角小块的值算出对应的左下角小块的值
a[i+m][j]=a[i][j+m];
//由左上角小块的值算出对应的右下角小块的值
a[i+m][j+m]=a[i][j];
}
}
}
void copyodd(int n, int **a) // n/2 为奇数时的合并算法
{
printf("当前行号%05d\n",__LINE__);
int m=n/2;
int b[m];
for(int i=0;i<m;i++){
b[i]=m+i;
b[m+i]=b[i];
}
for(int i=0;i<m;i++){
//由左上角小块的值算出相应的左下角小块的值
for(int j=0;j<m+1;j++){
if(a[i][j]>=m){
a[i][j]=b[i];
a[m+i][j]=(b[i]+m)%n;
} else a[m+i][j]=a[i][j]+m;
}
//由左上角小块的值算出相应的右上角和右下角小块的值
for(int j=1;j<m;j++){
a[i][m+j]=b[i+j];
a[b[i+j]][m+j]=i;
}
}
}
void merge(int n, int **a) //合并算法
{
if((n/2)>1 && (n/2)%2 == 1) copyodd(n,a); //n/2 为奇数时,注意是 (n/2)%2 == 1，n别忘了/2
else copy(n,a);
}
void tournament(int n, int **a) //循环赛算法
{
printf("当前行号%05d\n",__LINE__);
if(n==1){a[0][0]=0;return;}
if(n%2 == 1) {tournament(n+1,a);return;} //n为奇数，分治
tournament(n/2,a); //n为偶数，分治
merge(n,a); //合并
}
main()
{
int n;
scanf("%d",&n);
//创建数组
int **a;
a = (int**)malloc(sizeof(int*)*n);
if(n%2==1){
for(int i=0; i<n+1; i++) a[i] = (int*)malloc(sizeof(int)*(n+1));
} else {
for(int i=0; i<n; i++) a[i] = (int*)malloc(sizeof(int)*n);
}
//生成循坏赛矩阵
tournament(n,a);
//打印
printf("当前行号:%05d\n",__LINE__);
for(int i=0; i<n; i++){
for(int j=1; j<(n%2 == 1 ? n+1 : n); j++){
if(a[i][j]<n) printf("%d ",a[i][j]);
else printf("x ");
}
printf("\n");
}
//检验程序
if(Check(a,n)==1) printf("This gametable is availuable.\n");
else printf("This gametable is unavailuable.\n");
if(n%2 ==1){
for(int i=0; i<n; i++) free(a[i]);
} else {
for(int i=0; i<n+1; i++) free(a[i]);
}
free(a);
}
四、测试程序
测试程序对我们生成的矩阵进行检验。从两个角度进行。
- 每个队伍都要和其他队伍进行一场比赛
- 每个队伍每天仅进行一场比赛
测试程序代码如下int Check(int **a, int n)
{
int column;
if(n%2==1) column=n+1;
else column=n;
int flag=0;
int check=1;//check为0说明不符合条件，停止检验。
//检验每个队伍都与其他队伍比赛
for(int i=0; i<n&&check==1; i++){
for(int k=0; k<n&&check==1; k++){
flag=0;
for(int j=0;j<column&&flag==0;j++){
if(a[i][j] == k) flag=1;
}
if(flag==0) check=0;
}
}
//检验某天是否有队伍重复比赛
int times[n];
for(int j=1; j<column&&check==1; j++){
for(int w=0; w<n; w++) times[w]=0;
for(int i=0; i<n&&check==1; i++){
times[a[i][j]]++;
if(times[a[i][j]]>=2) check==0;
}
}
if(check==1) return 1;
else return 0;
}
五、实验结果
- 当n=6时
- 当n=9时
测试结果均正确。
参考文献
[1]王民川,田永轩.分治法在循环赛日程表设计中的应用[J].光盘技术,2009(05):45-46.