循環(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)賽日程表問題；分治法、題目描述設(shè)有 n 個(gè)運(yùn)動(dòng)員要進(jìn)行網(wǎng)球循環(huán)賽。設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：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 天。、問題分析循環(huán)賽日程表可以采用分治法實(shí)現(xiàn)， 把一個(gè)表格分成 4 個(gè)小表格來處理， 每個(gè)小表格都 是一樣的處理方法，只是參數(shù)不同。分析過程具體如下：1、n=1表 2-1)2. 、 n

3、=2表 2-2)1212213、n=3(1) 添加一個(gè)虛擬選手 4#，構(gòu)成 n+1 4(2) 4/2 2，分兩組，每組各自安排( 1 2)，(3 4)(3) 每組跟另一組分別比賽(拷貝)這是四個(gè)人比賽的(4) 把虛選手置為 01234214334124321表 2-3 ) 4 人賽程表 2-4)3 人賽程12302103301230321這是三個(gè)人比賽的安排4、n=4，見表 2-35、n=5(1) 加一個(gè)虛選手， n+1=6 。安排好 6 個(gè)人的比賽后，把第 6 個(gè)人用 0 表示即得 5 人的。(2) 分成兩組 (1 2 3) (4 5 6)，各 3名選手(3) 依照表 2-4，安排第 1組；

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

5、成 0，(a) 若 1#5#，由于 3#和 6#已經(jīng)比賽過，所以只能安排 : 2#6#，(b) 若 1# 6#，由于 2#和 5#已經(jīng)比賽過，只能安排：2#4#，這樣安排后前三行的后兩列，后三行的后兩列由上面的三行來定：表 2-8) 6 人賽程123456215364361245456132542613634521表 2-8 就是 6 名選手的比賽日程安排。將其中的 6 號(hào)作為虛擬選手， 即得 5 名選手的賽程安排表：表 2-9 )5 人賽程1234502153043012454501325420136345216、n=6 ，見表 2-8。7、n=7, 添加 1，n+1=8。8名選手的安排，由

6、 4 名選手(表 2-3)構(gòu)成表 2-10) 8 人賽程1234567821436587341278564321876556781234658721437856341287654321將其中的 8 改成 0，即得 7 名選手的賽程安排。表 2-11) 7 人賽程12345670214365073412705643210765567012346507214370563412076543218、n=8 ，見表 2-10。9、n=9，由 n+1 10人，將虛選手 10 號(hào)置為 0來得到。10、n=10。10人的比賽，分兩組( 1 2 3 4 5)和(6 7 8 9 10)各 5人。前 5人比賽的安排

7、 如表 2-12表 2-12 )67891007610809806791091006871097068然后兩組合并，得到表 2-14表 2-14 )12345021530430124545013254201367891007610809806791091006871097068找兩組中同一天中沒有安排比賽的，安排他們比賽：表 2-15 )123456215374381245459132542101367891017610829836791091046871097568由于兩組中：1 2 3 4 56 7 8 9 10按列對(duì)應(yīng)的已經(jīng)比賽過一次： 1 6，27，38，49，510。后面再安排兩組

8、選手分別比賽的時(shí)候，就不考慮已經(jīng)比賽過的組合。安排兩組選手分別比賽的時(shí)候， 依照這樣的規(guī)則： 1#按遞增順序依次跟沒有比賽過 的第 2組選手比賽（ 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 所示：表 2-16）10 人的賽程安排1234567891021537489106381245910674591321067854210136789678910154327610829154383679102154910468

9、7321510975684321觀察表 2-16 的右上角，發(fā)現(xiàn)如下規(guī)律（表 2-8， 6人比賽時(shí)，也有此規(guī)律） ： 【規(guī)則一】：每一行數(shù)值從左到右循環(huán)遞增；每一列上也是6 10（即 n/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ī)律

10、填數(shù)字，就可以得到一種合理的安排。 由于我們不是求全部的安排，所以，只要得到這么一個(gè)解就可以了。9 人比賽，則將表 2-16 中的 10 全部用 0 代替即得。表 2-17） 9 人的賽程安排1234567890215374890638124590674591320678542013678967890154327608291543836790215490468732150975684321三、算法設(shè)計(jì)n 名選手的賽程安排問題：1、如果 n 為偶數(shù)，可分為兩個(gè) n/2 人的組，分別比賽，然后兩組間比賽。（ 1）如果 n/2 為偶數(shù)，左下角為左上角加 n/2 來得到，然后左下角拷貝到右上角；左 上

11、角拷貝到右下角；（2）如果 n/2 為奇數(shù)，先安排左下角（除 0 外都加 n/2 ），然后把同一天都有空的選手 安排比賽。然后，右上角要按規(guī)則一來完成，右下角由規(guī)則二來定。2、如果 n 為奇數(shù)，則加 1 個(gè)選手使 n+1 成為偶數(shù)。轉(zhuǎn)化成偶數(shù)名選手的賽程安排問題 來解決。最后把虛擬選手 n+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)賽

12、，畫 n 邊形，每個(gè)點(diǎn)表示一個(gè)選手。 在同一水平線上的選手進(jìn)行比賽。每天的比賽由旋轉(zhuǎn)一次的多邊形決定，每次順時(shí)針旋轉(zhuǎn) 360/n 度 。例如：（ 1）假設(shè)有 5名運(yùn)動(dòng)員（每天將有一名隊(duì)員輪空） ，則可建立一個(gè)如下五邊多邊形：所以第一天 4號(hào)輪空，對(duì)局為 1-2 和5-3（ 2）第二天順時(shí)針旋轉(zhuǎn) 360/5 度，即為：所以第二天 3號(hào)輪空，對(duì)局為 1-5 和2-4（3）依此類推，直到第五天，多邊形為比賽結(jié)束，同理，若比賽人數(shù)為8人，多邊形則為8依次順時(shí)針旋轉(zhuǎn) 360/8 度7次后，五、算法實(shí)現(xiàn)即比賽進(jìn)行 7 天，即可結(jié)束比賽1）采用分治法實(shí)現(xiàn)代碼（ c 語言實(shí)現(xiàn)）/* 循環(huán)賽日程安排問題- 采用

13、分治法 */#include #include int *A;/int *int *schedule; /int int N =1;/指針數(shù)組，數(shù)組，一維數(shù)組保存二維數(shù)組的數(shù)據(jù) 問題的規(guī)模。初始化時(shí)會(huì)設(shè)定/isodd: 判斷 x 是否奇數(shù)，是則返回 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;else row=N; col=N;10printf( 第 1 列是選手編號(hào) n);for(i=0;irow; i+)for(j=0;jcol;

14、 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( 請(qǐng)輸入選手人數(shù)： );fgets(line,sizeof(line), stdin);N=atoi(line);if(N=0) exit(-1); if(isodd(N)n=N+1;elsen=N;/schedule 是行化的二維數(shù)組 schedule=(int *)calloc(n*n, sizeof(int);A=(int

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

16、/*copyeven:m 為偶數(shù)時(shí)用 ,由前 1 組的 m位選手的安排，來構(gòu)成第的賽程安排，以及兩組之間的比賽安排 */void copyeven(int m)if(isodd(m) return;int i,j;for (j=0;jm;j+) /1.for (i=0;im;i+)Ai+mj=Aij+m;for (j=m;j2*m;j+)/for (i=0;im;i+) /2.Aij=Ai+mj-m; /for (i=m;i2*m;i+) /3.Aij=Ai-mj-m; /求第 2 組的安排（ +m）兩組間比賽的安排第 1 組和第 2 組把左下角拷貝到右上角對(duì)應(yīng)的，第 2 組和第 1 組把左上

17、角拷貝到右下角return;/*copyodd:m 為奇數(shù)時(shí)用 , 由前 1 組的 m位選手的安排，來構(gòu)成第 2 組 m位選手 的賽程安排，以及兩組之間的比賽安排。這時(shí)和m為偶數(shù)時(shí)的處理有區(qū)別。*/12void copyodd(int m)int i,j;for (j=0;j=m;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+

18、1;j2*m;j+)Aij= j+1; /2. 1 號(hào)選手的后 m-1 天比賽A (Aij -1) j = i+1; /3.他的對(duì)手后 m-1 天的安排 / 以下的取值要依賴于 1號(hào)選手的安排，所以之前先安排 1 號(hào)的賽程 for (i=1;im;i+) / 第 1 組的其他選手的后 m-1 天的安排 for (j=m+1;j2*m;j+)/2.觀察得到的規(guī)則一：向下 m+12*m循環(huán)遞增Aij (Ai-1j+1)%m;/3.= (Ai-1j+1)%m=0)?Ai-1j+1 :m +對(duì)應(yīng)第 2 組的對(duì)手也要做相應(yīng)的安排A (Aij-1) j = i+1; return;13/*makecopy

19、: 當(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/2copyodd(m/2);else /m/2 copyeven(m/2);void tournament(int m)if(m=1)A00=1; return ;else if(isodd(m) /tournament(m+1); / replaceVirtual(m+1); / return ;else /mtournament(

20、m/2); / makecopy(m); /return ;為偶數(shù)如果 m為奇數(shù)，則 m+1是偶數(shù) 按照偶數(shù)個(gè)選手來求解然后把第 m+1號(hào)虛選手置成 0是偶數(shù)，則先安排第 1 組的 m/2 人比賽然后根據(jù)算法，構(gòu)造左下、右下、右上、右下的矩陣/*endprogram: 回收分配的內(nèi)存 */ void endprogram()free(schedule);free(A);14int main()init(); /初始化tournament(N);/求解print(); /打印結(jié)果endprogram(); /回收內(nèi)存getchar();return 0;2)多邊形法( C語言實(shí)現(xiàn)) /* 采用多

21、邊形實(shí)現(xiàn)法 */ #include #define N 1000 int 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=1) return;int m=odd(n) ? n : n-1; int i,j,k,r;for(i=1;i=m;+i)ai1=i;15 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;elsem=n;for(i=1;i=n;+i)for(j=1;jn)printf(0 );16elseprintf