分治法循環賽日程表

算法分析與設計作業

 

 

 

 

 

 

 

 

 

姓名：蔡東赟

學號：3106007039

班級：06軟件04班

組員：蔡東赟

完成日期：2009-3-22

 

分治法循環日程表... 1

算法分析與設計作業... 1

姓名：蔡東赟... 1

學號：3106007039. 1

班級：06軟件04班... 1

組員：蔡東赟... 1

完成日期：2009-3-22. 1

目錄：

一、問題描述：單循環賽... 3

二、算法分析：... 3

1.    首先我要證明老師提供的問題，有錯誤。... 3

2.    算法思路(N可能為奇數，也可能是偶數) 3

總體思路：按分治策略，將所有分為兩半，n個選手可以通過n/2個選手設計的比賽日程表來決定。遞歸地用一分為二的略對選手進行分割，直到只剩下兩個選手。... 3

存儲結構：... 3

數組 a[i][j], a[i][j]表示運動員i在第j天所遇到的選手... 3

詳細思路：... 4

（1）分治法，... 4

（2）n為偶數的情況Copy（）函數：A.將左上角遞歸計算出的小塊的所有數字按其相對位置抄到右下角，B.將右上角的小塊的所有數字加n/2后按其相對位置抄到左下角，將左下角的小塊中的所有數字按其相對位置抄到右上角    4

（3）一般性描述：n為偶數; n是奇數時增加一個虛擬選手n+1，將問題轉換為n是偶數的情形。    4

（4） 判斷奇偶... 4

（5）makecopy（）與copy相似，并區分奇偶情況... 4

(6)copyodd(n)實現n/2為奇數的時候的復制... 4

三、時間效率：... 5

 

 

一、問題描述：單循環賽

•         賽程問題:    有N個運動員進行單循環賽，即每個運動員要和所有其他運動員進行一次比賽。

•         試用分治法為這N個運動員安排比賽日程。

•         要求每個運動員每天只進行一場比賽，

•         且整個賽程在N -1天內結束。

•         將運動員從1到N編號。

二、算法分析：

1.     首先我要證明老師提供的問題，有錯誤。

整個賽程，當N為偶數的時候，N-1天能夠結束，

而當N為奇數的時候，只能在至少N天結束，、

錯誤地方：原命題中“整個賽程在N-1天結束”，這在N為奇數下的情況不成立

 A. 因為，由已知 “每個運動員要和所有其他運動員進行一次比賽”則 每個運動員總共進行N-1場，又由每一場有兩個運動員參加，N個運動員就進行了[N*（N-1）]/2，設為C

   B.又因為已知“要求每個運動員每天只進行一場比賽”則沒人每天只能進行1

場，所有運動員為N，每一場由兩個運動員參加，

 當N為偶數的時候，每天只能出現的場數為N/2場,推出==》至少的天數為C/(N/2)=N-1場，這與命題中“且整個賽程在N -1天內結束。”不矛盾

 當N為奇數的時候，由于每個運動員每天只能進行一場，所以每天能進行的總場數最多只能為（N-1）/2場，則整個賽程的天數最少需要 天數 C/[(N-1)/2]=N天，這與原命題“且整個賽程在N -1天內結束。”矛盾，

比如N=3的時候，每場必須有兩個人，則每天只能有一場比賽，假設是1和2比賽，則3號運動員沒有對象比賽，所以一天最多一場比賽，這個比賽需要的比賽場數C=3場，則整個比賽需要的天數為C/1=3天

 

由此依照命題前部分要求得出，當N為偶數的情況 循環賽可以進行N-1天，當N為奇數的時候，循環賽至少要進行N天。

2.     算法思路(N可能為奇數，也可能是偶數)

總體思路：按分治策略，將所有分為兩半，n個選手可以通過n/2個選手設計的比賽日程表來決定。遞歸地用一分為二的略對選手進行分割，直到只剩下兩個選手。

對于N為奇數的情況可以虛擬多一個選手，使其編程N+1個選手的日程表，最然后忽略虛擬運動員參與的比賽。對于分割時候N/2的情況也做特殊處理, 前n/2輪比賽空選手與下一個未參賽的選手進行比賽

 

 

存儲結構：

數組 a[i][j], a[i][j]表示運動員i在第j天所遇到的選手

 

 

詳細思路：

（1）分治法，

    Tourna（n）：

If n==1  

       a[1][1]=1;return;

 

tourna(n/2);//遞歸分割

copy(n); //填表

 

（2）n為偶數的情況Copy（）函數：A.將左上角遞歸計算出的小塊的所有數字按其相對位置抄到右下角，B.將右上角的小塊的所有數字加n/2后按其相對位置抄到左下角，將左下角的小塊中的所有數字按其相對位置抄到右上角

Viod copy(int n){

   Int m=n/2;

   For i=1àm

      For j=1--->m{

   a[i][j+m]=a[i][j]+m;// 小塊的數值抄到右下角

   a[i+m][j]=a[i][j+m];// 右上抄到左下

   a[i+m][j+m]=a[i][j];//   左下抄到右上

}

        

}

----------------------------------------------------------------------------------------------------------------------

（3）一般性描述：n為偶數; n是奇數時增加一個虛擬選手n+1，將問題轉換為n是偶數的情形。

   tournament（n）:

       if n==1 : a[1][1]=1;return;//分割到最后

       if n為奇數 ：tournament（n+1）;return;//奇數的情況加上虛擬選手

       tournament（n/2）;//分割

       makecopy(n);//這個函數copy分n為偶數很n為奇數的情況

（4） 判斷奇偶

odd(n):

      Return n&1;

（5）makecopy（）與copy相似，并區分奇偶情況

     makecopy(n):

        if n/2>1 &&add(n/2) copyodd(n);//對n/2為奇數的情況的處理

        else copy(n);//偶數的情況

 (6)copyodd(n)實現n/2為奇數的時候的復制

    n/2奇數的一種處理方法：前n/2輪比賽空選手與下一個未參賽的選手進行比賽

 

 

    Copyodd(n):

       Int m=n/2

       For i=1→m

         b[i]=m+i;b[m+i]=b[i];

      

       for i=1→m

         for j=1→m+1{

            if a[i][j]>m:

                 a[i][j]=b[i];a[m+i][j]=(b[i]+m)%n;

            else

               a[m+i][j]=a[i][j]+m;

            for j=2→m

                a[i][m+j]=b[i+j-1];

                a[b[i+j-1]][m+j]=i

 

          }

三、時間效率：

 T(n)=T(n/2)+f(n)

 f(n)為copy的時間

f(n)=(n/2)^2

推出：T(n)=T(n/2)+(n/2)^2

N規模的問題做logN次f(n)

T(n)屬于O（∑O((n/(2^k))^2)） 1<=k<log(n) 也就是T(n)∈O(n^2)

計算規模減少，但是時間復雜度一樣增長