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

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

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

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

4、321 （4） 把表25排于表2-4下方（表26）123021033012456054066045（5） 把同一天都有空的兩組安排在一起比賽（按這種安排，肯定每天只有一對(duì)空組）。 (表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） 若15，由于3和6已經(jīng)比賽過，所以只能安排： 26， 34#(b） 若16，由于2和5已經(jīng)比賽過，只能安排： 24， 3#5這樣安排后前三

5、行的后兩列，后三行的后兩列由上面的三行來定:123456215364361245456132542613634521 (表28）6人賽程表2-8就是6名選手的比賽日程安排。將其中的6號(hào)作為虛擬選手，把6換成0,即得5名選手的賽程安排表： （表29）5人賽程1234502153043012454501325420136345216、n=6，見表28。7、n=7， 添加1,n+1=8。8名選手的安排，由4名選手（表2-3）構(gòu)成 (表2-10）8人賽程1234567821436587341278564321876556781234658721437856341287654321將其中的8改成0，即得

6、7名選手的賽程安排. (表2-11）7人賽程12345670214365073412705643210765567012346507214370563412076543218、n=8 ，見表2-10.9、n=9，由n+110人，將虛選手10號(hào)置為0來得到。10、n=10。10人的比賽，分兩組(1 2 3 4 5)和（6 7 8 9 10)各5人。前5人比賽的安排如表212 （表2-12）123450215304301245450132542013第2組的5人比賽就是將前5人比賽選手（非0）號(hào)對(duì)應(yīng)加5 （表213)67891007610809806791091006871097068然后兩組合并

7、，得到表214（表214)12345021530430124545013254201367891007610809806791091006871097068找兩組中同一天中沒有安排比賽的，安排他們比賽： (表2-15）123456215374381245459132542101367891017610829836791091046871097568由于兩組中:1 2 3 4 5 6 7 8 9 10 按列對(duì)應(yīng)的已經(jīng)比賽過一次：16,27，38,49，510。后面再安排兩組選手分別比賽的時(shí)候,就不考慮已經(jīng)比賽過的組合。安排兩組選手分別比賽的時(shí)候，依照這樣的規(guī)則：1按遞增順序依次跟沒有比賽過的第2

8、組選手比賽(7，8，9,10各一天)。若1和x1比賽，則2號(hào)從610號(hào)中從x1之后開始按增序中找第一個(gè)沒有比賽過的選手，跟他比賽(如果x110,則2號(hào)從6號(hào)開始按增序找).3、4、5號(hào)也如此找。結(jié)果如表2-16所示：（表216）10人的賽程安排12345678910215374891063812459106745913210678542101367896789101543276108291543836791021549104687321510975684321觀察表216的右上角,發(fā)現(xiàn)如下規(guī)律(表2-8，6人比賽時(shí)，也有此規(guī)律）：【規(guī)則一】：每一行數(shù)值從左到右循環(huán)遞增；每一列上也是610（即n

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

10、4590674591320678542013678967890154327608291543836790215490468732150975684321三、算法設(shè)計(jì)n名選手的賽程安排問題：1、如果n為偶數(shù),可分為兩個(gè)n/2人的組，分別比賽，然后兩組間比賽。（1)如果n/2為偶數(shù)，左下角為左上角加n/2來得到，然后左下角拷貝到右上角；左上角拷貝到右下角； (2)如果n/2為奇數(shù)，先安排左下角（除0外都加n/2），然后把同一天都有空的選手安排比賽。然后，右上角要按規(guī)則一來完成,右下角由規(guī)則二來定.2、如果n為奇數(shù),則加1個(gè)選手使n+1成為偶數(shù).轉(zhuǎn)化成偶數(shù)名選手的賽程安排問題來解決。最后把虛擬選手n

11、+1號(hào)所在位置上的值置為0.即完成安排.四、算法改進(jìn)循環(huán)賽要求比賽的每?jī)蓚€(gè)選手都要進(jìn)行一次比賽,而且每個(gè)選手每天都要比賽一場(chǎng).這種題目的解法通常是用分治的思想來做，并且是分治方法解題的經(jīng)典題目.下面的一種受多邊形啟發(fā)的方法，也能巧妙解決循環(huán)賽日程表問題。多邊形解法:有n個(gè)選手要進(jìn)行循環(huán)賽，畫n邊形，每個(gè)點(diǎn)表示一個(gè)選手。在同一水平線上的選手進(jìn)行比賽.每天的比賽由旋轉(zhuǎn)一次的多邊形決定，每次順時(shí)針旋轉(zhuǎn)360/n度.例如：（1）假設(shè)有5名運(yùn)動(dòng)員（每天將有一名隊(duì)員輪空）,則可建立一個(gè)如下五邊多邊形:1 2 5 3 4 所以第一天4號(hào)輪空，對(duì)局為12和53(2)第二天順時(shí)針旋轉(zhuǎn)360/5度，即為:5 14

12、 23所以第二天3號(hào)輪空，對(duì)局為15和2-4(3）依此類推,直到第五天,多邊形為2 3 1 4 5比賽結(jié)束，同理,若比賽人數(shù)為8人，多邊形則為1 2 8 3 7 4 6 5依次順時(shí)針旋轉(zhuǎn)360/8度7次后，即比賽進(jìn)行7天，即可結(jié)束比賽五、算法實(shí)現(xiàn)（1)采用分治法實(shí)現(xiàn)代碼（c語言實(shí)現(xiàn))：/ 循環(huán)賽日程安排問題采用分治法 */includestdlib。h>includestdio.hint *A； /int *指針數(shù)組,int schedule； /int數(shù)組，一維數(shù)組保存二維數(shù)組的數(shù)據(jù)int N =1; /問題的規(guī)模。初始化時(shí)會(huì)設(shè)定/isodd：判斷x是否奇數(shù)，是則返回1,否則0int

13、isodd（int x) return x1;/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；irow； i+） for（j=0；jcol； j+） printf（”4d”, Aij)； printf(”n”); /init：初始化，設(shè)置問題規(guī)模N值，分配內(nèi)存，用schedule指向； 把A構(gòu)造成一個(gè)二維數(shù)組/void init（) int i， n； char line100=0'； printf

14、（"請(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； /schedule是行化的二維數(shù)組 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等價(jià)為二維數(shù)組 Ai=schedule+in; Ai0=i+1；/初始化這個(gè)數(shù)組的第一

15、列 return；/replaceVirtual：把第m號(hào)虛的選手去掉（換做0)*/void replaceVirtual（int m） int i，j; for(i=0；im-1；i+） /行:對(duì)應(yīng)選手號(hào)1m1 for （j=0;j=m；j+） /列： 比行要多1 Aij = (Aij=m）？0：Aij； return；/*copyeven：m為偶數(shù)時(shí)用，由前1組的m位選手的安排，來構(gòu)成第2組m位選手 的賽程安排，以及兩組之間的比賽安排 /void copyeven（int m） if（isodd(m）) return； int i，j； for （j=0;jm；j+） /1. 求第2組的安

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

17、j+） /1。 求第2組的安排(前m天） for (i=0；im；i+）/行 if （Aij！=0） Ai+mj=Aij+m； else /特殊處理：兩個(gè)隊(duì)各有一名選手有空，安排他們比賽 Ai+mj = i+1； Aij = i+m+1； /*安排兩組選手之間的比賽(后m-1天）/ for（i=0，j=m+1；j<2m；j+） Aij= j+1; /2. 1號(hào)選手的后m1天比賽 A （Aij 1） j = i+1; /3. 他的對(duì)手后m-1天的安排 /以下的取值要依賴于1號(hào)選手的安排，所以之前先安排1號(hào)的賽程 for （i=1；im；i+) /第1組的其他選手的后m1天的安排 for (

18、j=m+1；j2m；j+) /2. 觀察得到的規(guī)則一：向下m+12m循環(huán)遞增 Aij = (Ai-1j+1)m=0)?Ai1j+1 ：m + （Ai-1j+1)m; /3。 對(duì)應(yīng)第2組的對(duì)手也要做相應(yīng)的安排 A (Aij1） 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ù) c

19、opyeven（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è)選手來求解 replaceVirtual(m+1）； /然后把第m+1號(hào)虛選手置成0 return ; else /m是偶數(shù)， tournament（m/2)； /則先安排第1組的m/2人比賽 makecopy（m）; /然后根據(jù)算法,構(gòu)造左下、右下、右上、右下的矩陣 return ；/endprogram：回收分配的內(nèi)存*/void endprogram(） fr

20、ee（schedule）; free（A）； int main（） init（）； /初始化 tournament(N）;/求解 print（）； /打印結(jié)果 endprogram（）； /回收內(nèi)存 getchar（)； return 0；（2） 多邊形法（C語言實(shí)現(xiàn))：/* 采用多邊形實(shí)現(xiàn)法 */include <stdio。hdefine N 1000int aNN；int bN;inline bool odd（int n） return n 1；void init（） int i； for（i=0；iN；+i） ai0=i；void tour（int n） an1=n； if(n=

21、1) return； int m=odd（n） ？ n ： n1； 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 "）; el