1、问题描述：设有 n 个运动员要进行网球循环赛。设计一个满足以下要求的比赛日程表：（1）每个选手必须与其他 n-1 个选手各赛一次；（2）每个选手一天只能赛一次；（3）当 n 是偶数时，循环赛进行 n-1 天。当 n 是奇数时，循环赛进行 n 天。分析过程：这个问题的解搜索空间是一个 n 的全排列。要求的解是其中的 n 个排列，满足条件：第 1列 n 个元素值按增序排列；每行每列没有相同的数。也是一个幻方（除对角线的和不作要求）的问题。1.n=1（表 1）12. n=2（表 2）1 22 13.n=3,(1) 添加一个虚拟选手 4#，构成 n+14(2) 4/22，分两组，每组各自安排（1 2）
2、 ， （3 4）(3)每组跟另一组分别比赛（拷贝）这是四个人比赛的安排(表 3) 4 人赛程1 2 3 42 1 4 33 4 1 24 3 2 1(4)把虚选手置为 0(表 4)3 人赛程这是三个人比赛的安排4. n=4, 见表 3 5. 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）1 2 3 02 1 0 33 0 1 20 3 2 1(4) 把表 5 排于表 4
3、 下方（表 6）1 2 3 02 1 0 33 0 1 24 5 6 05 4 0 66 0 4 5(5) 把同一天都有空的两组安排在一起比赛( 按这种安排，肯定每天只有一对空组，？)。（表 7）(6) 第一组的 (1 2 3)和第 2 组的(4 5 6)分别比赛。 但是由于(1,4), (2, 5), (3 6)已经比赛过了，所以在后面的安排中不能再安排他们比赛。1 2 34 5 6首先，1#只能和 5#或 6#比赛。(a) 若 1#5#，由于 3#和 6#已经比赛过，所以只能安排: 2#6#， 3#4#(b) 若 1#6#，由于 2#和 5#已经比赛过，只能安排： 2#4#， 3#5#这样
4、安排后前三行的后两列，后三行的后两列由上面的三行来定：（表 8）6 人赛程表 8 就是 6 名选手的比赛日程安排。将其中的 6 号作为虚拟选手，把 6 换成 0，即得 5 名选手的赛程安排表：4 5 6 05 4 0 66 0 4 50 3 2 11 2 3 42 1 5 33 6 1 24 5 6 15 4 2 66 3 4 51 2 3 4 5 62 1 5 3 6 43 6 1 2 4 54 5 6 1 3 25 4 2 6 1 36 3 4 5 2 1（表 9）5 人赛程6 n=6，见表 8。7 n=7, 添加 1，n+1=8。8 名选手的安排，由 4 名选手（表 3）构成（表 10）
5、8 人赛程1 2 3 4 5 6 7 82 1 4 3 6 5 8 73 4 1 2 7 8 5 64 3 2 1 8 7 6 55 6 7 8 1 2 3 46 5 8 7 2 1 4 37 8 5 6 3 4 1 28 7 6 5 4 3 2 1将其中的 8 改成 0，即得 7 名选手的赛程安排。（表 11）7 人赛程1 2 3 4 5 6 7 02 1 4 3 6 5 0 73 4 1 2 7 0 5 64 3 2 1 0 7 6 55 6 7 0 1 2 3 46 5 0 7 2 1 4 37 0 5 6 3 4 1 20 7 6 5 4 3 2 18 n=8 ，见表 10。9 n=9
6、，由 n+110 人，将虚选手 10 号置为 0 来得到。10 n=10。10 人的比赛，分两组（1 2 3 4 5）和(6 7 8 9 10)各 5 人。前 5 人比赛的安排如表 9（表 12）1 2 3 4 5 02 1 5 3 0 43 0 1 2 4 54 5 0 1 3 25 4 2 0 1 36 3 4 5 2 11 2 3 4 5 02 1 5 3 0 43 0 1 2 4 54 5 0 1 3 25 4 2 0 1 3第 2 组的 5 人比赛就是将前 5 人比赛选手（非 0）号对应加 5（表 13）然后两组合并（表 14）找两组中同一天中没有安排比赛的，安排他们比赛：（表 15
7、）由于两组中：1 2 3 4 5 6 7 8 9 10 按列对应的已经比赛过一次：16，27，38，49，510。后面再安排两组选手分别比赛的时候，就不考虑已经比赛过的组合。安排两组选手分别比赛的时候，依照这样的规则：1#按递增顺序依次跟没有比赛过的第 26 7 8 9 10 07 6 10 8 0 98 0 6 7 9 109 10 0 6 8 710 9 7 0 6 81 2 3 4 5 02 1 5 3 0 43 0 1 2 4 54 5 0 1 3 25 4 2 0 1 36 7 8 9 10 07 6 10 8 0 98 0 6 7 9 109 10 0 6 8 710 9 7 0
8、6 81 2 3 4 5 62 1 5 3 7 43 8 1 2 4 54 5 9 1 3 25 4 2 10 1 36 7 8 9 10 17 6 10 8 2 98 3 6 7 9 109 10 4 6 8 710 9 7 5 6 8组选手比赛（7，8，9，10 各一天） 。若 1#和 x1 比赛，则 2 号从 610 号中从 x1 之后开始按增序中找第一个没有比赛过的选手，跟他比赛(如果 x110，则 2 号从 6 号开始按增序找) 。3、4、5 号也如此找。结果如表 16 所示：（表 16）10 人的赛程安排观察表 16 的右上角，发现如下规律（表 8，6 人比赛时，也有此规律）：【规
9、则一】：每一行数值从左到右循环递增；每一列上也是 610（即 n/2+1n）循环递增（取到最大值 10 之后，下一个数字又从 6 开始取值；而且不包含左上角的块同一行中取过的值） 。第一行第 m+1(下标从 0 开始) 列的值为(m+1)+1 ，依次向右递增；要先处理。其他行上的值要依赖于它的这个取值。【规则二】：右下角的块：因为比赛是两两之间进行的，所以右下角由右上角决定（比赛的对手是两个人，因此对应的安排要成对） ；OK，至此，问题就好解决了，只要按照这个规律填数字，就可以得到一种合理的安排。由于我们不是求全部的安排，所以，只要得到这么一个解就可以了。9 人比赛，则将表 16 中的 10
10、全部用 0 代替即得。（表 17）9 人的赛程安排由上面的分析，可以总结出如下算法： n 名选手的赛程安排问题：1 如果 n 为偶数，可分为两个 n/2 人的组，分别比赛，然后两组间比赛。1.1 如果 n/2 为偶数，左下角为左上角加 n/2 来得到，然后左下角拷贝到右上角；左上角拷贝到右下角； 1.2 如果 n/2 为奇数，先安排左下角（除 0 外都加 n/2） ，然后把同一天都有空的选手1 2 3 4 5 6 7 8 9 102 1 5 3 7 4 8 9 10 63 8 1 2 4 5 9 10 6 74 5 9 1 3 2 10 6 7 85 4 2 10 1 3 6 7 8 96 7
11、 8 9 10 1 5 4 3 27 6 10 8 2 9 1 5 4 38 3 6 7 9 10 2 1 5 49 10 4 6 8 7 3 2 1 510 9 7 5 6 8 4 3 2 11 2 3 4 5 6 7 8 9 02 1 5 3 7 4 8 9 0 63 8 1 2 4 5 9 0 6 74 5 9 1 3 2 0 6 7 85 4 2 0 1 3 6 7 8 96 7 8 9 0 1 5 4 3 27 6 0 8 2 9 1 5 4 38 3 6 7 9 0 2 1 5 49 0 4 6 8 7 3 2 1 50 9 7 5 6 8 4 3 2 1安排比赛。然后，右上角要按
12、规则一来完成，右下角由规则二来定。2 如果 n 为奇数，则加 1 个选手使 n+1 成为偶数。转化成偶数名选手的赛程安排问题来解决。最后把虚拟选手 n+1 号所在位置上的值置为 0。即完成安排。/* exp6_09_3.cpp 循环赛日程安排问题-采用分治法 */#include#includeint *A; /int *指针数组，int *schedule; /int 数组，一维数组保存二维数组的数据int N =1; /问题的规模。初始化时会设定/isodd:判断 x 是否奇数，是则返回 1，否则 0int isodd(int x)return x/print:打印赛程void print
13、()int i,j, row, col;if(isodd(N)row=N;col=N+1;elserow=N;col=N;printf(“第 1 列是选手编号n“);for(i=0;irow; i+)for(j=0;jcol; j+)printf(“%4d“, Aij);printf(“n“);/*init：初始化，设置问题规模 N 值，分配内存，用 schedule 指向；把 A 构造成一个二维数组*/void init() int i, n;char line100=0;printf(“请输入选手人数：“);fgets(line,sizeof(line), stdin);N=atoi(li
14、ne); 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 等价为二维数组Ai=schedule+i*n;Ai0=i+1;/初始化这个数组的第一列return;/*replaceVirtual:把第 m 号虚的选手去掉（换做 0）*/void replaceVirtual(int
15、 m)int i,j;for(i=0;im-1;i+) /行：对应选手号 1m-1for (j=0;j=m;j+) /列: 比行要多 1Aij = (Aij=m)?0:Aij;return;/*copyeven:m 为偶数时用,由前 1 组的 m 位选手的安排，来构成第 2 组 m 位选手的赛程安排，以及两组之间的比赛安排 */void copyeven(int m)if(isodd(m) return;int i,j;for (j=0;jm;j+) /1. 求第 2 组的安排（+m）for (i=0;im;i+)Ai+mj=Aij+m;for (j=m;j2*m;j+)/两组间比赛的安排fo
16、r (i=0;im;i+) /2. 第 1 组和第 2 组Aij=Ai+mj-m; /把左下角拷贝到右上角for (i=m;i2*m;i+) /3. 对应的，第 2 组和第 1 组Aij=Ai-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;im;i+)/行if (Aij!=0)A
17、i+mj=Aij+m;else /特殊处理：两个队各有一名选手有空，安排他们比赛Ai+mj = i+1; Aij = i+m+1; /安排两组选手之间的比赛(后 m-1 天)/for(i=0,j=m+1;j2*m;j+)Aij = j+1; /2. 1 号选手的后 m-1 天比赛A (Aij -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+12*m 循环递增Aij
18、= (Ai-1j+1)%m=0)?Ai-1j+1 :m + (Ai-1j+1)%m;/3. 对应第 2 组的对手也要做相应的安排A (Aij-1) j = i+1;return;/*makecopy:当前有 m 位（偶数）选手，分成两组，每组由 m/2 位选手构成由第一组的 m/2 位选手的安排来构成第二组的比赛安排，第一组与第二组的比赛安排。要区分 m/2 为奇数和偶数两种情况*/void makecopy(int m)if (isodd(m/2) /m/2 为奇数copyodd(m/2);else /m/2 为偶数copyeven(m/2);void tournament(int m)if
19、(m=1)A00=1;return ;else if(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:回收分配的内存*/void endprogram()free(schedule);free(A); int main()init(); /初始化 tournament(N);/求解print(); /打印结果endprogram(); /回收内存return 0;
