算法設(shè)計(jì)與分析課程設(shè)計(jì)報(bào)告

1、算法與分析課程設(shè)計(jì)報(bào)告題 目：算法設(shè)計(jì)和分析專業(yè)：網(wǎng)絡(luò)工程班級(jí)：1020552學(xué)號(hào)： 11姓名：赫前進(jìn)太原工業(yè)學(xué)院 計(jì)算機(jī)工程系2012年11月24日第二 章 主元 素 問 題1、 算 法 問 題描述主元素問題：設(shè)T0.n-1是n個(gè)元素的數(shù)組。對(duì)任一元素x,設(shè)S(x) =iTi=x。當(dāng)|S(x)|n/2 時(shí)，稱x為T的主元素。如果T中元素存在序關(guān) 系，按分治策略設(shè)計(jì)并實(shí)現(xiàn)一個(gè)線性時(shí)間算法，確定T0.n-1是否有一個(gè)主元素。2、 算 法 問 題形式化表示若 T 中存在主元素，則將T 分為兩部分后，T 的主元素也必為兩部分中至少一部分的主元素，因此可用分治法。將元素劃分為兩部分，遞歸地檢查兩部分有

2、無主元素。算法如下：若 T 只含一個(gè)元素，則此元素就是主元素，返回此數(shù)。將T分為兩部分T1和T2 (二者元素個(gè)數(shù)相等或只差一個(gè))，分別遞歸調(diào)用此方法求其主元素m1 和 m2。若ml和m2都存在且相等，則這個(gè)數(shù)就是 T的主元素，返回此數(shù)。若 m1 和 m2 都存在且不等，則分別檢查這兩個(gè)數(shù)是否為T 的主元素，若有則返回此數(shù)，若無則返回空值。若 m1 和 m2 只有一個(gè)存在，則檢查這個(gè)數(shù)是否為T 的主元素，若是則返回此數(shù)，若否就返回空值。若ml和m2都不存在，則T無主元素，返回空值。3、 期 望 輸 入與輸出輸入：數(shù)組中元素的個(gè)數(shù)9數(shù)組元素0 0 1 1 0 8 1 1 1輸出：顯示主元素是1。4

3、、 算 法 分 析與步驟描述選擇一個(gè)元素作為劃分起點(diǎn)，然后用快速排序的方法將小于它的移動(dòng)到左邊，大于它的移動(dòng)到右邊。這樣就將元素劃分為兩個(gè)部分。此時(shí)，劃分元素所在位置為k。如果kn/2 ,那么繼續(xù)用同樣的方法在左邊部分找；如果 k m+1 , di * (n +1) = i橫向i = 0 - n+1, di = I,即：如下圖是初始化之后的表格信息，縱向是b,d 橫向是 a,b,c,d1012341 2步驟：for(i = 1 - 2)/2 為 “bd”的長度for( j = 1- 4 )/ 4 為 abcd”的長度為了確定d i j 的大小，需要比較a)從 d i - 1 田-1修改字符 s

4、rcStri - 1,使之變?yōu)?dstStrj - 1,如果srcStri - 1 = dstStrj - 1則這一步可以免去b)從di-1 j 在srcStr的i- 1處添加一個(gè)字符，使字符srcStri - 1 變?yōu)?dstStrj - 1 c)從d i j - 1 在dstStr的j - 1 處刪除一個(gè)字符，使字符dstStrj - 1 變?yōu)閟rcStri - 1,三者之間的最小值賦給d i j 六、算法運(yùn)行截圖input, arc Surina： please inpuu d季二 Scrmg:Rdmul匚 Art ay: 012341L13332235Edit Distanct ls:

5、： 2七、 算法 復(fù) 雜 度 分 析從上面算法可以看出，該算法時(shí)間復(fù)雜性為0(m*n),空間復(fù)雜性為O (m*n)。同時(shí)可以看出，當(dāng)對(duì)第i 行進(jìn)行填表時(shí)，只需要用到第i-1 行的數(shù)據(jù)，因此可以用一個(gè)一維數(shù)組dis0可代替二維數(shù)組 D0m,0n,因此空間復(fù)雜性降為 O(n)。第四 章 磁帶 存 儲(chǔ) 問 題1、 算 法 問 題描述設(shè)有n個(gè)程序1 ,2,n 要存放在長度為L的磁帶上。程序i存放在磁帶 上的長度是li , 1=i= n。這n個(gè)程序的讀取概率分別為pl, p2, pn,且2pi=1(i=1,2, - -.n) 0如果將這n個(gè)程序按i1 , i2 ,in的次序存放， 則讀取程序所需的時(shí)間t

6、r=c 2 pik lik(k=1,2,.)(可假定c為1)。這n個(gè)程序的平均讀取時(shí)間為t(1)+t(2)+.+t(r) 。磁帶最優(yōu)存儲(chǔ)問題要求確定這n個(gè)程序在磁帶上的一個(gè)存儲(chǔ)次序，使平均讀取時(shí)間達(dá)到最小。2、 算 法 問 題形式化表示對(duì)于給定的N個(gè)程序存放在磁帶上的長度，計(jì)算磁帶上最多可以存儲(chǔ)的程序數(shù) 和占用磁帶的長度3、 期 望 輸 入與輸出輸入：input.txt給出輸入數(shù)據(jù)。第1行是正整數(shù)n,表示文件個(gè)數(shù)。接下來的n 行中，每行有2 個(gè)正整數(shù)a 和 b, 分別表示程序存放在磁帶上的長度和讀取概率。實(shí)際上第k個(gè)程序的讀取概率為ak/2 ai。對(duì)所有輸入的均假定c = 1。輸出：將編程計(jì)算

7、出的最小平均讀取時(shí)間輸出到文件output.txt 。輸入文件示例輸出文件示例iput.txtoutput.txt 6 153 5 4 9 784、 算 法 分 析與步驟描述因?yàn)殚L度和檢索該程序的時(shí)間成正比，輸入程序后，先按程序長度由小到大排序，即程序短的放在前面，則由題意的檢索方法可知該方法檢索時(shí)間最短。1.輸入n 和L1,L2,.Ln;2 .將L 數(shù)組從小到大排序；3 .計(jì)算出個(gè)個(gè)程序的從頭查到的檢索時(shí)間Ti ；4 .計(jì)算出最有存儲(chǔ)的平均檢索時(shí)間ST。5、 問 題 實(shí) 例及算法運(yùn)算步 驟最多數(shù)量是最優(yōu)先解決的問題，然后再數(shù)量最大的前提下讓利用率站到最大,所以按照貪心策略先將占用的長度從小到

8、大進(jìn)行排序，以此輸入到磁帶中,62 4831 2797排序之后3,7,7,8,9,12，最佳組合應(yīng)為3912，先按照數(shù)量最多的前提下可存放3個(gè)程序3 7 7,然后進(jìn)行第2策略讓利用率最大，3+7+7 = 17 24-17 =7表明還剩下7個(gè)空間，從3, 7, 7最后一個(gè)數(shù)開始使其盡可能的大3, 7, 12=22,此時(shí)磁帶還剩下空間2,再從倒數(shù)第二個(gè)數(shù)開始使其盡可能的大，但是 最大上限不能超過12,3, 8, 12 = 23磁帶還剩下1空間，然后在分析比8大的 數(shù)9則3+9+12是24,再從倒數(shù)第三個(gè)數(shù)開始重復(fù)上述操作，但是比 3大一位是 7,如果采用7, 9, 12已經(jīng)超過磁帶最大上限所以停止

9、查找，既此時(shí)最大個(gè)數(shù)3最大利用率24。六、算法運(yùn)行截圖工閆霆仆Javad ar反聲第Q蟠集臼志區(qū)止,Tesffll (lava應(yīng)用程* D:新文件夾* mpiit.七比七七、算法復(fù)雜度分析時(shí)間復(fù)雜度為O(n)第五章電路板問題算法問題描述最小長度電路板排列問題是大規(guī)模電子系統(tǒng)設(shè)計(jì)中提出的實(shí)際問題。該問題的提法是，將n塊電路板以最佳排列方案插入帶有 n個(gè)插槽的機(jī)箱中。n塊電路 板的不同的排列方式對(duì)應(yīng)于不同的電路板插入方案。設(shè)B=1, 2,，n 是n塊電路板的集合。集合 L= N 1 , N 2 ,，Nm 是 n塊電路板的m個(gè)連接塊。其中每個(gè)連接塊 N i是B的一個(gè)子集，且N i中的電 路板用同一根

10、導(dǎo)線連接在一起。算法問題形式化表示在最小長度電路板排列問題中，連接塊的長度是指該連接塊中第 1塊電路板到 最后1塊電路板之間的距離。例如在圖示的電路板排列中，連接塊 N 4的第1 塊電路板在插槽3中，它的最后1塊電路板在插槽6中，因此N 4的長度為 3。同理N 2的長度為2。圖中連接塊最大長度為3。試設(shè)計(jì)一個(gè)分支限界法找出所給n個(gè)電路板的最佳排列，使得 m個(gè)連接塊中最大長度達(dá)到最小。對(duì)于給定的電路板連接塊，設(shè)計(jì)一個(gè)隊(duì)列式分支限界法，找出所給n個(gè)電路板的最佳排列，使得m個(gè)連接塊中最大長度達(dá)到最小。這8塊電路板的一個(gè)可能的排列如圖所示2 I 3 J 5678三、期望輸入與輸出輸入：第一行有2個(gè)正整

11、數(shù)n和m (1 m,n 20)。接下來的n行中，每行有 m 個(gè)數(shù)。第k行的第j個(gè)數(shù)為0表示電路板k不在連接塊j中，1表示電路板k 在連接塊j中。輸出：將計(jì)算出的電路板排列最小長度及其最佳排列輸出。第1行是最小長度；接下來的1行是最佳排列。Input :output :8 541 1 1 1 15 4 3 1 62 8 70 1 0 1 00 1 1 1 01 0 1 1 01 0 1 0 01 1 0 1 00 0 0 0 10 1 0 0 1四、算法分析與步驟描述當(dāng)i=n時(shí)，算法搜索到葉結(jié)點(diǎn)，所有n塊電路板都已經(jīng)排定， 其密度為cd;當(dāng) in時(shí)，電路板尚未排列完成。X1:i-1是當(dāng)前擴(kuò)展結(jié)點(diǎn)

12、所 相應(yīng)的部分排列，cd 是相應(yīng)的部分排列密度。在當(dāng)前部分排列之后加入一塊未排定的電路板，擴(kuò)展當(dāng)前部分排列產(chǎn)生當(dāng)前擴(kuò)展結(jié)點(diǎn)的一個(gè)子結(jié)點(diǎn)。對(duì)于這個(gè)子結(jié)點(diǎn)，計(jì)算新的部分排列密度ld如果ld=0。因此，最優(yōu)解被更新的次數(shù)為O (m ;更新當(dāng)前最優(yōu)解的時(shí)間為 O (mn o綜上可知，解電路板排列問題的回溯算法 backtrack所要的計(jì)算時(shí)間為 O (mn!)。第六章野人問題一、算法問題描述野人過河問題描述如下：有M個(gè)牧師和N個(gè)野人過河(M N),只有一條能裝下兩個(gè)人的船，在河的任何一方或者船上，如果野人的人數(shù)大于牧師的人數(shù)， 那么牧師就會(huì)有危險(xiǎn)。二、算法問題形式化表示該問題就是求解牧師和野人從左岸全

13、部擺渡到右岸的過程中，任何時(shí)刻滿足M (牧師數(shù)) N (野人數(shù))和M+律2的擺渡方案。由于牧師和野人數(shù)是一個(gè)常數(shù)，所以知道了一岸的情況，另一岸的情況也就知道了。因此為了簡便起見，在描述問題時(shí)，只描述一岸(如左岸)的情況就可以了。另外，該問題我們最關(guān)心的是在擺渡過程中，兩岸狀態(tài)的變化情況，因此 船上的情況并不需要直接表達(dá)出來。在一次擺渡過程中，船上究竟有幾個(gè)牧師 和野人，可以通過兩個(gè)相連的狀態(tài)簡單得到。三、期望輸入與輸出輸入：本程序的設(shè)計(jì)考慮到了野人和牧師的人數(shù)、船可以容納人數(shù)的動(dòng)態(tài)設(shè)計(jì)，按照題目的要求，首先輸入3個(gè)野人、3個(gè)牧師和船只容納2人，也可以根據(jù) 個(gè) 人的需求動(dòng)態(tài)輸入其他數(shù)據(jù)，輸入的數(shù)

14、據(jù)限定為正整數(shù)。輸出：輸出時(shí)野人和牧師每一次過河的過程都會(huì)進(jìn)行輸出，若動(dòng)態(tài)輸入的野人、牧師和船可以容納人數(shù)無法滿足安全渡河，則輸出“問題無解”四、算法分析與步驟描述先來看看問題的初始狀態(tài)和目標(biāo)狀態(tài)，假設(shè)和分為甲岸和乙岸：初始狀態(tài)：甲岸，3野人，3牧師；乙岸，0野人，0牧師；船停在甲岸，船上有0個(gè)人；目標(biāo)狀態(tài)：甲岸，0野人，0牧師；乙岸，3野人，3牧師；船停在乙岸，船上有0個(gè)人；整個(gè)問題就抽象成了怎樣從初始狀態(tài)經(jīng)中間的一系列狀態(tài)達(dá)到目標(biāo)狀態(tài)。問題 狀態(tài)的改變是通過劃船渡河來引發(fā)的，所以合理的渡河操作就成了通常所說的 算符，根據(jù)題目要求，可以得出以下 5個(gè)算符：渡1野人、渡1牧師、渡1野人1牧師、

15、渡2野人、渡2牧師算符知道以后，剩下的核心問題就是搜索方法了，本算法采用深度優(yōu)先搜索，通過一個(gè)FindNext()函數(shù)找出下一步可以進(jìn)行的渡河操作中的最優(yōu)操作，如果沒有找到則返回其父節(jié)點(diǎn)，看看是否有其它兄弟節(jié)點(diǎn)可以擴(kuò)展，然后用 Process()函數(shù)遞規(guī)調(diào)用FindNext()，一級(jí)一級(jí)的向后擴(kuò)展。五、問題實(shí)例及算法運(yùn)算步驟首先從比較簡單的入手，先設(shè) M=N= 3,則給定的問題可用下圖表示，圖中 L和 R表示左岸和右岸，B= 1或0分別表示有船或無船。約束條件是：兩岸上Lj即0*13 口IpM N,船上 M+ N 2。pL/反外0*3的0/B口其實(shí)就是五種狀態(tài)：1. 兩個(gè)野人過河2. 兩個(gè)牧師過河3. 一個(gè)野人一個(gè)牧師過河4. 一個(gè)牧師過河5. 一個(gè)野人過河只需對(duì)這5種狀態(tài)進(jìn)行搜索，直到得到問題的解，或者得到問題無解，搜索過 程即終止。六、算法運(yùn)行截圖第3步，從左岸向右岸運(yùn)送。個(gè)牧師和2個(gè)野人第3步:從右岸向左岸運(yùn)送口個(gè)枚肺和1個(gè)野人第3步:從左岸向右岸運(yùn)送。個(gè)私標(biāo)和2個(gè)好人第勺步；從右岸向左岸運(yùn)送0個(gè)牧師和1個(gè)野人第5步：從左岸向右岸運(yùn)送2個(gè)校師和。個(gè)好人第6步：從右岸向左出運(yùn)送1個(gè)牧師和1個(gè)好人第7步：從左