循环赛日程表问题研究

学年论文

题目循环赛日程表问题研究

学生

指导教师

年级2009级

专业软件工程

系别软件工程

学院计算机科学与信息工程学院

哈尔滨师范大学

2012年6月

论文提要

本文采用分治算法来解决循环赛日程表的安排问题。通过对问题的详细分析，列出1到10个选手的比赛日程表，找出两条规则，作为算法实现的依据，而后采用c语言实现算法，通过测试分析，程序运行结果正确，运行效率较高。同时也介绍了循环赛日程表问题的另一种解法多边形解法，这种方法另辟蹊径，巧妙地解决了循环赛日程表问题，运行效率较高。

循环赛日程表问题研究

摘 要：本文采用分治算法来解决循环赛日程表的安排问题。根据算法的设计结果，采用c 语言实现算法，通过测试分析，程序运行结果正确，运行效率较高。同时也介绍了循环赛日程表问题的另一种解法，这种方法另辟蹊径，想法独特，运行效率较高。

关键词：循环赛日程表问题；分治法

一、题目描述

设有n 个运动员要进行网球循环赛。设计一个满足以下要求的比赛日程表： （1）每个选手必须与其他n-1个选手各赛一次； （2）每个选手一天只能赛一次；

（3）当n 是偶数时，循环赛进行n-1天。当n 是奇数时，循环赛进行n 天。

二、问题分析

循环赛日程表可以采用分治法实现，把一个表格分成4个小表格来处理，每个小表格都是一样的处理方法，只是参数不同。分析过程具体如下：

1、n=1

（表2-1）

2.、n=2

（表2-2）

3、n=3

(1) 添加一个虚拟选手4#，构成n+1＝4

(2) 4/2＝2，分两组，每组各自安排（1 2），（3 4） (3) 每组跟另一组分别比赛（拷贝）这是四个人比赛的

（表2-3） 4人赛程

(4) 把虚选手置为0

（表2-4）3人赛程

1

21

4321

这是三个人比赛的安排

4、n=4，见表2-3

5、n=5

(1) 加一个虚选手，n+1=6。安排好6个人的比赛后，把第6个人用0表示即得5人的。

(2) 分成两组(1 2 3) （4 5 6），各3名选手

(3) 依照表2-4，安排第1组；按表2-5安排第2组(除0元素外，都加3)

（表2-5）

(4) 把表2-5排于表2-4下方

（表2-6）

(5) 把同一天都有空的两组安排在一起比赛(按这种安排，肯定每天只有一对空组)。

（表2-7）

0321

0651

32065

432165

(6) 第一组的(1 2 3)和第2组的(4 5 6)分别比赛。 但是由于(1,4), (2, 5), (3 6)已经比赛过了，所以在后面的安排中不能再安排他们比赛。

1 2 3

4 5 6

首先，1#只能和5#或6#比赛。

(a) 若1#－5#，由于3#和6#已经比赛过，所以只能安排: 2#－6#， 3#－4#

(b) 若1#－6#，由于2#和5#已经比赛过，只能安排： 2#－4#， 3#－5#

这样安排后前三行的后两列，后三行的后两列由上面的三行来定：

表2-8就是6名选手的比赛日程安排。将其中的6号作为虚拟选手，把6换成0，即得5名选手的赛程安排表：

（表2-9）5人赛程

6、n=6，见表2-8。

7、n=7, 添加1，n+1=8。8名选手的安排，由4名选手（表2-3）构成 （表2-10）8人

赛程

645

231

04523

1

876543

将其中的8改成0，即得7名选手的赛程安排。

（表2-11）7人赛程

8、n=8 ，见表2-10。

9、n=9，由n+1＝10人，将虚选手10号置为0来得到。

10、n=10。10人的比赛，分两组（1 2 3 4 5）和(6 7 8 9 10)各5人。前5人比赛的安排如表2-12

（表2-12）

第2组的5人比赛就是将前5人比赛选手（非0）号对应加5 （表2-13）

21

0765

43

21

04523

9

然后两组合并，得到表2-14

（表2-14）

找两组中同一天中没有安排比赛的，安排他们比

赛：

（表

2-15）

1

7

8

4

5

230

9

1

7

8

6

4

5

231

由于两组中：

1 2 3 4 5 6 7 8 9 10

按列对应的已经比赛过一次：1－6，2－7，3－8，4－9，5－10。后面再安排两组选手分别比赛的时候，就不考虑已经比赛过的组合。

安排两组选手分别比赛的时候，依照这样的规则：1#按递增顺序依次跟没有比赛过的第2组选手比赛（7，8，9，10各一天）。若1#和x 1比赛，则2号从6~10号中从x 1之后开始按增序中找第一个没有比赛过的选手，跟他比赛(如果x 1＝10，则2号从6号开始按增序找)。3、4、5号也如此找。结果如表2-16所示：

（表2-16）10人的赛程安排

9

17

8

1

6

7

8

9

2

3

观察表2-16的右上角，发现如下规律（表2-8，6人比赛时，也有此规律）： 【规则一】：每一行数值从左到右循环递增；每一列上也是6～10（即n/2+1~n ）循环递增（取到最大值10之后，下一个数字又从6开始取值；而且不包含左上角的块同一行中取过的值）。第一行第m+1(下标从0开始)列的值为(m+1)+1，依次向右递增；要先处理。其他行上的值要依赖于它的这个取值。

【规则二】：右下角的块：因为比赛是两两之间进行的，所以右下角由右上角决定（比赛的对手是两个人，因此对应的安排要成对）；

OK ，至此，问题就好解决了，只要按照这个规律填数字，就可以得到一种合理的安排。

由于我们不是求全部的安排，所以，只要得到这么一个解就可以了。 9人比赛，则将表2-16中的10全部用0代替即得。

（表2-17）9人的赛程安排

4

5

1

0678923451

三、算法设计

n名选手的赛程安排问题：

1、如果n为偶数，可分为两个n/2人的组，分别比赛，然后两组间比赛。

（1）如果n/2为偶数，左下角为左上角加n/2来得到，然后左下角拷贝到右上角；左上角拷贝到右下角；

（2）如果n/2为奇数，先安排左下角（除0外都加n/2），然后把同一天都有空的选手安排比赛。然后，右上角要按规则一来完成，右下角由规则二来定。

2、如果n为奇数，则加1个选手使n+1成为偶数。转化成偶数名选手的赛

程安排问题来解决。最后把虚拟选手n+1号所在位置上的值置为0。即完成安排。

四、算法改进

循环赛要求比赛的每两个选手都要进行一次比赛，而且每个选手每天都要比赛一场。这种题目的解法通常是用分治的思想来做，并且是分治方法解题的经典题目。下面的一种受多边形启发的方法，也能巧妙解决循环赛日程表问题。

多边形解法：有n个选手要进行循环赛，画n边形，每个点表示一个选手。在同

五、算法实现

（1）采用分治法实现代码（c语言实现）：

/* 循环赛日程安排问题-采用分治法*/

#include

#include

int **A; //int *指针数组，

int *schedule; //int数组，一维数组保存二维数组的数据

int N =1; //问题的规模。初始化时会设定

//isodd:判断x是否奇数，是则返回1，否则0

int isodd(int x)

{

return x&1;

}

//print:打印赛程

void print()

{

int i,j, row, col;

if(isodd(N))

{

row=N;

col=N+1;

}

else

{

row=N;

col=N;

}

printf("第1列是选手编号\n");

for(i=0;i

{

for(j=0;j

{

printf("%4d", A[i][j]);

}

printf("\n");

}

}

/*init：初始化，设置问题规模N值，分配内存，用schedule指向；

把A构造成一个二维数组*/

void init()

{ int i, n;

char line[100]={'\0'};

printf("请输入选手人数：");

fgets(line,sizeof(line), stdin);

N=atoi(line);

if(N<=0) exit(-1);

if(isodd(N))

n=N+1;

else

n=N;

//schedule是行化的二维数组

schedule=(int *)calloc(n*n, sizeof(int));

A=(int **)calloc(n, sizeof(int *));

if(!schedule || A==NULL) exit(-2);

for(i=0;i

{

A[i]=schedule+i*n;

A[i][0]=i+1;//初始化这个数组的第一列

}

return;

}

/*replaceVirtual:把第m号虚的选手去掉（换做0）*/

void replaceVirtual(int m)

{

int i,j;

for(i=0;i

{

for (j=0;j<=m;j++) //列: 比行要多1

A[i][j] = (A[i][j]==m)?0:A[i][j];

}

return;

}

/*copyeven:m为偶数时用,由前1组的m位选手的安排，来构成第2组m位选手

的赛程安排，以及两组之间的比赛安排*/ void copyeven(int m)

{

if(isodd(m)) return;

int i,j;

for (j=0;j

{

for (i=0;i

{

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

}

}

for (j=m;j<2*m;j++)//两组间比赛的安排

{

for (i=0;i

{

A[i][j]=A[i+m][j-m]; //把左下角拷贝到右上角

}

for (i=m;i<2*m;i++) //3. 对应的，第2组和第1组

{

A[i][j]=A[i-m][j-m]; //把左上角拷贝到右下角

}

}

return;

}

/*copyodd:m为奇数时用,由前1组的m位选手的安排，来构成第2组m位选手

的赛程安排，以及两组之间的比赛安排。这时和m为偶数时的

处理有区别。

*/

void copyodd(int m)

{

int i,j;

for (j=0;j<=m;j++) //1. 求第2组的安排(前m天)

{

for (i=0;i

{

if (A[i][j]!=0)

{

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

}

else //特殊处理：两个队各有一名选手有空，安排他们比赛

{

A[i+m][j] = i+1;

A[i][j] = i+m+1;

}

}

}

/*安排两组选手之间的比赛(后m-1天)*/

for(i=0,j=m+1;j<2*m;j++)

{

A[i][j]= j+1; //2. 1号选手的后m-1天比赛

A[ (A[i][j] -1) ][j] = i+1; //3. 他的对手后m-1天的安排

}

//以下的取值要依赖于1号选手的安排，所以之前先安排1号的赛程

for (i=1;i

{

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

{//2. 观察得到的规则一：向下m+1~2*m循环递增

A[i][j] = ((A[i-1][j]+1)%m==0)?A[i-1][j]+1 :m + (A[i-1][j]+1)%m;

//3. 对应第2组的对手也要做相应的安排

A[ (A[i][j]-1) ][j] = i+1;

}

}

return;

}

/*makecopy:当前有m位（偶数）选手，分成两组，每组由m/2位选手构成

由第一组的m/2位选手的安排来构成第二组的比赛安排，第一

组与第二组的比赛安排。要区分m/2为奇数和偶数两种情况*/

void makecopy(int m)

{

if (isodd(m/2)) //m/2为奇数

copyodd(m/2);

else //m/2为偶数

copyeven(m/2);

}

void tournament(int m)

{

if(m==1)

{

A[0][0]=1;

return ;

}

else if(isodd(m)) //如果m为奇数，则m+1是偶数

{

tournament(m+1); //按照偶数个选手来求解

replaceVirtual(m+1); //然后把第m+1号虚选手置成0

return ;

}

else //m是偶数，

{

tournament(m/2); //则先安排第1组的m/2人比赛

makecopy(m); //然后根据算法，构造左下、右下、右上、右下的矩阵

}

return ;

}

/*endprogram:回收分配的内存*/

void endprogram()

{

free(schedule);

free(A);

}

int main()

{

init(); //初始化

tournament(N);//求解

print(); //打印结果

endprogram(); //回收内存

getchar();

return 0;

}

（2）多边形法（C语言实现）：

/* 采用多边形实现法*/

#include

#define N 1000

int a[N][N];

int b[N];

inline bool odd(int n)

{

return n & 1;

}

void init()

{

int i;

for(i=0;i

a[i][0]=i;

}

void tour(int n)

{

a[n][1]=n;

if(n==1) return;

int m=odd(n) ? n : n-1;

int i,j,k,r;

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

{

a[i][1]=i;

b[i]=i+1;

b[m+i]=i+1;

}

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

{

a[1][i+1]=b[i];

a[b[i]][i+1]=1;

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

{

k=b[i+j];

r=b[i+m-j];

a[k][i+1]=r;

a[r][i+1]=k;

}

}

}

void out(int n)

{

if(n==1)

{

printf("1\n");

return;

}

int i,j;

int m;

if(odd(n))

m=n+1;

else

m=n;

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

{

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

{

if(a[i][j]>n)

printf("0 ");

else

printf("%d ",a[i][j]);

}

printf("\n");

}

}

int main()

{

int n;

init();

while(scanf("%d",&n),n)

{

tour(n);

out(n);

}

return 0;

}

六、总结

算法实现1采用的分治算法，其基本思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。这是循环赛日程表问题解决方法的经典形式，但是比较复杂，分析起来比较繁琐。而算法实现2采用的多边形解法，其基本思想是，对于n个选手进行的循环赛，画出一个n边形，每个点表示一个选手，在同一水平线上的选手进行比赛，每天的比赛由旋转一次的多边形决定，每次顺时针旋转360/n 度。，该解法很巧妙，思想独特，并且容易理解。两者效率差不多，在整体上多边形解法比分治法较优。多边形解法给了我们一个良好的启发，对于一个复杂的问题，往往会有一个很简单的解决方法。

参考文献：

[1] 王晓东：计算机算法分析与设计，电子工业出版社，2006年版。

[2] 严蔚敏吴伟民：数据结构（C语言版），清华大学出版社，1997年版。

学年论文（设计）成绩表