分治法循環(huán)賽日程表

算法分析與設(shè)計(jì)作業(yè)

 

 

 

 

 

 

 

 

 

姓名：蔡?hào)|赟

學(xué)號(hào)：3106007039

班級(jí)：06軟件04班

組員：蔡?hào)|赟

完成日期：2009-3-22

 

分治法循環(huán)日程表... 1

算法分析與設(shè)計(jì)作業(yè)... 1

姓名：蔡?hào)|赟... 1

學(xué)號(hào)：3106007039. 1

班級(jí)：06軟件04班... 1

組員：蔡?hào)|赟... 1

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

目錄：

一、問(wèn)題描述：?jiǎn)窝h(huán)賽... 3

二、算法分析：... 3

1.    首先我要證明老師提供的問(wèn)題，有錯(cuò)誤。... 3

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

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

存儲(chǔ)結(jié)構(gòu)：... 3

數(shù)組 a[i][j], a[i][j]表示運(yùn)動(dòng)員i在第j天所遇到的選手... 3

詳細(xì)思路：... 4

（1）分治法，... 4

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

（3）一般性描述：n為偶數(shù); n是奇數(shù)時(shí)增加一個(gè)虛擬選手n+1，將問(wèn)題轉(zhuǎn)換為n是偶數(shù)的情形。    4

（4） 判斷奇偶... 4

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

(6)copyodd(n)實(shí)現(xiàn)n/2為奇數(shù)的時(shí)候的復(fù)制... 4

三、時(shí)間效率：... 5

 

 

一、問(wèn)題描述：?jiǎn)窝h(huán)賽

•         賽程問(wèn)題:    有N個(gè)運(yùn)動(dòng)員進(jìn)行單循環(huán)賽，即每個(gè)運(yùn)動(dòng)員要和所有其他運(yùn)動(dòng)員進(jìn)行一次比賽。

•         試用分治法為這N個(gè)運(yùn)動(dòng)員安排比賽日程。

•         要求每個(gè)運(yùn)動(dòng)員每天只進(jìn)行一場(chǎng)比賽，

•         且整個(gè)賽程在N -1天內(nèi)結(jié)束。

•         將運(yùn)動(dòng)員從1到N編號(hào)。

二、算法分析：

1.     首先我要證明老師提供的問(wèn)題，有錯(cuò)誤。

整個(gè)賽程，當(dāng)N為偶數(shù)的時(shí)候，N-1天能夠結(jié)束，

而當(dāng)N為奇數(shù)的時(shí)候，只能在至少N天結(jié)束，、

錯(cuò)誤地方：原命題中“整個(gè)賽程在N-1天結(jié)束”，這在N為奇數(shù)下的情況不成立

 A. 因?yàn)?，由已?/span> “每個(gè)運(yùn)動(dòng)員要和所有其他運(yùn)動(dòng)員進(jìn)行一次比賽”則 每個(gè)運(yùn)動(dòng)員總共進(jìn)行N-1場(chǎng)，又由每一場(chǎng)有兩個(gè)運(yùn)動(dòng)員參加，N個(gè)運(yùn)動(dòng)員就進(jìn)行了[N*（N-1）]/2，設(shè)為C

   B.又因?yàn)?/span>已知“要求每個(gè)運(yùn)動(dòng)員每天只進(jìn)行一場(chǎng)比賽”則沒(méi)人每天只能進(jìn)行1

場(chǎng)，所有運(yùn)動(dòng)員為N，每一場(chǎng)由兩個(gè)運(yùn)動(dòng)員參加，

 當(dāng)N為偶數(shù)的時(shí)候，每天只能出現(xiàn)的場(chǎng)數(shù)為N/2場(chǎng),推出==》至少的天數(shù)為C/(N/2)=N-1場(chǎng)，這與命題中“且整個(gè)賽程在N -1天內(nèi)結(jié)束。”不矛盾

 當(dāng)N為奇數(shù)的時(shí)候，由于每個(gè)運(yùn)動(dòng)員每天只能進(jìn)行一場(chǎng)，所以每天能進(jìn)行的總場(chǎng)數(shù)最多只能為（N-1）/2場(chǎng)，則整個(gè)賽程的天數(shù)最少需要 天數(shù) C/[(N-1)/2]=N天，這與原命題“且整個(gè)賽程在N -1天內(nèi)結(jié)束。”矛盾，

比如N=3的時(shí)候，每場(chǎng)必須有兩個(gè)人，則每天只能有一場(chǎng)比賽，假設(shè)是1和2比賽，則3號(hào)運(yùn)動(dòng)員沒(méi)有對(duì)象比賽，所以一天最多一場(chǎng)比賽，這個(gè)比賽需要的比賽場(chǎng)數(shù)C=3場(chǎng)，則整個(gè)比賽需要的天數(shù)為C/1=3天

 

由此依照命題前部分要求得出，當(dāng)N為偶數(shù)的情況 循環(huán)賽可以進(jìn)行N-1天，當(dāng)N為奇數(shù)的時(shí)候，循環(huán)賽至少要進(jìn)行N天。

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

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

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

 

 

存儲(chǔ)結(jié)構(gòu)：

數(shù)組 a[i][j], a[i][j]表示運(yùn)動(dòng)員i在第j天所遇到的選手

 

 

詳細(xì)思路：

（1）分治法，

    Tourna（n）：

If n==1  

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

 

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

copy(n); //填表

 

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

Viod copy(int n){

   Int m=n/2;

   For i=1àm

      For j=1--->m{

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

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

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

}

        

}

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

（3）一般性描述：n為偶數(shù); n是奇數(shù)時(shí)增加一個(gè)虛擬選手n+1，將問(wèn)題轉(zhuǎn)換為n是偶數(shù)的情形。

   tournament（n）:

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

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

       tournament（n/2）;//分割

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

（4） 判斷奇偶

odd(n):

      Return n&1;

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

     makecopy(n):

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

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

 (6)copyodd(n)實(shí)現(xiàn)n/2為奇數(shù)的時(shí)候的復(fù)制

    n/2奇數(shù)的一種處理方法：前n/2輪比賽空選手與下一個(gè)未參賽的選手進(jìn)行比賽

 

 

    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

 

          }

三、時(shí)間效率：

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

 f(n)為copy的時(shí)間

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

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

N規(guī)模的問(wèn)題做logN次f(n)

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

計(jì)算規(guī)模減少，但是時(shí)間復(fù)雜度一樣增長(zhǎng)