循環(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)算2 / 18 法，通過測(cè)試分析，程序運(yùn)行結(jié)果正確，運(yùn)行效率較高。同時(shí)也介紹了循環(huán)賽日程表問題的另一種解法多邊形解法，這種方法另辟蹊徑，巧妙地解決了循環(huán)賽日程表問題，運(yùn)行效率較高。循環(huán)賽日程表問題研究摘要：本文采用分治算法來解決循環(huán)賽日程表的安排問題。根據(jù)算法的設(shè)計(jì)結(jié)果，采用 c 語言實(shí)現(xiàn)算法，

2、通過測(cè)試分析，程序運(yùn)行結(jié)果正確，運(yùn)行效率較高。同時(shí)也介紹了循環(huán)3 / 18 賽日程表問題的另一種解法，這種方法另辟蹊徑，想法獨(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）3、n=3 (1) 添加一個(gè)虛擬選手4#，構(gòu)成 n+14 (2) 4/22，分兩組，每組各自安排（1 2） ， （3 4）(3) 每組跟另一組分別比賽（拷貝）這是四個(gè)人比賽的（表 2-3） 4 人賽程(4) 把虛選手置為0 （表 2-4）3 人賽程1 1 2 2 1 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 1 2 3 0 2 1 0 3 3 0 1 2 4 / 18 這是三個(gè)人比賽的安排4、n=4，見表 2-3 5、n=5 (1) 加一個(gè)虛選手，n+1=6。安排好6 個(gè)人的比賽后，把第6 個(gè)人用0 表示即得5人的。(2) 分成兩組 (1 2 3) （4

4、 5 6） ，各 3 名選手(3) 依照表 2-4，安排第1 組；按表2-5 安排第 2 組(除 0 元素外，都加3) （表 2-5）(4) 把表 2-5 排于表 2-4 下方（表 2-6）(5) 把同一天都有空的兩組安排在一起比賽(按這種安排， 肯定每天只有一對(duì)空組)。（表 2-7）(6) 第一組的 (1 2 3)和第 2 組的 (4 5 6)分別比賽。但是由于 (1,4), (2, 5), (3 6) 已經(jīng)比0 3 2 1 4 5 6 0 5 4 0 6 6 0 4 5 0 3 2 1 1 2 3 0 2 1 0 3 3 0 1 2 4 5 6 0 5 4 0 6 6 0 4 5 1 2

5、3 4 2 1 5 3 3 6 1 2 4 5 6 1 5 4 2 6 6 3 4 5 5 / 18 賽過了，所以在后面的安排中不能再安排他們比賽。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#已經(jīng)比賽過，只能安排：2#4#， 3#5# 這樣安排后前三行的后兩列，后三行的后兩列由上面的三行來定：（表 2-8）6 人賽程表 2-8 就是 6 名選手的比賽日程安排。將其中的6 號(hào)作為虛擬選手，把6 換成 0，即得 5 名選手的賽程安排表：（表 2-9）

6、5 人賽程6、n=6，見表 2-8。7、n=7, 添加 1，n+1=8。8 名選手的安排，由4 名選手（表2-3）構(gòu)成（表 2-10）8 人賽程將其中的8 改成 0，即得 7 名選手的賽程安排。1 2 3 4 5 6 2 1 5 3 6 4 3 6 1 2 4 5 4 5 6 1 3 2 5 4 2 6 1 3 6 3 4 5 2 1 1 2 3 4 5 0 2 1 5 3 0 4 3 0 1 2 4 5 4 5 0 1 3 2 5 4 2 0 1 3 6 3 4 5 2 1 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7

7、 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1 6 / 18 （表 2-11）7 人賽程8、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 人比賽的安排如表 2-12 （表 2-12）第 2 組的 5 人比賽就是將前5 人比賽選手（非0）號(hào)對(duì)應(yīng)加5 （表 2-13）然后兩組合并，得到表2-14 1 2 3 4 5 6 7 0 2 1 4 3 6 5 0

8、7 3 4 1 2 7 0 5 6 4 3 2 1 0 7 6 5 5 6 7 0 1 2 3 4 6 5 0 7 2 1 4 3 7 0 5 6 3 4 1 2 0 7 6 5 4 3 2 1 1 2 3 4 5 0 2 1 5 3 0 4 3 0 1 2 4 5 4 5 0 1 3 2 5 4 2 0 1 3 6 7 8 9 10 0 7 6 10 8 0 9 8 0 6 7 9 10 9 10 0 6 8 7 10 9 7 0 6 8 7 / 18 （表 2-14）找兩組中同一天中沒有安排比賽的，安排他們比賽：（表 2-15）由于兩組中：1 2 3 4 5 6 7 8 9 10 按列對(duì)應(yīng)

9、的已經(jīng)比賽過一次：1 6，27，38，49，510。后面再安排兩組選手分別比賽的時(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 所示：1 2 3 4 5 0 2 1 5 3 0 4 3 0 1 2 4 5 4 5 0 1 3 2 5 4 2 0 1 3 6 7 8 9 10 0 7 6 10

10、 8 0 9 8 0 6 7 9 10 9 10 0 6 8 7 10 9 7 0 6 8 1 2 3 4 5 6 2 1 5 3 7 4 3 8 1 2 4 5 4 5 9 1 3 2 5 4 2 10 1 3 6 7 8 9 10 1 7 6 10 8 2 9 8 3 6 7 9 10 9 10 4 6 8 7 10 9 7 5 6 8 8 / 18 （表 2-16）10 人的賽程安排觀察表 2-16 的右上角，發(fā)現(xiàn)如下規(guī)律（表2-8， 6人比賽時(shí)，也有此規(guī)律）：規(guī)則一 ：每一行數(shù)值從左到右循環(huán)遞增；每一列上也是610（即 n/2+1n）循環(huán)遞增（取到最大值10 之后，下一個(gè)數(shù)字又從6 開

11、始取值；而且不包含左上角的塊同一行中取過的值）。第一行第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 人比賽，則將表2-16 中的 10 全部用 0代替即得。（表 2-17）9 人的賽程安排1 2 3 4 5 6 7 8 9 10 2 1 5 3 7 4 8 9 10 6

12、 3 8 1 2 4 5 9 10 6 7 4 5 9 1 3 2 10 6 7 8 5 4 2 10 1 3 6 7 8 9 6 7 8 9 10 1 5 4 3 2 7 6 10 8 2 9 1 5 4 3 8 3 6 7 9 10 2 1 5 4 9 10 4 6 8 7 3 2 1 5 10 9 7 5 6 8 4 3 2 1 1 2 3 4 5 6 7 8 9 0 2 1 5 3 7 4 8 9 0 6 3 8 1 2 4 5 9 0 6 7 4 5 9 1 3 2 0 6 7 8 5 4 2 0 1 3 6 7 8 9 6 7 8 9 0 1 5 4 3 2 7 6 0 8 2 9

13、 1 5 4 3 8 3 6 7 9 0 2 1 5 4 9 0 4 6 8 7 3 2 1 5 0 9 7 5 6 8 4 3 2 1 9 / 18 三、算法設(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ù)名選手的賽程

14、安排問題來解決。最后把虛擬選手n+1 號(hào)所在位置上的值置為0。即完成安排。四、算法改進(jìn)循環(huán)賽要求比賽的每兩個(gè)選手都要進(jìn)行一次比賽，而且每個(gè)選手每天都要比賽一場。這種題目的解法通常是用分治的思想來做，并且是分治方法解題的經(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ì)局為1-2 和5

15、-3 （2）第二天順時(shí)針旋轉(zhuǎn)360/5 度，即為：5 1 4 2 3 10 / 18 所以第二天 3號(hào)輪空，對(duì)局為1-5和 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)賽日程安排問題- 采用分治法 */ #include #include int *a; /int *指針數(shù)組，int *schedule; /int數(shù)組，一維數(shù)組保存二維數(shù)組的數(shù)據(jù)int n =1; /問題的

16、規(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; 11 / 18 printf(第 1 列是選手編號(hào) n); for(i=0;irow; i+) for(j=0;jcol; j+) printf(%4d, aij); printf(n); /*init：初始化，設(shè)置問題規(guī)模n值，分配存，用schedule 指向；把 a構(gòu)造成一

17、個(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; /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+) /

18、把 a等價(jià)為二維數(shù)組 ai=schedule+i*n; ai0=i+1;/初始化這個(gè)數(shù)組的第一列 return; /*replacevirtual:把第 m號(hào)虛的選手去掉（換做0） */ void replacevirtual(int m) 12 / 18 int i,j; for(i=0;im-1;i+) /行：對(duì)應(yīng)選手號(hào)1m-1 for (j=0;j=m;j+) /列: 比行要多1 aij = (aij=m)?0:aij; return; /*copyeven:m為偶數(shù)時(shí)用 ,由前 1 組的 m位選手的安排，來構(gòu)成第2 組 m位選手的賽程安排，以與兩組之間的比賽安排 */ void cop

19、yeven(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+)/兩組間比賽的安排 for (i=0;im;i+) /2. 第 1 組和第 2 組 aij=ai+mj-m; /把左下角拷貝到右上角 for (i=m;i2*m;i+) /3. 對(duì)應(yīng)的，第2 組和第 1 組 aij=ai-mj-m; /把左上角拷貝到右下角 return; /*copyodd:m為奇數(shù)時(shí)用 , 由前 1 組的 m位選手的安排，來構(gòu)成第

20、2組 m位選手的賽程安排，以與兩組之間的比賽安排。這時(shí)和m為偶數(shù)時(shí)的處理有區(qū)別。*/ 13 / 18 void 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+1;j2*m;j+) aij= j+1; /2. 1號(hào)選手的后m-1 天比賽 a (ai

21、j -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=0)?ai-1j+1 :m + (ai-1j+1)%m; /3. 對(duì)應(yīng)第 2 組的對(duì)手也要做相應(yīng)的安排 a (aij-1) j = i+1; return; 14 / 18 /*makecopy: 當(dāng)前有 m位（偶數(shù)）選手，分成兩組，每組由m/2 位選手構(gòu)成由第一

22、組的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+1); /按照偶數(shù)個(gè)選手來求解 replacevirtual(m+1); /然后把第m+1號(hào)虛選手置成0 return ;

23、else /m是偶數(shù)， tournament(m/2); /則先安排第1 組的 m/2 人比賽 makecopy(m); /然后根據(jù)算法，構(gòu)造左下、右下、右上、右下的矩陣 return ; /*endprogram:回收分配的存 */ void endprogram() free(schedule); free(a); 15 / 18 int main() init(); /初始化 tournament(n);/求解 print(); /打印結(jié)果 endprogram(); /回收存 getchar(); return 0; （2）多邊形法（c語言實(shí)現(xiàn)）：/* 采用多邊形實(shí)現(xiàn)法 */ #inc

24、lude #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; 16 / 18 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); re