這是一個算法作業，老師說要用分治思想解決，在網上找了都講解的不是很明白，比賽對數為奇數時，有點費解。不過最后還是想明白了，順便把作業放這，有興趣了解的可以看一下，逃）

問題：

有N個運動員進行單循環賽，即每個運動員要和所有其他運動員進行一次比賽。
1．試用分治法為N個運動員安排比賽日程。
2．要求每個（或隊）運動員每天只能進行一場比賽，且當運動員人數(隊數)為偶數時，整個比賽在N-1天內結束，為奇數時，在N天內結束；
3．將運動員從1到N編號。

思路：
我們用表格的方式來表示循環賽的日程安排，最左邊的一列表示隊號，每一行表示相應隊比賽每天的對手，即a[i][j]表示第i隊第j天的對手。
我們從兩個隊的比賽開始，并發現其中規律：

其中，四隊的表格可以從兩隊的表格產生的：

但這只能解決2的冪的隊數的循環賽日程。

為了解決更普遍的隊數，我們考慮隊數為偶數時，它必然可以被2整除，商為偶數或奇數。商為偶數可以用上面的方法得到結果，商為奇數時，就不行了。
我們先來看一個例子，隊數為6時，它的一半為3，是奇數，不能用上面的方法，我們先考慮它的子問題：隊數為4時，就是上面求出的結果了，我們要從隊數4產生6的結果：

我們可以看到后3行其實和前3行是一樣的，只是編號變了而已。為了讓編號在6以內，我們要改變編號7的對應情況，可以看出編號7是由編號4產生的，所以我們只要讓它們相對的隊組成一隊就可以了，即3-6,2-5,1-4。

至此，我們只解決了6隊的一部分情況，第5、6列還沒有產生：
由上面可知，第1行還缺5,6，第2行缺4,6，第3行缺4,5，那么它們該怎么排列才不會沖突呢？我們看到1,2,3行的5,6列在4,5,6中取兩個值，可以用循環隊列的形式解決，如下：

到此，我們來想更普遍的情況，任意一個隊數n，是否都可以分解為上面的兩種情況？
首先，我們看任意n是否能終止分解？如下偽代碼：

while i != 1 doif i % 2 == 0i i/2else i i+1

對于任何大于2的數除以2再加1或者加1再除以2，它的規模都會縮小，所以這最終是可以終止的。接著我們看是否能分解為上面兩種情況：
n為奇數時，用n+1代替計算，即轉化為偶數的隊數。
n為偶數時，分兩種情況，（1）n/2為偶數，（2）n/2為奇數。（1）繼續被2除，直到商為1，即轉化為第一種情況，n是2的冪，或者商為大于1的奇數（2），轉化為（2）。（2）就是第二種情況。所以，任意n是可以分解為上面兩種情況的，而且是可以終止的。
把上述的內容一般化，即為我們解決該問題的解：
1．tournament(a[][],n)用遞歸把問題分解為多個子問題，其中odd(n)判斷n是否為奇數,makecopy(a[][], n)用上面的兩種情況中的一種產生日程：

tournament(a[][], n) if n == 1a[0][0] = 1;return; if odd(n)tournament(a[][], n+1); elsetournament(a[][], n/2); makecopy(a[][], n); return;

2．odd(n)判斷n是否為奇數：

odd(n) return n&1;

3．makecopy(a[][], n)用上面的兩種情況中的一種產生日程，如果n/2為偶數用第一種，即copy(a[][], n)，n/2為奇數用第二種，即copyodd(a[][], n):

makecopy(a[][], n) m = n/2; if odd(m)copyodd(a[][], n); else copy(a[][], n);

4．copy(a[][], n)第一種情況的日程產生方法，為了更好的理解，我們從1*1到2*2到4*4的表格產生情況開始（假設表為二維數組a）：

1*1表產生2*2表是將a[0][0]加1放到a[0][1],再將這個值復制到a[1][0],將a[0][0]中的數復制到a[1][1].
同理，2*2表產生4*4表是將2*2表相應位置(即4*4表左上角)加2放到右上角，再復制到左下角，將左上角復制到右下角：

copy(a[][], n) m = n/2; for i 0 to m-1 dofor j 0 to m-1 doa[i][j+m] = a[i][j]+m;a[i+m][j] = a[i][j+m];a[i+m][j+m] = a[i][j];

5．copyodd(a[][], n)為第二種情況的日程產生方法，上面我們已經了解了隊數為6時的產生情況，我們把情況一般化，隊數為n，且m=n/2為奇數，且隊數為m+1的子情況已經解決：

因為2m+1已經超出n的范圍，所以我們將值為m+1和2m+1的隊組成一組，即1—m+1,2—m+2,3—m+3,……,m—n.
因為它們之間都相差m，所以可以用一個數組b的索引和值的對應關系來表示：

至此，我們完成了部分對應關系，接著要解決m+2到n列的對應關系：
第1行還缺m+2……n;
第2行缺 m+3……n, m+1;
第3行缺 m+4……n, m+1,m+2;
……
第m行缺 m+1……n-1.
可以看出它們是在m+1到n之間循環取值，且每次取m-1個。所以，可以用一個包括2個m+1到n連續排列的數組表示：
0 1 …… m-1 m m+1 …… n-1
m+1 m+2 …… n m+1 m+2 …… n
剩下未分配的隨之解決。

copyodd(a[][], n) m = n/2; for i0 to n-1 dob[i] = m+i+1; for i0 to m-1 dofor j 0 to m-1 doif a[i][j]> m a[i][j] = b[i];a[i+m][j] = i+1;elsea[i+m][j] = a[i][j] + m;for j 1 to m-1a[i][m+j] = b[i+j];a[b[i+j]][m+j] = i+1;

循環賽算法到此完成。
數據結構：
一個二維數組a[n][n]存儲日程表，一個一維數組b[n]存儲映射關系。
效率分析：
T(n) = T(n/2)+f(n)
其中，f(n)為copy()的時間
f(n) = (n/2)^2
推出：T(n) = T(n/2)+(n/2)^2
因為二分可以分log n次，所以T(n) = (n/2)^2+(n/4)^2+…+1 ;
所以，T(n)∈O(n^2)。
參考資料：
http://www.cppblog.com/cdy20/archive/2009/04/01/78573.html?yyue=a21bo.50862.201879#_Toc225487252

http://www.cnblogs.com/hoojjack/p/4211941.html

http://www.cnblogs.com/kelin1314/archive/2009/07/15/1523905.html

總結

以上是生活随笔為你收集整理的循环赛算法分析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。