循环赛问题分析与C语言代码-分治法

《循环赛问题分析与C语言代码-分治法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.问题描述：设有n个运动员要进行网球循环赛。设计一个满足以下要求的比赛日程表：（1）每个选手必须与其他n-1个选手各赛一次；（2）每个选手一天只能赛一次；（3）当n是偶数时，循环赛进行n-1天。当n是奇数时，循环赛进行n天。分析过程：这个问题的解搜索空间是一个n的全排列。要求的解是其中的n个排列，满足条件：第1列n个元素值按增序排列；每行每列没有相同的数。也是一个幻方（除对角线的和不作要求）的问题。1.n=1（表1）12.n=2（表2）12213.n=3,(1)添加一个虚拟选手4#，构成n+1＝4(2)4/2＝2，分两组，每组各自安排（12），（34）(3)每组跟另一组分别比赛（拷贝

2、）这是四个人比赛的安排(表3)4人赛程1234214334124321(4)把虚选手置为0(表4)3人赛程1230210330120321这是三个人比赛的安排4.n=4,见表35.n=5,(1)加一个虚选手，n+1=6。安排好6个人的比赛后，把第6个人用0表示即得5人的。(2)分成两组(123)（456），各3名选手(3)依照表4，安排第1组；按表5安排第2组(除0元素外，都加3)（表5）4560....540660450321(4)把表5排于表4下方（表6）123021033012456054066045(5)把同一天都有空的两组安排在一起比赛(按这种安排，肯定每天只有一对空组，？

3、)。（表7）123421533612456154266345(6)第一组的(123)和第2组的(456)分别比赛。但是由于(1,4),(2,5),(36)已经比赛过了，所以在后面的安排中不能再安排他们比赛。123456首先，1#只能和5#或6#比赛。(a)若1#－5#，由于3#和6#已经比赛过，所以只能安排:2#－6#，3#－4#(b)若1#－6#，由于2#和5#已经比赛过，只能安排：2#－4#，3#－5#这样安排后前三行的后两列，后三行的后两列由上面的三行来定：（表8）6人赛程123456215364361245456132542613634521表8就是6名选手的比赛日程安排。将

4、其中的6号作为虚拟选手，把6换成0，即得5名选手的赛程安排表：....（表9）5人赛程1234502153043012454501325420136345216n=6，见表8。7n=7,添加1，n+1=8。8名选手的安排，由4名选手（表3）构成（表10）8人赛程1234567821436587341278564321876556781234658721437856341287654321将其中的8改成0，即得7名选手的赛程安排。（表11）7人赛程12345670214365073412705643210765567012346507214370563412076543218n=8，见

5、表10。9n=9，由n+1＝10人，将虚选手10号置为0来得到。10n=10。10人的比赛，分两组（12345）和(678910)各5人。前5人比赛的安排如表9（表12）123450215304301245450132542013....第2组的5人比赛就是将前5人比赛选手（非0）号对应加5（表13）67891007610809806791091006871097068然后两组合并（表14）12345021530430124545013254201367891007610809806791091006871097068找两组中同一天中没有安排比赛的，安排他们比赛：（表15）12345

6、6215374381245459132542101367891017610829836791091046871097568由于两组中：12345678910按列对应的已经比赛过一次：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号也如此找。结果如表16所示：

7、（表16）10人的赛程安排12345678910215374891063812459106745913210678542101367896789101543276108291543836791021549104687321510975684321观察表16的右上角，发现如下规律（表8，6人比赛时，也有此规律）：【规则一】：每一行数值从左到右循环递增；每一列上也是6～10（即n/2+1~n）循环递增（取到最大值10之后，下一个数字又从6开始取值；而且不包含左