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

循环赛问题分析与C语言代码-分治法.docx问题描述:设有n个运动员要进行网球循环赛。设计一个满足以下要求的比赛tl程表:每个选手必须与其他ml个选手各赛一次;每个选手一天只能赛一次;当n是偶数时,循环赛进行ml天。当n是奇数时,循坏赛进行n天。分析过程:这个问题的解搜索空间是一个n的全排列。要求的解是其中的n个排列,满足条件:第1列n个元素值按增序排列;每行每列没有相同的数。也是一个幻方(除对角线的和不作要求)的问题。=l(表1)=2(表2)=3,添加一个虚拟选手4#,构成n+1=44/2=2,分两组,每组各自安排(12),(34)每组跟另一组分別比赛(拷贝)这是四个人比赛的安排(表3)4人赛程1221344334431221把虚选手置为0(表4)3人赛程这是三个人比赛的安排n=4,见表3n=5,(l)加一个虚选手,n+l=6o安排好6个人的比赛后,把第6个人用0表示即得5人的。分成两组(123)(456),各3名选手依照表4,安排第1组;按表5安排第2组(除0元素外,都加3)(表5)4560540660450321把表5排于表4下方(表6)123021033012456054066045把同一天都有空的两组安排在一起比赛(按这种安排,肯定每天只有一对空组,?)o(表7)123421533612456154266345第一组的(123)和笫2组的(456)分别比赛。但是由于(1,4),⑵5),(36)已经比赛过了,所以在后面的安排中不能再安排他们比赛。1 23456首先,1#只能和5#或6#比赛。若1#-5#,由于3#和6#已经比赛过,所以只能安排:2#—6#, 3#-4#若1#-6#,由于2#和5#己经比赛过,只能安排: 2#-4#,3#-5#这样安排后前三行的后两列,后三行的后两列由上面的三行来定:(表8)6人赛程表8就是6名选手的比赛日程安排。将其中的6号作为虚拟选手,把6换成0,即得5名选手的赛程安排表:(表9)5人赛程6n=6,见表8。7n=7,添加1,n+l=8o8名选手的安排,由4名选手(表3)构成(表10)8人赛程将其中的8改成0,即得7名选手的赛程安排。(表11)7人赛程12345670214365073412705643210765567012346507214370563412076|5|43218n=8,见表10。9n=9,由n+l=10人,将虚选手10号置为0來得到。10n=10o10人的比赛,分两组(12345)和(678910)各5人。前5人比赛的安排如表9(表12)12345421530301245450132542013第2组的5人比赛就是将前5人比赛选手(非0)号对应加5(表13)67891007610809806791091006871097068然后两组合并(表14)12345021530430124545013254201367891007610809806791091006871097068找两组中同一天中没有安排比赛的,安排他们比赛:(表15)123456215374381245459132542101367891017610829836791091046871097568由于两组中:12 3 4 56 7 8 9 10按列对应的已经比赛过一次:1—6,2-7,3—8,4-9,5—10。后而再安排两组选手分别比赛的时候,就不