循環賽日程表的遞歸和非遞解

摘要：介紹了算法設計技術分治法的應用。使用分治法實現了循環賽日程表的遞歸和非遞歸解，并作了較為詳細的說明，供《算法設計與分析》課程教學參考。

關鍵詞：算法；數據結構；分治法；遞歸

中圖分類號：TP301文獻標識碼：A文章編號：1009-3044(2008)25-1445-04

The Recursive and Non-recursive Solution for Calendar of Round Robin

WU Xiu-mei， JIANG Jing， WANG Shao-hua， WEN Jing-he

(School of Computer and Information， Shanghai Second Polytechnic University， Shanghai 201209， China)

Abstract: The application of a powerful algorithm design technique is introduced. The name oftechnique is \"divide and conquer\". The recursive and non-recursive solution for calendar of round robin is given by divide and conquer. The algorithm of solution is more detailed explanation. It can be used for teaching reference.

Key words: algorithm; data structure; divide and conquer; recursive

1 引言

分治法是一種重要的算法設計技術，它可以用來解決各類問題。分治顧名思義就是分而治之，分治法的基本思想是：將問題遞歸分成若干個子實例（多數情況下是分成2個），分別解決每個子實例，然后把子實例的解組合起來，得到原問題的解，比較典型的應用例子就是“歸并排序法”和“快速排序法”。在大多數《算法設計與分析》教課書中，通常將“歸并排序法”和“快速排序法”作為講解分治法的例子[1-3]。然而，“歸并排序法”和“快速排序法”早已成為《數據結構》課程的教學內容[4-5]，當然講解的角度和重點與《算法設計與分析》課程不一樣。若在《算法設計與分析》課程中，仍然并且僅僅使用這二個例子來講解分治法的話，給學生有一種分治法應用實例貧乏的感覺。

實際上分治法不僅可以用來設計算法，而且在其它各方面也有廣泛應用。例如，可以用分治法設計電路、構造數學證明、制定循環賽日程表、……等等。在參考文獻[1]中，介紹了用分治解決制定循環賽日程表的問題，但算法描述過于簡單，程序可理解性并不盡人意。在本文中，對參考文獻[1]中的算法實現作了一些修改，對修改后的算法實現作了較為詳細的說明。在此基礎上，進一步提出了循環賽日程表的遞歸解，供《算法設計與分析》課程教學參考。

2 問題和算法基本思想

設有n=2k個運動員要進行網球比賽。設計一個滿足以下要求的比賽日程表[1-2]：

1) 每個選手必須與其它n-1個選手各賽一次。

2) 每個選手一天只能賽一次。

3) 循環賽一共進行n-1天。

按此要求可將比賽日程表設計成有n行和n-1列的一個表。在表中第i行和第j列處填入第i個選手在第j天所遇到的選手。

設有8個運動員，這樣共比賽7天，比賽日程表如下所示：

表1 循環賽日程表（8人）

■

按分治策略，可將所有選手分成二組。n個選手的比賽日程表，可以通過為n/2個選手設計日程表來決定；n/2個選手的比賽日程表，可以通過為n/4個選手設計日程表來決定； …… ；直到為2個選手設計比賽日程表。這樣比賽日程表的設計就變得很簡單，這時只要讓二個選手相互比賽即可，這樣形成4組2個選手的比賽日程表。詳見表2、表3、表4和表5。

表2表3表4 表5

■

我們已經為2個選手的相互比賽設計了比賽日程表，在此基礎上為4個選手相互比賽設計比賽日程表。參考表1，將表3抄至表2的右側，將表2抄至表3的右側；再將表5抄至表4的右側，將表4抄至表5的右側，這樣就形成了2組4個選手的比賽日程表。詳見表6、表7。

將表2和表3按水平方向 “表2左表3右” 拼接。由于表2中的運動員和表3中的運動員完全不同，拼接后在每一行中不可能存在二個相同號碼，即拼接后不會產生一個運動員和另一個運動員比賽二次的情況。將表3和表2按水平方向“表3左表2右”拼接。同理，拼接后也不會產生一個運動員和另一個運動員比賽二次的情況。二次水平拼接后形成表6，讓我們以垂直方向觀察表6。在左半部分是“表2上表3下”，在右半部分是“表3上表2下”。由于表3中的運動員和表2中的運動員完全不同，在每一列中不可能存在二個相同號碼，即拼接后不會產生一個運動員在同一天和不同選手比賽二場的情況。

表6 循環賽日程表（4人） 表6 循環賽日程表（4人）

■

我們已經為4個選手相互比賽設計了比賽日程表，在此基礎上為8個選手相互比賽設計比賽日程表。參考表1，將表7抄至表6的右側，將表6抄至表7的右側。這樣就形成了8個選手的比賽日程表，如表1所示。

3 循環賽日程表的非遞歸解

3.1 變量說明

1) 變量k

k表示每組運動員人數。假設n=8，k值范圍為2、4、8。

2) 變量v

v表示目前處理（被抄）數據的起始行號。假設n=8，v值范圍如下所示：

①當k=2時，v值范圍為0、2、4、6；

②當k=4時，v值范圍為0、4；

③當k=8時，v值為0。

(3) 變量i

i表示目前處理（被抄）數據的相對行號（絕對行號=起始行號+相對行號=v+i）。假設n=8，對應于k值，i值范圍如下所示：

①當k=2時，i值范圍為1..2。處理右下角時i=1（目標行號= v+i+k/2=v+i+1=v+2），處理右上角時i=2（目標行號=v+i-k/2=v+i-1=v+1） ；

②當k=4時，i值范圍為1..4。處理右下角時i=1..2（目標行號= v+i+k/2=v+i+2），處理右上角時i=3..4（目標行號=v+i-k/2=v+i-2）；

③當k=8時，i值范圍為1..8。處理右下角時i=1..4（目標行號= v+i+k/2=v+i+4），處理右上角時i=5..8（目標行號= v+i-k/2=v+i-4）。

4) 變量j

j表示目前處理（被抄）數據的列號。假設n=8，j的數值范圍如下所示：

①當k=2時，j值為1。目標列號=j+k/2=j+1=2；

②當k=4時，j值范圍為1..2。目標列號=j+k/2=j+2；

③當k=8時，j值范圍為1..4。目標列號=j+k/2=j+4；

5) 二維數組A

二維數組A用于保存比賽日程表，其規模為n*n，其中n是運動員的人數。第1列按順序從小到大記錄運動員的編號，第2至第7列用以記錄比賽對手的號碼。

3.2 算法描述

輸入：運動員人數n（假定n恰好為2的i次方）

輸出：比賽日程表A[1..n，1..n]

1.for i←1 to n//設置運動員編號

2.A[i，1]←i

3.end for

4.k←2 //初值k=2，先處理2個運動員循環賽日程表。

5.while k≤n

6.v←0 //初值v=0，當k=2時先處理(1，2)。

7.while v≤n-k

8.for i←1 to k/2//沿對角線處理右下角。

9.for j←1 to k/2

10. a[v+i+k/2，j+k/2]←a[v+i，j]

11. end for

12. end for

13. for i←k/2+1 to k//沿對角線處理右上角。

14. for j←1 to k/2

15. a[v+i-k/2，j+k/2]←a[v+i，j]

16. end for

17. end for

18. v←v+k //當k=2，則v的值為2，4，6，依次處理 (3，4)，(5，6)，(7，8)。

19. end while

20. k←k*2 //然后處理4、8、…、n=2k個運動員的比賽日程表

21. end while

在上述偽代碼中，輸入和輸出部分略。由程序中的第5至第9句可知，程序含4重循環。盡管程序含4重循環，但在循環體中語句所做的工作是填表，并且表中的每個單元被填寫且僅被填寫一次。由于二維數組的規模為n2，所以算法的時間復雜性可用Θ(n2)來表示。

3.3 測試

用C語言具體實現上述偽代碼。設n=16，程序處理結果如圖1所示。

■

圖1 循環賽日程表（16人）

4 循環賽日程表的遞歸解

4.1 變量說明

1) 形式參數k

k表示每組運動員人數。假設n=8，k值范圍為2、4、8。

2) 形式參數i

i表示目前處理（被抄）數據的起始行號。假設n=8，對應于k值，i值范圍如下所示：

①當k=8時，i值為1；

②當k=4時，i值為1、5；

③當k=2時，i值為1、3、5、7。

3) 二維數組A

二維數組A的作用同前。可將其作為函數參數，傳遞給被調用函數；也可將其定義為全程量，供被用函數使用。在下面算法中，將二維數組A視為全程量。

4.2 算法描述

輸入：運動員人數n（假定n恰好為2的i次方）

輸出：比賽日程表A[1..n，1..n]

1. input n//輸入

2. for i←1 to n//設置運動員編號。

3. A[i，1]←i

4. end for

5. Calendar(1，n)//過程調用

6. for i←1 to n//輸出

7. for j←1 to n

8. output A[i，j]

9. end for

10.end for

過程Calendar(i， k)//i表示起始行，k表示運動員人數。

1. if k=2 then//運動員人數為2個

2. A[i+1，2]←A[i，1]

3. A[i，2]←A[i+1，1]

4. else

5. Calendar(i，k/2);//將運動員分成二組，然后按人數一半遞歸處理。

6. Calendar(i+k/2，k/2);

7. for a←i to i+k/2-1//將2個k/2人組的解組合成1個k人組的解。

8. for b←1 to k/2

9. A[a+k/2，b+k/2]←A[a，b] //沿對角線處理右下角。

10.end for

11.end for

12.for a←i+k/2 to i+k-1

13.for b←1 to k/2

14.A[a-k/2，b+k/2]←A[a，b] //沿對角線處理右上角。

15.end for

16.end for

17.end if

由上述偽代碼可知，遞歸算法簡潔，意義明確，且容易理解。設運動員人數為8人，算法首先將他們分為2組，每組4人，起始行號分別為1和5；再將2個4人組分為4個2人組，同樣通過起始行號來區分它們。經過這樣的劃分后，每一個組僅有2人，這樣只要讓他們相互比賽即可。然后，由2人組的解組合成4人組的解；再由4人組的解，組合成原問題（8人組）的最終解。

5 結束結

由于循環賽日程表具有一定的實際意義，問題的解又是用分治法來實現的，所以論文內容可作為《算法設計與分析》課程中分治法的教學內容或教學參考。問題解的前提條件是：假定運動員人數恰好為2的i次方。當運動員人數不符合此條件時，上述算法提供了一個解題思路，或給出了一個近似解。

參考文獻：

[1] 王曉東. 算法設計與分析[M]. 北京:清華大學出版社，2003.

[2] 王曉東. 計算機算法設計與分析[M]. ２版. 北京:電子工業出版社，2005.

[3] [沙特]M.H.Alsuwaiyel.算法設計技巧與分析[M]. 北京:電子工業出版社，2004.

[4] 嚴蔚敏， 吳偉民. 數據結構[M]. 北京:清華大學出版社，1997.

[5] 溫敬和. 歸并排序法的非遞歸實現[J]. 上海第二工業大學學報，2002，1:50-55.