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

问题描述：设有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)每组跟另一组分别比赛（拷贝）这是四个人比赛的安排(表3)4人赛程1234214334124321(4)把虚选手置为0(表4)3人赛程这是三个人比赛的安排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）12302103301203214560(4)把表5排于表4下方（表6）123021033012456054066045(5)把同一天都有空的两组安排在一起比赛(按这种安排，肯定每天只有一对空组，？)。（表7）(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人赛程表8就是6名选手的比赛日程安排。将其中的6号作为虚拟选手，把6换成0，即得5名选手的赛程安排表：540660450321123421533612456154266345123456215364361245456132542613634521（表9）5人赛程6n=6，见表8。7n=7,添加1，n+1=8。8名选手的安排，由4名选手（表3）构成（表10）8人赛程1234567821436587341278564321876556781234658721437856341287654321将其中的8改成0，即得7名选手的赛程安排。（表11）7人赛程12345670214365073412705643210765567012346507214370563412076543218n=8，见表10。9n=9，由n+1＝10人，将虚选手10号置为0来得到。10n=10。10人的比赛，分两组（12345）和(678910)各5人。前5人比赛的安排如表9（表12）123450215304301245450132542013634521123450215304301245450132542013第2组的5人比赛就是将前5人比赛选手（非0）号对应加5（表13）然后两组合并（表14）找两组中同一天中没有安排比赛的，安排他们比赛：（表15）由于两组中：12345678910按列对应的已经比赛过一次：1－6，2－7，3－8，4－9，5－10。后面再安排两组选手分别比赛的时候，就不考虑已经比赛过的组合。安排两组选手分别比赛的时候，依照这样的规则：1#按递增顺序依次跟没有比赛过的第2组选手比赛（7，8，9，10各一天）。若1#和x1比赛，则2号从6~10号中从x1之后开始按6789100761080980679109100687109706812345021530430124545013254201367891007610809806791091006871097068123456215374381245459132542101367891017610829836791091046871097568增序中找第一个没有比赛过的选手，跟他比赛(如果x1＝10，则2号从6号开始按增序找)。3、4、5号也如此找。结果如表16所示：（表16）10人的赛程安排观察表16的右上角，发现如下规律（表8，6人比赛时，也有此规律）：【规则一】：每一行数值从左到右循环递增；每一列上也是6～10（即n/2+1~n）循环递增（取到最大值10之后，下一个数字又从6开始取值；而且不包含左上角的块同一行中取过的值）。第一行第m+1(下标从0开始)列的值为(m+1)+1，依次向右递增；要先处理。其他行上的值要依赖于它的这个取值。【规则二】：右下角的块：因为比赛是两两之间进行的，所以右下角由右上角决定（比赛的对手是两个人，因此对应的安排要成对）；OK，至此，问题就好解决了，只要按照这个规律填数字，就可以得到一种合理的安排。由于我们不是求全部的安排，所以，只要得到这么一个解就可以了。9人比赛，则将表16中的10全部用0代替即得。（表17）9人的赛程安排由上面的分析，可以总结出如下算法：n名选手的赛程安排问题：1如果n为偶数，可分为两个n/2人的组，分别比赛，然后两组间比赛。1.1如果n/2为偶数，左下角为左上角加n/2来得到，然后左下角拷贝到右上角；左上角拷贝到右下角；1.2如果n/2为奇数，先安排左下角（除0外都加n/2），然后把同一天都有空的选手安排比赛。然后，右上角要按规则一来完成，右下角由规则二来定。1234567891021537489106381245910674591321067854210136789678910154327610829154383679102154910468732151097568432112345678902153748906381245906745913206785420136789678901543276082915438367902154904687321509756843212如果n为奇数，则加1个选手使n+1成为偶数。转化成偶数名选手的赛程安排问题来解决。最后把虚拟选手n+1号所在位置上的值置为0。即完成安排。/*exp6_09_3.cpp循环赛日程安排问题-采用分治法*/#includestdlib.h#includestdio.hint**A;//int*指针数组，int*schedule;//int数组，一维数组保存二维数组的数据intN=1;//问题的规模。初始化时会设定//isodd:判断x是否奇数，是则返回1，否则0intisodd(intx){returnx&1;}//print:打印赛程voidprint(){inti,j,row,col;if(isodd(N)){row=N;col=N+1;}else{row=N;col=N;}printf(第1列是选手编号\n);for(i=0;irow;i++){for(j=0;jcol;j++){printf(%4d,A[i][j]);}printf(\n);}}/*init：初始化，设置问题规模N值，分配内存，用schedule指向；把A构造成一个二维数组*/voidinit(){inti,n;charline[100]={'\0'};printf(请输入选手人数：);fgets(line,sizeof(line),stdin);N=atoi(line);if(N=0)exit(-1);if(isodd(N))n=N+1;elsen=N;//schedule是行化的二维数组schedule=(int*)calloc(n*n,sizeof(int));A=(int**)calloc(n,sizeof(int*));if(!schedule||A==NULL)exit(-2);for(i=0;in;i++)//把A等价为二维数组{A[i]=schedule+i*n;A[i][0]=i+1;//初始化这个数组的第一列}return;}/*replaceVirtual:把第m号虚的选手去掉（换做0）*/voidreplaceVirtual(intm){inti,j;for(i=0;im-1;i++)//行：对应选手号1～m-1{for(j=0;j=m;j++)//列:比行要多1A[i][j]=(A[i][j]==m)?0:A[i][j];}return;}/*copyeven:m为偶数时用,由前1组的m位选手的安排，来构成第2组m位选手的赛程安排，以及两组之间的比赛安排*/voidcopyeven(intm){if(isodd(m))return;inti,j;for(j=0;jm;j++)//1.求第2组的安排（+m）{for(i=0;im;i++){A[i+m][j]=A[i][j]+m;}}for(j=m;j2*m;j++)//两组间比赛的安排{for(i=0;im;i++)//2.第1组和第2组{A[i][j]=A[i+m][j-m];//把左下角拷贝到右上角}for(i=m;i2*m;i++)//3.对应的，第2组和第1组{A[i][j]=A[i-m][j-m];//把左上角拷贝到右下角}}return;}/*copyodd:m为奇数时用,由前1组的m位选手的安排，来构成第2组m位选手的赛程安排，以及两组之间的比赛安排。这时和m为偶数时的处理有区别。*/voidcopyodd(intm){inti,j;for(j=0;j=m;j++)//1.求第2组的安排(前m天){for(i=0;im;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;j2*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;im;i++)//第1组的其他选手的后m-1天的安排{for(j=m+1;j2*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为奇数和偶数两种情况*/voidmakecopy(intm){if(isodd(m/2))//m/2为奇数copyodd(m/2);else//m/2为偶数copyeven(m/2);}voidtournament(intm){if(m==1){A[0][0]=1;return;}elseif(isodd(m))//如果m为奇数，则m+1是偶数{tournament(m+1);//按照偶数个选手来求解replaceVirtual(m+1);//然后把第m+1号虚选手置成0return;}else//m是偶数，{tournament(m/2);//则先安排第1组的m/2人比赛makecopy(m);//然后根据算法，构造左下、右下、右上、右下的矩阵}return;}/*endprogram:回收分配的内存*/voidendprogram(){free(schedule);free(A);}intmain(){init();//初始化tournament(N);//求解print();//打印结果endpro