循环赛日程表问题研究.doc

学　年　论　文
题 目 循环赛日程表问题研究
学 生
指导教师
年 级 2009级
专 业 软件工程
系 别 软件工程
学 院 计算机科学与信息工程学院
哈尔滨师范大学
2012年6月
论　文　提　要
本文采用分治算法来解决循环赛日程表的安排问题.通过对问题的详细分析，列出1到10个选手的比赛日程表，找出两条规则,作为算法实现的依据,而后采用c语言实现算法，通过测试分析,程序运行结果正确，运行效率较高。同时也介绍了循环赛日程表问题的另一种解法多边形解法，这种方法另辟蹊径，巧妙地解决了循环赛日程表问题，运行效率较高.
循环赛日程表问题研究
摘　要：本文采用分治算法来解决循环赛日程表的安排问题。根据算法的设计结果，采用c语言实现算法，通过测试分析，程序运行结果正确,运行效率较高。同时也介绍了循环赛日程表问题的另一种解法,这种方法另辟蹊径，想法独特，运行效率较高。
关键词:循环赛日程表问题；分治法
一、 题目描述
设有n个运动员要进行网球循环赛。设计一个满足以下要求的比赛日程表：
（1）每个选手必须与其他n—1个选手各赛一次；
（2）每个选手一天只能赛一次；
（3)当n是偶数时，循环赛进行n—1天。当n是奇数时，循环赛进行n天。
二、 问题分析
循环赛日程表可以采用分治法实现，把一个表格分成4个小表格来处理，每个小表格都是一样的处理方法,只是参数不同.分析过程具体如下：
1、n=1
（表2-1）
1
2。、n=2
(表2—2)
1
2
2
1
3、n=3
(1) 添加一个虚拟选手4＃,构成n+1＝4
（2） 4/2＝2，分两组，每组各自安排（1 2)，(3 4）
(3) 每组跟另一组分别比赛(拷贝）这是四个人比赛的
(表2—3） 4人赛程
1
2
3
4
2
1
4
3
3
4
1
2
4
3
2
1
（4) 把虚选手置为0
（表2—4）3人赛程
1
2
3
0
2
1
0
3
3
0
1
2
0
3
2
1
这是三个人比赛的安排
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
5
6
0
5
4
0
6
6
0
4
5
0
3
2
1
(4） 把表2-5排于表2—4下方
（表2-6）
1
2
3
0
2
1
0
3
3
0
1
2
4
5
6
0
5
4
0
6
6
0
4
5
（5） 把同一天都有空的两组安排在一起比赛（按这种安排,肯定每天只有一对空组）。
（表2—7）
1
2
3
4
2
1
5
3
3
6
1
2
4
5
6
1
5
4
2
6
6
3
4
5
（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#
这样安排后前三行的后两列，后三行的后两列由上面的三行来定：
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
（表2—8）6人赛程
表2—8就是6名选手的比赛日程安排.将其中的6号作为虚拟选手，把6换成0,即得5名选手的赛程安排表：
（表2—9)5人赛程
1
2
3
4
5
0
2
1
5
3
0
4
3
0
1
2
4
5
4
5
0
1
3
2
5
4
2
0
1
3
6
3
4
5
2
1
6、n=6，见表2—8。
7、n=7， 添加1,n+1=8.8名选手的安排,由4名选手（表2—3)构成
（表2—10）8人赛程
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
将其中的8改成0，即得7名选手的赛程安排。
（表2—11）7人赛程
1
2
3
4
5
6
7
0
2
1
4
3
6
5
0
7
3
4
1
2
7
0
5
6
4
3
2
1
0
7
6
5
5
6
7
0
1
2
3
4
6
5
0
7
2
1
4
3
7
0
5
6
3
4
1
2
0
7
6
5
4
3
2
1
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）
1
2
3
4
5
0
2
1
5
3
0
4
3
0
1
2
4
5
4
5
0
1
3
2
5
4
2
0
1
3
第2组的5人比赛就是将前5人比赛选手（非0）号对应加5
（表2-13)
6
7
8
9
10
0
7
6
10
8
0
9
8
0
6
7
9
10
9
10
0
6
8
7
10
9
7
0
6
8
然后两组合并，得到表2-14
(表2—14）
1
2
3
4
5
0
2

1
5
3
0
4
3
0
1
2
4
5
4
5
0
1
3
2
5
4
2
0
1
3
6
7
8
9
10
0
7
6
10
8
0
9
8
0
6
7
9
10
9
10
0
6
8
7
10
9
7
0
6
8
找两组中同一天中没有安排比赛的，安排他们比赛:
(表2—15）
1
2
3
4
5
6
2
1
5
3
7
4
3
8
1
2
4
5
4
5
9
1
3
2
5
4
2
10
1
3

6
7
8
9
10
1
7
6
10
8
2
9
8
3
6
7
9
10
9
10
4
6
8
7
10
9
7
5
6
8
由于两组中：
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＃和x1比赛，则2号从6～10号中从x1之后开始按增序中找第一个没有比赛过的选手,跟他比赛（如果x1＝10,则2号从6号开始按增序找）.3、4、5号也如此找。结果如表2—16所示：
(表2—16）10人的赛程安排
1
2
3
4
5
6
7
8
9
10
2
1
5
3
7
4
8
9
10
6
3
8
1
2
4
5
9
10
6
7
4
5
9
1
3
2
10
6
7
8
5
4
2
10
1
3
6
7
8
9
6
7
8
9
10
1
5
4
3
2
7
6
10
8
2
9
1
5
4
3
8
3
6
7
9
10
2
1
5
4
9
10
4
6
8
7
3
2
1
5
10
9
7
5
6
8
4
3
2
1
观察表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人的赛程安排
1
2
3
4
5
6
7
8
9
0
2
1
5
3
7
4
8
9
0
6
3
8
1
2
4
5
9
0
6
7
4
5
9
1
3
2
0
6
7
8
5
4
2
0
1
3
6
7
8

9
6
7
8
9
0
1
5
4
3
2
7
6
0
8
2
9
1
5
4
3
8
3
6
7
9
0
2
1
5
4
9
0
4
6
8
7
3
2
1
5
0
9
7
5
6
8
4
3
2
1
三、算法设计
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边形,每个点表示一个选手。在同一水平线上的选手进行比赛。每天的比赛由旋转一次的多边形决定，每次顺时针旋转360/n度.例如:
(1）假设有5名运动员（每天将有一名队员轮空）,则可建立一个如下五边多边形：
1 2
5 3
4
所以第一天4号轮空，对局为1—2和5—3
（2）第二天顺时针旋转360/5度，即为:
5 1
4 2
3
所以第二天3号轮空,对局为1—5和2—4
（3）依此类推，直到第五天，多边形为
2 3
1 4
5
比赛结束，同理，若比赛人数为8人，多边形则为
1 2
8 3
7 4
6 5
依次顺时针旋转360/8度7次后，即比赛进行7天，即可结束比赛
五、算法实现
(1)采用分治法实现代码（c语言实现)：
/* 循环赛日程安排问题—采用分治法 ＊/
＃include
＃include是则返回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〈row; i++)
｛
forj=0;jatoi(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〈n；i++） //把A等价为二维数组
{
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〈m—1;i++） //行:对应选手号1~m—1
{
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 （j=m；j〈2＊m；j++）//两组间比赛的安排
{
for (i=0；i〈m；i++) //2。 第1组和第2组
{
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；
｝
/＊copyoddm为奇数时用，由前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〈m；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〈m;i++） //第1组的其他选手的后m-1天的安排
｛
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[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年版。
学年论文（设计）成绩表
论文题目
循环赛日程表问题研究
作　　者

指导教师

职　称
讲师
指
导
教
师
评
语

该生在论文中，详细介绍循环赛日程表问题,在对问题进行详细分析论述的基础上提出了两种风格不同的解题策略,对每种策略都给出了实现算法的具体程序。
该生在完成论文的过程中态度认真积极，能及时与老师沟通，按时完成写作进度。该生基本上具有独立分析问题、解决问题的能力.
论文结构清晰,论述完整,观点明确，表达清楚。文章书写工整，格式及标点规范.符合本科生学年论文标准.
指导教师签字

等级

14