《算法設(shè)計與分析課程設(shè)計報告(共10頁).doc》由會員分享，可在線閱讀，更多相關(guān)《算法設(shè)計與分析課程設(shè)計報告(共10頁).doc（10頁珍藏版）》請在匯文網(wǎng)上搜索。

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

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

3、0 8 1 1 1輸出：顯示主元素是1。四、 算法分析與步驟描述選擇一個元素作為劃分起點(diǎn)，然后用快速排序的方法將小于它的移動到左邊，大于它的移動到右邊。這樣就將元素劃分為兩個部分。此時，劃分元素所在位置為k。如果k>n/2，那么繼續(xù)用同樣的方法在左邊部分找；如果k<n/2就在右邊部分找；k=n/2就找到了中位元素。根據(jù)快速排序的思想，可以在平均時間復(fù)雜度為O(n)的時間內(nèi)找出一個數(shù)列的中位數(shù)。然后再用O(n)的時間檢查它是否是主元素。五、 問題實例及算法運(yùn)算步驟首先運(yùn)行程序，按照提示輸入數(shù)據(jù)；其次求出在數(shù)組T0:n中出現(xiàn)次數(shù)最多的元素x出現(xiàn)的次數(shù)k；然后用select方法線性時間選

4、擇，找到第（n+1）/2大的數(shù)；用QuickSort進(jìn)行快速排序；用Partition方法進(jìn)行數(shù)組劃分，用swap將小于x的元素移到x左邊，大于x的元素移到x右邊；然后就可以得到時候存在主元素，輸出到屏幕上。從屏幕得到數(shù)組0 0 1 1 0 8 1 1 1后，可以得到出現(xiàn)次數(shù)最多的元素為1，其次數(shù)為5，第（n+1）/2大的數(shù)字為0,可以判斷存在主元素，然后進(jìn)行快排，移動元素得到數(shù)組為0 0 0 1 1 1 1 1 8，此時就可以得到主元素為1。六、 算法運(yùn)行截圖七、 算法復(fù)雜度分析根據(jù)快速排序的思想，可以在平均時間復(fù)雜度為O(n)的時間內(nèi)找出一個數(shù)列的中位數(shù)。然后再用O(n)的時間檢查它是否是

5、主元素, 時間復(fù)雜度分析master()中求中位數(shù)可以在平均時間復(fù)雜度為O(n)的時間內(nèi)完成,檢查中位數(shù)是否是主元素耗時O(n),所以時間復(fù)雜度為O(n)。第三章 字符串問題一、 算法問題描述設(shè)A和B是兩個字符串，要用最少的字符操作將字符串A轉(zhuǎn)換為字符串B字符串操作包括，1）刪除一個字符2）插入一個字符3）將一個字符改為另一個字符將字符串A變換成字符串B所用的最少字符操作數(shù)稱為字符串A到B的編輯距離，記為d（A，B）。試著設(shè)計一個有效算法，對任意給出的倆個字符串A和B，計算出他們的編輯距離d(A,B)。二、 算法問題形式化表示定義一個二維數(shù)組D存儲中間結(jié)果，如下圖所示，為已經(jīng)初始化后的情況。然

6、后從D1,1開始從左到右，從上到下依次按填表，表的最后一個元素Dm,n就是要求的最終結(jié)果。 01234560012345611      22      33      44      55      66      三、 期望輸

7、入與輸出輸入：由文件input.txt 提供輸入數(shù)據(jù)，文件的第一行是字符串A，文件的第二行是文件B。輸出：程序運(yùn)結(jié)束時，將編輯距離d（A，B），輸出到文件output.txt的第一行中。四、 算法分析與步驟描述注意：報告中不附加程序代碼，主要程序要描述程序流程設(shè)所給的兩個字符串為A1:m和B1:n。定義Dij=d(A1:i,B1,j)。單字符a,b間的距離定義為：d(a,b)=0 (a=b)d(a,b)=1(a!=b)考察從字符串A1:i到字符串B1:j的變換?？煞殖梢韵聨追N情況：（1）字符Ai改為字符Bj；需要d(Ai,Bj)次操作。（2）刪除字符Ai；需要1次操作。（3）插入字符Bj；需要

8、1次操作。因此，Dij可遞歸地計算如下。Dij=minDi-1j-1+d(Ai,Bj),Di-1j+1,Dij-1+1。五、 問題實例及算法運(yùn)算步驟例子：下面實際解決一下從srcStr = "bd"  到 dstStr = "abcd"的過程，上面這三種情況分別是初始化的時候要做的,首先用一維數(shù)組表示兩位數(shù)組,縱向 i = 0 -> m+1 ， di * (n + 1) = i 橫向 i = 0 -> n+1, di = I,即：如下圖是初始化之后的表格信息，縱向是b,d   橫向是a,b,c,d步驟：for(i

9、 = 1 -> 2)     /  2為“bd"的長度   for( j = 1 -> 4 )   / 4 為”abcd"的長度為了確定d i j 的大小， 需要比較a)從d i - 1 j - 1 修改字符srcStri - 1, 使之變?yōu)閐stStrj - 1, 如果srcStri - 1 = dstStrj - 1 則這一步可以免去b)從d i - 1 j 在srcStr的 i - 1處添加一個字符，使字符srcStr i - 1 變?yōu)閐stStr j - 1 c)從

10、d i j - 1 在dstStr的 j - 1 處刪除一個字符,使字符dstStr j - 1 變?yōu)閟rcStr i - 1,三者之間的最小值賦給d i j 六、 算法運(yùn)行截圖七、 算法復(fù)雜度分析從上面算法可以看出，該算法時間復(fù)雜性為0(m*n),空間復(fù)雜性為O（m*n）。同時可以看出，當(dāng)對第i行進(jìn)行填表時，只需要用到第i-1行的數(shù)據(jù)，因此可以用一個一維數(shù)組dis0n代替二維數(shù)組D0m,0n，因此空間復(fù)雜性降為O(n)。第四章 磁帶存儲問題一、 算法問題描述設(shè)有n個程序1，2，n 要存放在長度為L的磁帶上。程序i 存放在磁帶上的長度是li ，1<=i<= n。這n個程序的讀取概率

11、分別為p1，p2， pn，且pi=1(i=1,2,.n)。如果將這n個程序按i1，i2， in的次序存放，則讀取程序所需的時間tr=cpik lik(k=1,2,.r)（可假定c為1）。這n 個程序的平均讀取時間為t(1)+t(2)+.+t(r)。磁帶最優(yōu)存儲問題要求確定這n 個程序在磁帶上的一個存儲次序，使平均讀取時間達(dá)到最小。二、 算法問題形式化表示對于給定的N個程序存放在磁帶上的長度，計算磁帶上最多可以存儲的程序數(shù)和占用磁帶的長度三、 期望輸入與輸出輸入：input.txt給出輸入數(shù)據(jù)。第1行是正整數(shù)n，表示文件個數(shù)。接下來的n行中，每行有2個正整數(shù)a和b,分別表示程序存放在磁帶上的長度

12、和讀取概率。實際上第k個程序的讀取概率為ak/ai。對所有輸入的均假定c = 1。輸出：將編程計算出的最小平均讀取時間輸出到文件output.txt。輸入文件示例 輸出文件示例iput.txt output.txt6 15 3 5 4 9 7 8 3四、 算法分析與步驟描述因為長度和檢索該程序的時間成正比，輸入程序后，先按程序長度由小到大排序，即程序短的放在前面，則由題意的檢索方法可知該方法檢索時間最短。1.輸入n和L1,L2,.Ln;2.將L數(shù)組從小到大排序；3.計算出個個程序的從頭查到的檢索時間Ti；4.計算出最有存儲的平均檢索時間ST。五、 問題實例及算法運(yùn)算步驟最多數(shù)量是最優(yōu)先解決的問

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

14、如果采用7，9，12已經(jīng)超過磁帶最大上限所以停止查找,既此時最大個數(shù)3最大利用率24。六、 算法運(yùn)行截圖七、 算法復(fù)雜度分析時間復(fù)雜度為O(n)第五章 電路板問題一、 算法問題描述最小長度電路板排列問題是大規(guī)模電子系統(tǒng)設(shè)計中提出的實際問題。該問題的提法是，將n塊電路板以最佳排列方案插入帶有n個插槽的機(jī)箱中。n塊電路板的不同的排列方式對應(yīng)于不同的電路板插入方案。設(shè)B=1，2，n 是n塊電路板的集合。集合L= N 1 ， N 2 ， N m 是n塊電路板的m個連接塊。其中每個連接塊N i 是B的一個子集，且N i 中的電路板用同一根導(dǎo)線連接在一起。二、 算法問題形式化表示在最小長度電路板排列問題中，連接塊的長度是指該連接塊中第1 塊電路板到最后1塊電路板之間的距離。例如在圖示的電路板排列中，連接塊N 4 的第1 塊電路板在插槽3 中，它的最后1塊電路板在插槽6中，因此N 4 的長度為3。同理N 2 的長度為2。圖中連接塊最大長度為3。試設(shè)計一個分支限界法找出所