学年论文
题目循环赛日程表问题研究
学生
指导教师
年级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人赛程
这是三个人比赛的安排
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) 把同一天都有空的两组安排在一起比赛(按这种安排，肯定每天只有一对空组)。
(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人赛程
将其中的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）
然后两组合并，得到表2-14
（表2-14）
找两组中同一天中没有安排比赛的，安排他们比赛：
（表2-15）
由于两组中：
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人的赛程安排
观察表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人的赛程安排
