比賽日程安排_08845

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

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

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

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

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