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

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

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

3、对空组，？)。(表 7)123421533612456154266345(6) 第一组的(1 2 3)和第2组的(4 5 6)分别比赛。但是由于(1,4), (2, 5), (3 6)已经比赛过 了，所以在后面的安排中不能再安排他们比赛。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人赛程123450215304301245450132542013634521将其中的8改成0,即得7名选手的赛程安排。（表11） 7人赛程12345670214365073412705643210765567012346507214370563412076543218 n=8，见表 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人比赛的安排如表 9 （表 12）123450215

5、304301245450132542013第2组的5人比赛就是将前5人比赛选手（非0）号对应加5（表 13）67891007610809806791091006871097068然后两组合并（表 14）12345021530430124545013254201367891007610809806791091006871097068找两组中同一天中没有安排比赛的，安排他们比赛:（表 15）123456215374381245459132542101367891017610829836791091046871097568由于两组中：123 456 78 910按列对应的已经比赛过一次：1 6, 2

6、-7, 3 8, 4-9, 5 10。后面再安排两组选手分别比赛的时候，就不考虑已经比赛过的组合。安排两组选手分别比赛的时候，依照这样的规则：1#按递增顺序依次跟没有比赛过的第2组选手比赛（7, 8, 9, 10各一天）。若1#和X1比赛，贝y 2号从610号中从X1之后开始按增序中找第一个没有比赛过的选手，跟他比赛（如果X1 = 10,则2号从6号开始按增序找）。3、4、5号也如此找。结果如表 16所示：（表16）10人的赛程安排1234567891021537489106381245910674591321067854210136789678910154327610829154383679

7、1021549104687321510975684321观察表16的右上角，发现如下规律（表8，6人比赛时，也有此规律）：【规则一】：每一行数值从左到右循环递增；每一列上也是610 （即n/2+1n ）循环递增（取到最大值10之后，下一个数字又从 6开始取值；而且不包含左上角的块同一行中取过 的值）。第一行第 m+1（下标从0开始）列的值为（m+1）+1，依次向右递增；要先处理。其他 行上的值要依赖于它的这个取值。【规则二】：右下角的块：因为比赛是两两之间进行的，所以右下角由右上角决定（比赛的 对手是两个人，因此对应的安排要成对）；OK，至此，问题就好解决了，只要按照这个规律填数字，就可以得到

8、一种合理的安排。 由于我们不是求全部的安排，所以，只要得到这么一个解就可以了。9人比赛，则将表16中的10全部用0代替即得。（表17） 9人的赛程安排123456789021537489063812459067459132067854201367896789015432760829154383679021549046873215由上面的分析，可以总结出如下算法：n名选手的赛程安排问题：1 如果n为偶数，可分为两个 n/2人的组，分别比赛，然后两组间比赛。1.1 如果n/2为偶数，左下角为左上角加n/2来得到，然后左下角拷贝到右上角；左上角拷贝到右下角；1.2 如果n/2为奇数，先安排左下角（除

9、 0外都加n/2），然后把同一天都有空的选手 安排比赛。然后，右上角要按规则一来完成，右下角由规则二来定。2 如果 n 为奇数，则加 1 个选手使 n+1 成为偶数。转化成偶数名选手的赛程安排问题来 解决。最后把虚拟选手 n+1 号所在位置上的值置为 0。即完成安排。/* exp6_09_3.cpp 循环赛日程安排问题 - 采用分治法 */ #include<stdlib.h>#include<stdio.h>int * A;int * schedule;int N =1;/int * 指针数组，/int 数组，一维数组保存二维数组的数据 / 问题的规模。初始化时会设定

10、/isodd: 判断 x 是否奇数，是则返回 1，否则 0 int isodd( int x)return x&1;/print: 打印赛程void print()int i,j, row, col;if (isodd(N)row =N;col =N+1;elserow =N;col =N;printf( "第 1 列是选手编号 n" );for (i =0;i <row; i+)for (j =0;j <col; j+)printf("%4d" , A ij);printf( "n" );/*init ：初始化，

11、设置问题规模 N 值，分配内存，用 schedule 指向； 把 A 构造成一个二维数组*/void init() int i, n; char line 100= '0' ;printf(" 请输入选手人数： ");fgets(line, sizeof (line), stdin);N =atoi(line); if (N<=0) exit(-1); if (isodd(N) n =N+1; else n =N;/schedule 是行化的二维数组schedule=( int * )calloc(n *n, sizeof ( int ); A=( i

12、nt * )calloc(n, sizeof (int *);if (!schedule | A=NULL) exit(-2);for (i =0;i <n;i+) / 把 A 等价为二维数组 A i=schedule +i *n;A i0=i +1; / 初始化这个数组的第一列 return ;/*replaceVirtual:把第m号虚的选手去掉(换做 0) */void replaceVirtual( int m)int i,j;for (i =0;i <m-1;i+)/ 行：对应选手号1 m-1for (j =0;j <=m;j+) / 列: 比行要多 1A ij =

13、 (A ij=m)?0:A ij;return ;2 组 m 位选手/*copyeven:m 为偶数时用，由前1组的m位选手的安排，来构成第 的赛程安排，以及两组之间的比赛安排 */void copyeven( int m)if (isodd(m) return ;int i，j;for (j =0;j <m;j+)/1. 求第 2 组的安排( +m)for (i =0;i <m;i+)A i +mj=A ij+m;for (j =m;j <2* m;j+) / 两组间比赛的安排for (i =0;i <m;i+) /2. 第 1 组和第 2 组A ij=A i +mj

14、-m; / 把左下角拷贝到右上角for (i =m;i <2* m;i+) /3. 对应的，第 2组和第 1 组A ij=A i-mj-m; / 把左上角拷贝到右下角return ;/*copyodd:m 为奇数时用,由前1组的m位选手的安排，来构成第2组m位选手的赛程安排，以及两组之间的比赛安排。这时和m为偶数时的处理有区别。*/void copyodd( int m)int i,j;for (j =0;j <=m;j+)/1. 求第 2 组的安排(前 m天)for (i =0;i <m;i+) / 行if (A ij!=0)Ai +mj=A ij+ m ;else / 特

15、殊处理：两个队各有一名选手有空，安排他们比赛Ai+mj = i +1;Aij= i +m+1;/安排两组选手之间的比赛(后 m-1 天)/for (i =0,j =m+1;j <2*m;j+)A ij= j +1;/2. 1 号选手的后 m-1 天比赛A (Aij -1) j = i +1;3.他的对手后 m-1 天的安排/ 以下的取值要依赖于 1 号选手的安排，所以之前先安排 1 号的赛程for (i =1;i <m;i+) / 第 1 组的其他选手的后 m-1 天的安排for (j =m+1;j <2* m;j+)112.观察得到的规则一：向下m+12*m循环递增A ij

16、 = (A i-1 j+ 1 )%m=0)?A i-1 j+ 1 :m + (A i- 1 j+ 1 )%m;/3.对应第 2 组的对手也要做相应的安排A (A ij -1) j = i +1;return/*makecopy:当前有m位(偶数)选手，分成两组，每组由 m/2位选手构成 由第一组的 m/2 位选手的安排来构成第二组的比赛安排，第一 组与第二组的比赛安排。要区分m/2为奇数和偶数两种情况*/void makecopy( int m)if (isodd(m/2)copyodd(m/2);elsecopyeven(m/2);void tournament( intif (m=1)A 00=1 ;return ;else if (isodd(m)tournament(m +1); replaceVirtual(m+1);return ;m)/m/2 为奇数/m/2 为偶数/如果m为奇数，则 m+1是偶数/ 按照偶数个选手