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

问题描述:设有n个运动员要进行网球循环赛。设计一个满足以下要求的比赛日程表:()每个选手必须与其他n-个选手各赛一次;()每个选手一天只能赛一次;()当n是偶数时,循环赛进行n-天。当n是奇数时,循环赛进行n天。分析过程:这个问题的解搜索空间是一个n的全排列。要求的解是其中的n个排列,满足条件:第列n个元素值按增序排列;每行每列没有相同的数。也是一个幻方(除对角线的和不作要求)的问题。.n=(表).n=(表).n=,()添加一个虚拟选手#,构成n+=()/=,分两组,每组各自安排(),()()每组跟另一组分别比赛(拷贝)这是四个人比赛的安排(表)人赛程 ()把虚选手置为(表)=,=,()加一个虚选手,n+=。安排好个人的比赛后,把第个人用表示即得人的。()分成两组()(),各名选手 ()依照表,安排第组;按表安排第组(除元素外,都加)(表)()把表排于表下方(表)()把同一天都有空的两组安排在一起比赛(按这种安排,肯定每天只有一对空组,?)。(表)()第一组的()和第组的()分别比赛。但是由于(,),(,),()已经比赛过了,所以在后面的安排中不能再安排他们比赛。首先,#只能和#或#比赛。若#-#,由于#和#已经比赛过,所以只能安排:#-#,#-#若#-#,由于#和#已经比赛过,只能安排:#-#,#-#这样安排后前三行的后两列,后三行的后两列由上面的三行来定:(表)人赛程表就是名选手的比赛日程安排。将其中的号作为虚拟选手,把换成,即得名选手的赛程安排表:(表)人赛程n=,见表。n=,添加,n+=。名选手的安排,由名选手(表)构成(表)人赛程将其中的改成,即得名选手的赛程安排。(表)人赛程n=,见表。n=,由n+=人,将虚选手号置为来得到。n=。人的比赛,分两组()和()各人。前人比赛的安排如表(表)第组的人比赛就是将前人比赛选手(非)号对应加(表)然后两组合并(表)