循環(huán)賽日程表問題研究

1、學(xué)年論文題 目 循環(huán)賽日程表問題研究 學(xué) 生 指導(dǎo)教師 年 級 2009級 專 業(yè) 軟件工程 系 別 軟件工程 學(xué) 院 計算機(jī)科學(xué)與信息工程學(xué)院哈爾濱師范大學(xué)2012年6月論文提要本文采用分治算法來解決循環(huán)賽日程表的安排問題。通過對問題的詳細(xì)分析，列出1到10個選手的比賽日程表，找出兩條規(guī)則，作為算法實現(xiàn)的依據(jù)，而后采用c語言實現(xiàn)算法，通過測試分析，程序運行結(jié)果正確，運行效率較高。同時也介紹了循環(huán)賽日程表問題的另一種解法多邊形解法，這種方法另辟蹊徑，巧妙地解決了循環(huán)賽日程表問題，運行效率較高。循環(huán)賽日程表問題研究摘要：本文采用分治算法來解決循環(huán)賽日程表的安排問題。根據(jù)算法的設(shè)計結(jié)果，采用c語言

2、實現(xiàn)算法，通過測試分析，程序運行結(jié)果正確，運行效率較高。同時也介紹了循環(huán)賽日程表問題的另一種解法，這種方法另辟蹊徑，想法獨特，運行效率較高。關(guān)鍵詞：循環(huán)賽日程表問題；分治法1、 題目描述 設(shè)有n個運動員要進(jìn)行網(wǎng)球循環(huán)賽。設(shè)計一個滿足以下要求的比賽日程表： （1）每個選手必須與其他n-1個選手各賽一次； （2）每個選手一天只能賽一次； （3）當(dāng)n是偶數(shù)時，循環(huán)賽進(jìn)行n-1天。當(dāng)n是奇數(shù)時，循環(huán)賽進(jìn)行n天。2、 問題分析循環(huán)賽日程表可以采用分治法實現(xiàn)，把一個表格分成4個小表格來處理，每個小表格都是一樣的處理方法，只是參數(shù)不同。分析過程具體如下：1、n=1（表2-1）12.、n=2（表2-2）122

3、13、n=3(1) 添加一個虛擬選手4#，構(gòu)成n+14(2) 4/22，分兩組，每組各自安排（1 2），（3 4）(3) 每組跟另一組分別比賽（拷貝）這是四個人比賽的 （表2-3） 4人賽程1234214334124321(4) 把虛選手置為0 （表2-4）3人賽程1230210330120321 這是三個人比賽的安排4、n=4，見表2-3 5、n=5(1) 加一個虛選手，n+1=6。安排好6個人的比賽后，把第6個人用0表示即得5人的。 (2) 分成兩組(1 2 3) （4 5 6），各3名選手(3) 依照表2-4，安排第1組；按表2-5安排第2組(除0元素外，都加3)（表2-5）456054

4、0660450321 (4) 把表2-5排于表2-4下方（表2-6）123021033012456054066045 (5) 把同一天都有空的兩組安排在一起比賽(按這種安排，肯定每天只有一對空組)。 （表2-7）123421533612456154266345(6) 第一組的(1 2 3)和第2組的(4 5 6)分別比賽。 但是由于(1,4), (2, 5), (3 6)已經(jīng)比賽過了，所以在后面的安排中不能再安排他們比賽。 1 2 3 4 5 6首先，1#只能和5#或6#比賽。(a) 若1#5#，由于3#和6#已經(jīng)比賽過，所以只能安排: 2#6#， 3#4#(b) 若1#6#，由于2#和5#已

5、經(jīng)比賽過，只能安排： 2#4#， 3#5#這樣安排后前三行的后兩列，后三行的后兩列由上面的三行來定：123456215364361245456132542613634521 （表2-8）6人賽程 表2-8就是6名選手的比賽日程安排。將其中的6號作為虛擬選手，把6換成0，即得5名選手的賽程安排表： （表2-9）5人賽程1234502153043012454501325420136345216、n=6，見表2-8。7、n=7, 添加1，n+1=8。8名選手的安排，由4名選手（表2-3）構(gòu)成 （表2-10）8人賽程1234567821436587341278564321876556781234658

6、721437856341287654321將其中的8改成0，即得7名選手的賽程安排。 （表2-11）7人賽程12345670214365073412705643210765567012346507214370563412076543218、n=8 ，見表2-10。9、n=9，由n+110人，將虛選手10號置為0來得到。10、n=10。10人的比賽，分兩組（1 2 3 4 5）和(6 7 8 9 10)各5人。前5人比賽的安排如表2-12 （表2-12）123450215304301245450132542013第2組的5人比賽就是將前5人比賽選手（非0）號對應(yīng)加5 （表2-13）6789100

7、7610809806791091006871097068然后兩組合并，得到表2-14（表2-14）12345021530430124545013254201367891007610809806791091006871097068找兩組中同一天中沒有安排比賽的，安排他們比賽： （表2-15）123456215374381245459132542101367891017610829836791091046871097568由于兩組中：1 2 3 4 5 6 7 8 9 10 按列對應(yīng)的已經(jīng)比賽過一次：16，27，38，49，510。后面再安排兩組選手分別比賽的時候，就不考慮已經(jīng)比賽過的組合。安排兩

8、組選手分別比賽的時候，依照這樣的規(guī)則：1#按遞增順序依次跟沒有比賽過的第2組選手比賽（7，8，9，10各一天）。若1#和x1比賽，則2號從610號中從x1之后開始按增序中找第一個沒有比賽過的選手，跟他比賽(如果x110，則2號從6號開始按增序找)。3、4、5號也如此找。結(jié)果如表2-16所示： （表2-16）10人的賽程安排12345678910215374891063812459106745913210678542101367896789101543276108291543836791021549104687321510975684321觀察表2-16的右上角，發(fā)現(xiàn)如下規(guī)律（表2-8，6人比賽

9、時，也有此規(guī)律）：【規(guī)則一】：每一行數(shù)值從左到右循環(huán)遞增；每一列上也是610（即n/2+1n）循環(huán)遞增（取到最大值10之后，下一個數(shù)字又從6開始取值；而且不包含左上角的塊同一行中取過的值）。第一行第m+1(下標(biāo)從0開始)列的值為(m+1)+1，依次向右遞增；要先處理。其他行上的值要依賴于它的這個取值?！疽?guī)則二】：右下角的塊：因為比賽是兩兩之間進(jìn)行的，所以右下角由右上角決定（比賽的對手是兩個人，因此對應(yīng)的安排要成對）；OK，至此，問題就好解決了，只要按照這個規(guī)律填數(shù)字，就可以得到一種合理的安排。由于我們不是求全部的安排，所以，只要得到這么一個解就可以了。9人比賽，則將表2-16中的10全部用0代

10、替即得。 （表2-17）9人的賽程安排1234567890215374890638124590674591320678542013678967890154327608291543836790215490468732150975684321三、算法設(shè)計n名選手的賽程安排問題：1、如果n為偶數(shù)，可分為兩個n/2人的組，分別比賽，然后兩組間比賽。（1）如果n/2為偶數(shù)，左下角為左上角加n/2來得到，然后左下角拷貝到右上角；左上角拷貝到右下角； （2）如果n/2為奇數(shù)，先安排左下角（除0外都加n/2），然后把同一天都有空的選手安排比賽。然后，右上角要按規(guī)則一來完成，右下角由規(guī)則二來定。2、如果n為奇數(shù)

11、，則加1個選手使n+1成為偶數(shù)。轉(zhuǎn)化成偶數(shù)名選手的賽程安排問題來解決。最后把虛擬選手n+1號所在位置上的值置為0。即完成安排。四、算法改進(jìn)循環(huán)賽要求比賽的每兩個選手都要進(jìn)行一次比賽，而且每個選手每天都要比賽一場。這種題目的解法通常是用分治的思想來做，并且是分治方法解題的經(jīng)典題目。下面的一種受多邊形啟發(fā)的方法，也能巧妙解決循環(huán)賽日程表問題。多邊形解法：有n個選手要進(jìn)行循環(huán)賽，畫n邊形，每個點表示一個選手。 在同一水平線上的選手進(jìn)行比賽。每天的比賽由旋轉(zhuǎn)一次的多邊形決定，每次順時針旋轉(zhuǎn)360/n度。例如：（1）假設(shè)有5名運動員（每天將有一名隊員輪空），則可建立一個如下五邊多邊形： 1 2 5 3

12、4 所以第一天4號輪空，對局為1-2和5-3（2）第二天順時針旋轉(zhuǎn)360/5度，即為： 5 1 4 2 3 所以第二天3號輪空，對局為1-5和2-4 （3）依此類推，直到第五天，多邊形為 2 3 1 4 5 比賽結(jié)束，同理，若比賽人數(shù)為8人，多邊形則為 1 2 8 3 7 4 6 5 依次順時針旋轉(zhuǎn)360/8度7次后，即比賽進(jìn)行7天，即可結(jié)束比賽五、算法實現(xiàn)（1）采用分治法實現(xiàn)代碼（c語言實現(xiàn)）：/* 循環(huán)賽日程安排問題-采用分治法 */#include<stdlib.h>#include<stdio.h>int *A; /int *指針數(shù)組，int *schedule

13、; /int數(shù)組，一維數(shù)組保存二維數(shù)組的數(shù)據(jù)int N =1; /問題的規(guī)模。初始化時會設(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列是選手編號n"); for(i=0;i<row; i+) for(j=0;j<col; j+) printf("%4d", Aij); pri

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

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

16、j; return;/*copyeven:m為偶數(shù)時用,由前1組的m位選手的安排，來構(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. 第1組和第2組 Aij=Ai+mj-m; /把左下角拷貝到右上角 for (i=m;i<2*m;i+)

17、 /3. 對應(yīng)的，第2組和第1組 Aij=Ai-mj-m; /把左上角拷貝到右下角 return;/*copyodd:m為奇數(shù)時用,由前1組的m位選手的安排，來構(gòu)成第2組m位選手 的賽程安排，以及兩組之間的比賽安排。這時和m為偶數(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 /特殊處理：兩個隊各有一名選手有空，安排他們比賽 Ai+mj = i+1; Aij = i+m+1; /*安排

18、兩組選手之間的比賽(后m-1天)*/ for(i=0,j=m+1;j<2*m;j+) Aij= 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+) /2. 觀察得到的規(guī)則一：向下m+12*m循環(huán)遞增 Aij = (Ai-1j+1)%m=0)?Ai-1j+1 :m + (Ai-1j+1)%m; /3. 對應(yīng)第2組的對手也要做相應(yīng)的安排 A

19、(Aij-1) j = i+1; return;/*makecopy:當(dāng)前有m位（偶數(shù)）選手，分成兩組，每組由m/2位選手構(gòu)成 由第一組的m/2位選手的安排來構(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

20、+1); /按照偶數(shù)個選手來求解 replaceVirtual(m+1); /然后把第m+1號虛選手置成0 return ; else /m是偶數(shù)， tournament(m/2); /則先安排第1組的m/2人比賽 makecopy(m); /然后根據(jù)算法，構(gòu)造左下、右下、右上、右下的矩陣 return ;/*endprogram:回收分配的內(nèi)存*/void endprogram() free(schedule); free(A); int main() init(); /初始化 tournament(N);/求解 print(); /打印結(jié)果 endprogram(); /回收內(nèi)存 getc

21、har(); return 0;（2） 多邊形法（C語言實現(xiàn)）：/* 采用多邊形實現(xiàn)法 */#include <stdio.h>#define N 1000int aNN;int bN;inline bool odd(int n) return n & 1;void init() int i; for(i=0;i<N;+i) ai0=i;void tour(int n) an1=n; if(n=1) return; int m=odd(n) ? n : n-1; int i,j,k,r; for(i=1;i<=m;+i) ai1=i; bi=i+1; bm+i=i+1; for(i=1;i<=m;+i) a1i+1=bi; abii+1=1; for(j=1;j<=m/2;+j) k=bi+j; r=bi+m-j; aki+1=r; ari+1=k; void out(int n) if(n=1) printf("1n"); return; int i,j; int m; if(odd(n) m=n+1; else m=n; for(i=1;i<=n;+i) for(j=1;j<=m;+j) if(aij>n) printf("0 "); els