A. 因?yàn)椋梢阎?/span> “每個(gè)運(yùn)動(dòng)員要和所有其他運(yùn)動(dòng)員進(jìn)行一次比賽”則每個(gè)運(yùn)動(dòng)員總共進(jìn)行N-1場，又由每一場有兩個(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)行一場比賽”則沒人每天只能進(jìn)行1

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

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

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

比如N=3的時(shí)候，每場必須有兩個(gè)人，則每天只能有一場比賽，假設(shè)是1和2比賽，則3號(hào)運(yùn)動(dòng)員沒有對(duì)象比賽，所以一天最多一場比賽，這個(gè)比賽需要的比賽場數(shù)C=3場，則整個(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è)選手可以通過n/2個(gè)選手設(shè)計(jì)的比賽日程表來決定。遞歸地用一分為二的略對(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，將問題轉(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ī)模的問題做logN次f(n)

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

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

posted on 2009-04-01 15:21 爬閱讀(8044) 評(píng)論(0) 編輯收藏引用所屬分類: 作業(yè)算法相關(guān)雜項(xiàng)

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。




網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

<

2012年10月

>

日

一

二

三

四

五

六

30

1

2

3

4

5

6

9

11

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

4

5

6

7

8

9

10

常用鏈接

留言簿(7)

隨筆分類

隨筆檔案

文章分類

link

搜索

積分與排名

積分 - 255404
排名 - 102

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品