循環(huán)賽問(wèn)題分析與C語(yǔ)言代碼分治法

1、問(wèn)題描述：設(shè)有n個(gè)運(yùn)動(dòng)員要進(jìn)行網(wǎng)球循環(huán)賽。設(shè)計(jì)一個(gè)滿(mǎn)足以下要求的比賽日程表： （1）每個(gè)選手必須與其他n-1個(gè)選手各賽一次； （2）每個(gè)選手一天只能賽一次； （3）當(dāng)n是偶數(shù)時(shí)，循環(huán)賽進(jìn)行n-1天。當(dāng)n是奇數(shù)時(shí)，循環(huán)賽進(jìn)行n天。分析過(guò)程：這個(gè)問(wèn)題的解搜索空間是一個(gè)n的全排列。要求的解是其中的n個(gè)排列，滿(mǎn)足條件：第1列n個(gè)元素值按增序排列；每行每列沒(méi)有相同的數(shù)。也是一個(gè)幻方（除對(duì)角線(xiàn)的和不作要求）的問(wèn)題。1.n=1（表1）12. n=2（表2）12213.n=3,(1) 添加一個(gè)虛擬選手4#，構(gòu)成n+14(2) 4/22，分兩組，每組各自安排（1 2），（3 4）(3)每組跟另一組分別比賽（拷貝

2、）這是四個(gè)人比賽的安排(表3) 4人賽程1234214334124321(4)把虛選手置為0(表4)3人賽程1230210330120321 這是三個(gè)人比賽的安排4. n=4, 見(jiàn)表3 5. n=5, (1)加一個(gè)虛選手，n+1=6。安排好6個(gè)人的比賽后，把第6個(gè)人用0表示即得5人的。 (2) 分成兩組(1 2 3) （4 5 6），各3名選手 (3) 依照表4，安排第1組；按表5安排第2組(除0元素外，都加3)（表5）4560540660450321 (4) 把表5排于表4下方 （表6）123021033012456054066045 (5) 把同一天都有空的兩組安排在一起比賽(按這種安排，

3、肯定每天只有一對(duì)空組，？)。 （表7）123421533612456154266345 (6) 第一組的(1 2 3)和第2組的(4 5 6)分別比賽。 但是由于(1,4), (2, 5), (3 6)已經(jīng)比賽過(guò)了，所以在后面的安排中不能再安排他們比賽。 1 2 3 4 5 6 首先，1#只能和5#或6#比賽。(a) 若1#5#，由于3#和6#已經(jīng)比賽過(guò)，所以只能安排: 2#6#， 3#4#(b) 若1#6#，由于2#和5#已經(jīng)比賽過(guò)，只能安排： 2#4#， 3#5#這樣安排后前三行的后兩列，后三行的后兩列由上面的三行來(lái)定： （表8）6人賽程12345621536436124545613254

4、2613634521 表8就是6名選手的比賽日程安排。將其中的6號(hào)作為虛擬選手，把6換成0，即得5名選手的賽程安排表：（表9）5人賽程1234502153043012454501325420136345216 n=6，見(jiàn)表8。7 n=7, 添加1，n+1=8。8名選手的安排，由4名選手（表3）構(gòu)成 （表10）8人賽程1234567821436587341278564321876556781234658721437856341287654321 將其中的8改成0，即得7名選手的賽程安排。（表11）7人賽程1234567021436507341270564321076556701234650721

5、4370563412076543218 n=8 ，見(jiàn)表10。9 n=9，由n+110人，將虛選手10號(hào)置為0來(lái)得到。10 n=10。10人的比賽，分兩組（1 2 3 4 5）和(6 7 8 9 10)各5人。前5人比賽的安排如表9（表12）123450215304301245450132542013第2組的5人比賽就是將前5人比賽選手（非0）號(hào)對(duì)應(yīng)加5（表13）67891007610809806791091006871097068然后兩組合并（表14）12345021530430124545013254201367891007610809806791091006871097068 找兩組中同一

6、天中沒(méi)有安排比賽的，安排他們比賽：（表15）123456215374381245459132542101367891017610829836791091046871097568由于兩組中：1 2 3 4 5 6 7 8 9 10 按列對(duì)應(yīng)的已經(jīng)比賽過(guò)一次：16，27，38，49，510。后面再安排兩組選手分別比賽的時(shí)候，就不考慮已經(jīng)比賽過(guò)的組合。安排兩組選手分別比賽的時(shí)候，依照這樣的規(guī)則：1#按遞增順序依次跟沒(méi)有比賽過(guò)的第2組選手比賽（7，8，9，10各一天）。若1#和x1比賽，則2號(hào)從610號(hào)中從x1之后開(kāi)始按增序中找第一個(gè)沒(méi)有比賽過(guò)的選手，跟他比賽(如果x110，則2號(hào)從6號(hào)開(kāi)始按增序找)

7、。3、4、5號(hào)也如此找。結(jié)果如表16所示：（表16）10人的賽程安排12345678910215374891063812459106745913210678542101367896789101543276108291543836791021549104687321510975684321觀察表16的右上角，發(fā)現(xiàn)如下規(guī)律（表8，6人比賽時(shí)，也有此規(guī)律）：【規(guī)則一】：每一行數(shù)值從左到右循環(huán)遞增；每一列上也是610（即n/2+1n）循環(huán)遞增（取到最大值10之后，下一個(gè)數(shù)字又從6開(kāi)始取值；而且不包含左上角的塊同一行中取過(guò)的值）。第一行第m+1(下標(biāo)從0開(kāi)始)列的值為(m+1)+1，依次向右遞增；要先處

8、理。其他行上的值要依賴(lài)于它的這個(gè)取值。【規(guī)則二】：右下角的塊：因?yàn)楸荣愂莾蓛芍g進(jìn)行的，所以右下角由右上角決定（比賽的對(duì)手是兩個(gè)人，因此對(duì)應(yīng)的安排要成對(duì)）；OK，至此，問(wèn)題就好解決了，只要按照這個(gè)規(guī)律填數(shù)字，就可以得到一種合理的安排。由于我們不是求全部的安排，所以，只要得到這么一個(gè)解就可以了。9人比賽，則將表16中的10全部用0代替即得。（表17）9人的賽程安排1234567890215374890638124590674591320678542013678967890154327608291543836790215490468732150975684321由上面的分析，可以總結(jié)出如下算法：

9、n名選手的賽程安排問(wèn)題：1 如果n為偶數(shù)，可分為兩個(gè)n/2人的組，分別比賽，然后兩組間比賽。1.1 如果n/2為偶數(shù)，左下角為左上角加n/2來(lái)得到，然后左下角拷貝到右上角；左上角拷貝到右下角； 1.2 如果n/2為奇數(shù)，先安排左下角（除0外都加n/2），然后把同一天都有空的選手安排比賽。然后，右上角要按規(guī)則一來(lái)完成，右下角由規(guī)則二來(lái)定。2 如果n為奇數(shù)，則加1個(gè)選手使n+1成為偶數(shù)。轉(zhuǎn)化成偶數(shù)名選手的賽程安排問(wèn)題來(lái)解決。最后把虛擬選手n+1號(hào)所在位置上的值置為0。即完成安排。/* exp6_09_3.cpp 循環(huán)賽日程安排問(wèn)題-采用分治法 */#include<stdlib.h>#

10、include<stdio.h>int *A; /int *指針數(shù)組，int *schedule; /int數(shù)組，一維數(shù)組保存二維數(shù)組的數(shù)據(jù)int N =1; /問(wèn)題的規(guī)模。初始化時(shí)會(huì)設(shè)定/isodd:判斷x是否奇數(shù)，是則返回1，否則0int isodd(int x) return x&1;/print:打印賽程void print() int i,j, row, col; if(isodd(N) row=N; col=N+1; else row=N; col=N; printf("第1列是選手編號(hào)n"); for(i=0;i<row; i+) f

11、or(j=0;j<col; j+) printf("%4d", Aij); printf("n"); /*init：初始化，設(shè)置問(wèn)題規(guī)模N值，分配內(nèi)存，用schedule指向； 把A構(gòu)造成一個(gè)二維數(shù)組*/void init() int i, n; char line100='0' printf("請(qǐng)輸入選手人數(shù)："); fgets(line,sizeof(line), stdin); N=atoi(line); if(N<=0) exit(-1); if(isodd(N) n=N+1; else n=N;

12、/schedule是行化的二維數(shù)組 schedule=(int *)calloc(n*n, sizeof(int); A=(int *)calloc(n, sizeof(int *); if(!schedule | A=NULL) exit(-2); for(i=0;i<n;i+) /把A等價(jià)為二維數(shù)組 Ai=schedule+i*n; Ai0=i+1;/初始化這個(gè)數(shù)組的第一列 return;/*replaceVirtual:把第m號(hào)虛的選手去掉（換做0）*/void replaceVirtual(int m) int i,j; for(i=0;i<m-1;i+) /行：對(duì)應(yīng)選手號(hào)

13、1m-1 for (j=0;j<=m;j+) /列: 比行要多1 Aij = (Aij=m)?0:Aij; return;/*copyeven:m為偶數(shù)時(shí)用,由前1組的m位選手的安排，來(lái)構(gòu)成第2組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+) Ai+mj=Aij+m; for (j=m;j<2*m;j+)/兩組間比賽的安排 for (i=0;i<m;i+) /2.

14、第1組和第2組 Aij=Ai+mj-m; /把左下角拷貝到右上角 for (i=m;i<2*m;i+) /3. 對(duì)應(yīng)的，第2組和第1組 Aij=Ai-mj-m; /把左上角拷貝到右下角 return;/*copyodd:m為奇數(shù)時(shí)用,由前1組的m位選手的安排，來(lái)構(gòu)成第2組m位選手 的賽程安排，以及兩組之間的比賽安排。這時(shí)和m為偶數(shù)時(shí)的 處理有區(qū)別。*/void copyodd(int m) int i,j; for (j=0;j<=m;j+) /1. 求第2組的安排(前m天) for (i=0;i<m;i+)/行 if (Aij!=0) Ai+mj=Aij+m; else /

15、特殊處理：兩個(gè)隊(duì)各有一名選手有空，安排他們比賽 Ai+mj = i+1; Aij = i+m+1; /安排兩組選手之間的比賽(后m-1天)/ for(i=0,j=m+1;j<2*m;j+) Aij = j+1; /2. 1號(hào)選手的后m-1天比賽 A (Aij -1) j = i+1; /3. 他的對(duì)手后m-1天的安排 /以下的取值要依賴(lài)于1號(hào)選手的安排，所以之前先安排1號(hào)的賽程 for (i=1;i<m;i+) /第1組的其他選手的后m-1天的安排 for (j=m+1;j<2*m;j+) /2. 觀察得到的規(guī)則一：向下m+12*m循環(huán)遞增 Aij = (Ai-1j+1)%m

16、=0)?Ai-1j+1 :m + (Ai-1j+1)%m; /3. 對(duì)應(yīng)第2組的對(duì)手也要做相應(yīng)的安排 A (Aij-1) j = i+1; return;/*makecopy:當(dāng)前有m位（偶數(shù)）選手，分成兩組，每組由m/2位選手構(gòu)成 由第一組的m/2位選手的安排來(lái)構(gòu)成第二組的比賽安排，第一 組與第二組的比賽安排。要區(qū)分m/2為奇數(shù)和偶數(shù)兩種情況*/void makecopy(int m) if (isodd(m/2) /m/2為奇數(shù) copyodd(m/2); else /m/2為偶數(shù) copyeven(m/2);void tournament(int m) if(m=1) A00=1; return ; else if(isodd(m) /如果m為奇數(shù)，則m+1是偶數(shù) tournament(m+1); /按照偶數(shù)個(gè)選手來(lái)求解 replaceVirtual(m+1); /然后把第m+1號(hào)虛