比賽日程安排_(tái)08845

1、摘要:對(duì)于單循環(huán)賽的比賽日程安排問(wèn)題利用分治算法給出了可讀性較好的設(shè)計(jì)并詳細(xì)分析了各種假設(shè)下的時(shí)間復(fù)雜度。中國(guó)論文網(wǎng)8view46102.ht關(guān)鍵詞:分治算法復(fù)雜度遞歸循環(huán)賽中圖分類(lèi)號(hào):TP301.6文獻(xiàn)標(biāo)識(shí)碼:A任何一個(gè)可以用計(jì)算機(jī)求解的問(wèn)題所需的計(jì)算時(shí)間都與其規(guī)模有關(guān)。問(wèn)題的規(guī)模越小越容易直接求解解題所需的計(jì)算時(shí)間也越少。分治法是計(jì)算機(jī)科學(xué)中經(jīng)常使用的一種算法。設(shè)計(jì)思想是將一個(gè)難以直接解決的大問(wèn)題分割成一些規(guī)模較小的相同問(wèn)題以便各個(gè)

2、擊破分而治之。但是不是所有問(wèn)題都適合用分治法解決。當(dāng)求解一個(gè)輸入規(guī)模為n且取值又相當(dāng)大的問(wèn)題時(shí)使用蠻力策略效率一般得不到保證。1分治法應(yīng)用條件及一般步驟1.1分治法的應(yīng)用條件若問(wèn)題能滿(mǎn)足以下所列條件就可以考慮用分治法來(lái)提高解決問(wèn)題的效率。(1)能將這n個(gè)數(shù)據(jù)分解成k個(gè)不同子集合且得到的k個(gè)子集合是可以獨(dú)立求解的子問(wèn)題其中1k=n(2)分解所得到的子問(wèn)題與原問(wèn)題具有相似的結(jié)構(gòu)便于利用遞歸或循環(huán)機(jī)制(3)合并各個(gè)子問(wèn)題的解就是原問(wèn)題的解。1

3、.2分治法的一般步驟采用分治算法解決問(wèn)題的基本步驟為:(10分解:將原問(wèn)題分解為若干個(gè)規(guī)模較小相互獨(dú)立與原問(wèn)題形式相同的子問(wèn)題(2)求解子問(wèn)題:若子問(wèn)題規(guī)模較小而容易被解決則直接解否則再繼續(xù)分解為更小的子問(wèn)題直到容易解決(3)合并:將已求解的各個(gè)子問(wèn)題的解合并為原問(wèn)題的解。需要注意的是不是所有的分治法都比簡(jiǎn)單的蠻力法更有效。由左上角小塊的值算出對(duì)應(yīng)的右上角小塊的值a[i][jm]=a[i][j]m由右上角小塊的值算出對(duì)應(yīng)的左下角小塊的值

4、a[im][j]=a[i][jm]由左上角小塊的值算出對(duì)應(yīng)的右下角小塊的值a[im][jm]=a[i][j]分析算法的時(shí)間性能迭代處理的循環(huán)體內(nèi)部有2個(gè)循環(huán)語(yǔ)句基本語(yǔ)句是最內(nèi)層循環(huán)體的賦值語(yǔ)句即填寫(xiě)比賽日程表中的元素?；菊Z(yǔ)句的執(zhí)行次數(shù)是:T(n)=T(n)30(4)所以算法的時(shí)間復(fù)雜度為0(4)。下面推廣n為任意整數(shù):當(dāng)n小于或等于1時(shí)沒(méi)有比賽。當(dāng)n是偶數(shù)時(shí)至少舉行n1輪比賽.當(dāng)n是奇數(shù)時(shí)至少舉行n輪比賽這時(shí)每輪必有一支球隊(duì)輪空。為了

5、統(tǒng)一奇數(shù)偶數(shù)的不一致性當(dāng)n為奇數(shù)時(shí)可以加入第n1支球隊(duì)(虛擬球隊(duì)實(shí)際上不存在)并按n1支球隊(duì)參加比賽的情形安排比賽日程。那么n(n為奇數(shù))支球隊(duì)時(shí)的比賽日程安排和n1支球隊(duì)時(shí)的比賽日程安排是一樣的。只不過(guò)每次和n1隊(duì)比賽的球隊(duì)都輪空。所以我們只需考慮n為偶數(shù)時(shí)情況(以上問(wèn)題的詳細(xì)證明見(jiàn)《初等數(shù)論》北京大學(xué)出版社潘承洞)。下面僅對(duì)n為偶數(shù)進(jìn)行討論:(1)當(dāng)n2為偶數(shù)時(shí)與n=情形類(lèi)似可用分治法求解。(2)當(dāng)n2為奇數(shù)時(shí)遞歸返回的輪空的比賽要