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

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

3、2 （表 2-2）3、n=3 (1) 添加一個虛擬選手4#，構成 n+14 (2) 4/22，分兩組，每組各自安排（1 2） ， （3 4）(3) 每組跟另一組分別比賽（拷貝）這是四個人比賽的（表 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 這是三個人比賽的安排4、n=4，見表 2-3 5、n=5 (1) 加一個虛選手，n+1=6。安排好6 個人的比賽后，把第6 個人用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) 把同一天都有空的兩組安排在一起比賽(按這種安排， 肯定每天只有一對空組)。（表 2-7）(6) 第一組的 (1 2 3)和第 2 組的 (4 5 6)分別比賽。但是由于 (1,4), (2, 5), (3 6) 已經比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#已經比賽過，所以只能安排: 2#6#， 3#4# (b) 若 1# 6#，由于 2#和 5#已經比賽過，只能安排：2#4#， 3#5# 這樣安排后前三行的后兩列，后三行的后兩列由上面的三行來定：（表 2-8）6 人賽程表 2-8 就是 6 名選手的比賽日程安排。將其中的6 號作為虛擬選手，把6 換成 0，即得 5 名選手的賽程安排表：（表 2-9）

6、5 人賽程6、n=6，見表 2-8。7、n=7, 添加 1，n+1=8。8 名選手的安排，由4 名選手（表2-3）構成（表 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 號置為 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）號對應加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 按列對應

9、的已經比賽過一次：1 6，27，38，49，510。后面再安排兩組選手分別比賽的時候，就不考慮已經比賽過的組合。安排兩組選手分別比賽的時候，依照這樣的規則：1#按遞增順序依次跟沒有比賽過的第 2 組選手比賽（7，8，9，10 各一天）。若 1#和 x1比賽，則2 號從 610 號中從 x1之后開始按增序中找第一個沒有比賽過的選手，跟他比賽(如果 x110，則 2 號從 6 號開始按增序找)。3、4、5 號也如此找。結果如表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 的右上角，發現如下規律（表2-8， 6人比賽時，也有此規律）：規則一 ：每一行數值從左到右循環遞增；每一列上也是610（即 n/2+1n）循環遞增（取到最大值10 之后，下一個數字又從6 開

11、始取值；而且不包含左上角的塊同一行中取過的值）。第一行第m+1(下標從 0 開始 )列的值為 (m+1)+1 ，依次向右遞增；要先處理。其他行上的值要依賴于它的這個取值。規則二 ：右下角的塊：因為比賽是兩兩之間進行的，所以右下角由右上角決定（比賽的對手是兩個人，因此對應的安排要成對）；ok ，至此，問題就好解決了，只要按照這個規律填數字，就可以得到一種合理的安排。由于我們不是求全部的安排，所以，只要得到這么一個解就可以了。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 三、算法設計n 名選手的賽程安排問題：1、如果 n 為偶數，可分為兩個n/2 人的組，分別比賽，然后兩組間比賽。（1）如果 n/2 為偶數，左下角為左上角加n/2 來得到，然后左下角拷貝到右上角；左上角拷貝到右下角；（2）如果 n/2 為奇數，先安排左下角（除0 外都加 n/2 ） ，然后把同一天都有空的選手安排比賽。然后，右上角要按規則一來完成，右下角由規則二來定。2、如果 n 為奇數，則加1 個選手使n+1 成為偶數。轉化成偶數名選手的賽程

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

15、-3 （2）第二天順時針旋轉360/5 度，即為：5 1 4 2 3 10 / 18 所以第二天 3號輪空，對局為1-5和 2-4 （3）依此類推，直到第五天，多邊形為2 3 1 4 5 比賽結束，同理，若比賽人數為8人，多邊形則為1 2 8 3 7 4 6 5 依次順時針旋轉360/8 度7次后，即比賽進行7天，即可結束比賽五、算法實現（1）采用分治法實現代碼（c 語言實現）：/* 循環賽日程安排問題- 采用分治法 */ #include #include int *a; /int *指針數組，int *schedule; /int數組，一維數組保存二維數組的數據int n =1; /問題的

16、規模。初始化時會設定/isodd:判斷 x 是否奇數，是則返回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 列是選手編號 n); for(i=0;irow; i+) for(j=0;jcol; j+) printf(%4d, aij); printf(n); /*init：初始化，設置問題規模n值，分配存，用schedule 指向；把 a構造成一

17、個二維數組*/ void init() int i, n; char line100=0; printf(請輸入選手人數：); fgets(line,sizeof(line), stdin); n=atoi(line); if(n=0) exit(-1); if(isodd(n) n=n+1; else n=n; /schedule是行化的二維數組 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等價為二維數組 ai=schedule+i*n; ai0=i+1;/初始化這個數組的第一列 return; /*replacevirtual:把第 m號虛的選手去掉（換做0） */ void replacevirtual(int m) 12 / 18 int i,j; for(i=0;im-1;i+) /行：對應選手號1m-1 for (j=0;j=m;j+) /列: 比行要多1 aij = (aij=m)?0:aij; return; /*copyeven:m為偶數時用 ,由前 1 組的 m位選手的安排，來構成第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. 對應的，第2 組和第 1 組 aij=ai-mj-m; /把左上角拷貝到右下角 return; /*copyodd:m為奇數時用 , 由前 1 組的 m位選手的安排，來構成第

20、2組 m位選手的賽程安排，以與兩組之間的比賽安排。這時和m為偶數時的處理有區別。*/ 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 /特殊處理：兩個隊各有一名選手有空，安排他們比賽 ai+mj = i+1; aij = i+m+1; /* 安排兩組選手之間的比賽(后 m-1 天)*/ for(i=0,j=m+1;j2*m;j+) aij= j+1; /2. 1號選手的后m-1 天比賽 a (ai

21、j -1) j = i+1; /3. 他的對手后m-1 天的安排 /以下的取值要依賴于1 號選手的安排，所以之前先安排1 號的賽程 for (i=1;im;i+) /第 1 組的其他選手的后m-1 天的安排 for (j=m+1;j2*m;j+) /2. 觀察得到的規則一：向下m+12*m循環遞增 aij = (ai-1j+1)%m=0)?ai-1j+1 :m + (ai-1j+1)%m; /3. 對應第 2 組的對手也要做相應的安排 a (aij-1) j = i+1; return; 14 / 18 /*makecopy: 當前有 m位（偶數）選手，分成兩組，每組由m/2 位選手構成由第一

22、組的m/2 位選手的安排來構成第二組的比賽安排，第一組與第二組的比賽安排。要區分m/2 為奇數和偶數兩種情況 */ void makecopy(int m) if (isodd(m/2) /m/2為奇數 copyodd(m/2); else /m/2為偶數 copyeven(m/2); void tournament(int m) if(m=1) a00=1; return ; else if(isodd(m) /如果 m為奇數，則m+1是偶數 tournament(m+1); /按照偶數個選手來求解 replacevirtual(m+1); /然后把第m+1號虛選手置成0 return ;

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