比賽日程安排_08845

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

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

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

4、a[im][j]=a[i][jm]由左上角小塊的值算出對應(yīng)的右下角小塊的值a[im][jm]=a[i][j]分析算法的時(shí)間性能迭代處理的循環(huán)體內(nèi)部有2個(gè)循環(huán)語句基本語句是最內(nèi)層循環(huán)體的賦值語句即填寫比賽日程表中的元素?；菊Z句的執(zhí)行次數(shù)是:T(n)=T(n)30(4)所以算法的時(shí)間復(fù)雜度為0(4)。下面推廣n為任意整數(shù):當(dāng)n小于或等于1時(shí)沒有比賽。當(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í)的比賽日程安排是一樣的。只不過每次和n1隊(duì)比賽的球隊(duì)都輪空。所以我們只需考慮n為偶數(shù)時(shí)情況(以上問題的詳細(xì)證明見《初等數(shù)論》北京大學(xué)出版社潘承洞)。下面僅對n為偶數(shù)進(jìn)行討論:(1)當(dāng)n2為偶數(shù)時(shí)與n=情形類似可用分治法求解。(2)當(dāng)n2為奇數(shù)時(shí)遞歸返回的輪空的比賽要