西電軟件學(xué)院算法實(shí)驗(yàn)報(bào)告模板2份

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第二次試驗(yàn)一、問題：Matrix-chain product分析：本題是矩陣鏈乘問題，需要求出最優(yōu)括號(hào)化方案。即在矩陣的乘法鏈上添加括號(hào)來改變運(yùn)算順序以使矩陣鏈乘法的代價(jià)降低?？梢苑治鲈撴湷说囊粋€(gè)子段總結(jié)一些結(jié)論。假設(shè)mi,j表示Ai*Aj的鏈成需要進(jìn)行的乘法次數(shù)（假設(shè)j-i足夠大），我們可以將Ai*Aj分為兩段進(jìn)行計(jì)算：（Ai*Ak）*（Ak+1*Aj）可以得出mi,j的遞推公式可以得出，當(dāng)i=j的時(shí)候，mi,j=0。當(dāng)i<j的時(shí)候。k的取值范圍是i到j(luò)-1，對(duì)于k的每一個(gè)取值都可以得到一個(gè)mi,j的值，取出最小值即時(shí)mi,j的最優(yōu)化方案。遞推公式如下：可以根

2、據(jù)上式得到一個(gè)遞歸算法。本題即是求m1,n的值。用二維數(shù)組m存儲(chǔ)mi,j的值，用二維數(shù)組s來儲(chǔ)存應(yīng)當(dāng)分割的位置。以本題中第一個(gè)矩陣a)<3, 5, 2, 1,10>為例，可以得出如下矩陣：通過m數(shù)組可以得出最少的乘法次數(shù)，通過s數(shù)組可以輸出最優(yōu)方案。遇到的問題：在輸出s數(shù)組的結(jié)果的時(shí)候仍然需要遞歸調(diào)用，需要合適的控制遞歸的條件。總結(jié)：在矩陣鏈乘問題中可以看出，動(dòng)態(tài)規(guī)劃結(jié)合遞歸的思想可以快捷的解決很多問題。本題中，重點(diǎn)是歸納出mi,j的遞推公式。二、問題：Longest Common Subsequence分析：本題即是最長(zhǎng)公共子序列問題。假設(shè)有序列Am和序列Bn，顯然，對(duì)于每一個(gè)i

3、,j，都對(duì)應(yīng)著一個(gè)公共子序列的長(zhǎng)度。假設(shè)長(zhǎng)度為c，就可以得到一個(gè)二維數(shù)組cm,n。對(duì)于ci,j，當(dāng)Ai=Bj的時(shí)候，問題就轉(zhuǎn)變?yōu)榍驛1.i-1和B1.j-1的公共子序列長(zhǎng)度的問題，所以ci，j的長(zhǎng)度就是ci-1，j-1 + 1;同理，當(dāng)Ai != Bj的時(shí)候，ci,j應(yīng)該在ci-1,j與ci,j-1中取最大值。另外，當(dāng)i或者j等于0的時(shí)候，顯然c的值為0。由上面所述，可以得到遞推公式如下：為了解決這個(gè)問題，還如要定義另一個(gè)數(shù)組用于存放c數(shù)組中每一個(gè)元素的來源。這個(gè)來源其實(shí)就反映了公共子串?？梢酝ㄟ^箭頭表示來源，相連的箭頭序列中指向左上方的箭頭最多的一串對(duì)應(yīng)的就是最長(zhǎng)公共子序列。比如對(duì)于題目中給

4、出的第一個(gè)例子X: xzyzzyx Y: zxyyzxz可以用一個(gè)矩陣表示計(jì)算的過程：遇到的問題：在算法中，=是屬于<還是>會(huì)給結(jié)果帶來不同。在輸出子序列的時(shí)候，最長(zhǎng)公共子序列可能不止一個(gè)，但是最終未能解決還是只能輸出一個(gè)?？偨Y(jié)：最長(zhǎng)公共子序列問題可以利用動(dòng)態(tài)規(guī)劃很好的解決。動(dòng)態(tài)規(guī)劃的思想就是根據(jù)規(guī)律獲得推導(dǎo)公式，然后解決問題。三、問題：Longest Common Substring分析：最長(zhǎng)公共子序列問題就是和最長(zhǎng)公共子串問題差不多，就是當(dāng)當(dāng)Ai != Bj的時(shí)候，對(duì)應(yīng)的ci，j置為0。推導(dǎo)公式如下：最終c數(shù)組的最大值max對(duì)應(yīng)的就是最長(zhǎng)公共子串，只需要將從本位置向前述max-

5、1個(gè)的子串即是所求子串。總結(jié)：本題就是第二題的一種特殊的情況，即c數(shù)組中的值不能從左和上兩個(gè)方向獲取，其他基本相同。在代碼上，只需要修改小部分代碼就可以實(shí)現(xiàn)該問題。四、問題：Max Sum分析：求和最大的子串。這個(gè)問題和第三題很像，不過這次不用二維數(shù)組而是使用兩個(gè)標(biāo)記來標(biāo)志所求子串的起始位置（maxb）結(jié)束位置（maxe）。思路是，對(duì)于第i個(gè)元素，如果當(dāng)前元素與目前選中的序列的sum小于0，那么這么序列不會(huì)被選擇，更新sumb與sume的值；如果sum仍然大于0，則sum可以選中。比較sum與max的值，如果sum>max，則更新maxb與maxe的值。遞推公式如下：遇到的問題：在全是負(fù)

6、數(shù)時(shí)出現(xiàn)問題，后來講max的初始值設(shè)置為第一個(gè)元素的值后就能正常了。總結(jié)：動(dòng)態(tài)規(guī)劃能解決很多問題，找到遞推公式非常重要。五、問題：Shortest path in multistage graphs. Find the shortest path from 0 to 15 for the following graph.分析：觀察本題圖的特點(diǎn)，發(fā)現(xiàn)可以將圖分解為7個(gè)部分，以此可以計(jì)算到每一個(gè)節(jié)點(diǎn)的最短的路徑。即可求出最終的最短路徑。 總結(jié)：結(jié)合本題中的特殊情況，可以采用適當(dāng)?shù)姆椒▉硖幚怼５谌螌?shí)驗(yàn)一、問題：Knapsack Problem. There are 5 items that hav

7、e a value and weight list below, the knapsack can contain at most 100 Lbs. Solve the problem both as fractional knapsack and 0/1 knapsack.分析：本題是背包問題的兩個(gè)解法。對(duì)于部分背包來說比較簡(jiǎn)單，就是將單位價(jià)值大的物品優(yōu)先放置到背包中，這樣就能在背包中獲取最大的價(jià)值。但是對(duì)于0/1背包問題來說，就相對(duì)復(fù)雜了?？梢酝ㄟ^貪心算法解決。經(jīng)過分析，我們轉(zhuǎn)化這個(gè)問題為將n件物品放置到容量為w的容器中。這里，每件物品只可能有一個(gè)狀態(tài)：放入/不放入，我們用0/1來對(duì)應(yīng)。用

8、vi,w來表示前i件物品選出重量不超過w的物品，并且構(gòu)成的最大的價(jià)值。那么，可以分析得出vi,w的遞推式。如果i=0或者w=0，顯然vI,w = 0;如果第i件物品的重量wi>w則i不可能放入容器中；如果i能夠放入容器（即wi<w）則在vi+vi-1,w-wi > vi-1,w時(shí)才可能會(huì)放入。關(guān)系式如下這樣，我們可以認(rèn)為，每一次都恰到好處的選擇了放或者不放一個(gè)物品。直到最后一個(gè)物品，我們得到的一定就是最好的結(jié)果總結(jié)：背包問題是一個(gè)典型的貪心算法的例子。在解決問題的時(shí)候可以將當(dāng)前步驟做到最好，然后通過推導(dǎo)，有可能得到一個(gè)關(guān)系式，這樣就能使問題得到解決。在本題中，我們可以通過第i

9、件物品是否應(yīng)該放在容量的w的背包中進(jìn)行分析，最終得到了一個(gè)遞推式。二、問題：A simple scheduling problem. We are given jobs j1, j2 jn, all with known running times t1, t2 tn, respectively. We have a single processor. What is the best way to schedule these jobs in order to minimize the average completion time. Assume that it is a nonpreem

10、ptive scheduling: once a job is started, it must run to completion. The following is an instance。分析：這是一個(gè)線程調(diào)度問題，通過操作系統(tǒng)課程的學(xué)習(xí)，我們了解到應(yīng)當(dāng)采用短作業(yè)優(yōu)先的調(diào)度方式。可以采用快速排序?qū)M(jìn)程順序進(jìn)行排序即可得到調(diào)度時(shí)間?？偨Y(jié)：在進(jìn)程調(diào)度問題中，如果想獲取最短的平均周轉(zhuǎn)時(shí)間（單線程）應(yīng)當(dāng)使用短作業(yè)優(yōu)先的算法。三、問題：?jiǎn)卧袋c(diǎn)最短路徑分析：本題中，因?yàn)槁窂街写嬖谪?fù)邊，所以應(yīng)當(dāng)使用bellman-ford算法。為了方便的使用該算法，需要首先創(chuàng)建合適的邊的數(shù)據(jù)結(jié)構(gòu)。這樣，在遍歷邊的時(shí)候

11、比較快捷。首先需要初始化每一個(gè)節(jié)點(diǎn)的d值，源點(diǎn)的d值為0，其他點(diǎn)的d值的初始值為max（一個(gè)足夠大的數(shù)）。表示在初始時(shí)，源點(diǎn)到各點(diǎn)都不可達(dá)。然后，對(duì)每條邊進(jìn)行松弛操作，進(jìn)行|V|-1次松弛之后，可以得到結(jié)果。隨后，檢測(cè)結(jié)果，如果依然存在可松弛的節(jié)點(diǎn)的話，說明存在權(quán)重為負(fù)的環(huán)路。表明結(jié)果不存在?？偨Y(jié)：該算法并沒有在一開始就計(jì)算是否存在權(quán)值為負(fù)的環(huán)路。而是通過結(jié)果來分析，如果沒有負(fù)環(huán)路，一定能在松弛循環(huán)結(jié)束后便不能繼續(xù)被松弛。由此，可以判斷是否存在最短路徑。所以，該算法不僅可以判斷一個(gè)圖是否存在最短路徑，還能得到最短路徑。四、問題：All-pairs shortest paths分析：所有節(jié)點(diǎn)對(duì)的

12、最短路徑問題，應(yīng)當(dāng)使用Johnson算法。Johnson算法需要用dijkstra和bellman-ford算法作為子程序。如果圖G=（V,E）中所有的邊權(quán)重都為非負(fù)值，可以通過在每一個(gè)節(jié)點(diǎn)使用dijkstra算法求出所有節(jié)點(diǎn)虹之間的最短路徑；如果該圖包含權(quán)值為負(fù)的邊，但是沒有權(quán)重為負(fù)的環(huán)路，那么只要計(jì)算一組新的非負(fù)權(quán)重值，然后使用同樣的方法即可?？偨Y(jié)：Johnson算法相當(dāng)于是對(duì)dijkstra算法和bellman-ford算法的應(yīng)用，結(jié)合這兩個(gè)算法，通過使用重新賦值權(quán)重來生成非負(fù)權(quán)重，最終得到所有節(jié)點(diǎn)對(duì)之間的最短路徑。第四次實(shí)驗(yàn)一、題目：0/1 Knapsack Problem. Ther

13、e are 5 items that have a value and weight list below, the knapsack can contain at most 100 Lbs. Solve the problem using back-tracking algorithm and try to draw the tree generated.分析：使用回溯法解決0/1背包問題。可以用一個(gè)數(shù)組來記錄“選中”物品的情況。首先，選擇第一件物品，如果超重的話不選擇該物品；如果沒有超重，繼續(xù)添加下一個(gè)物品，這樣選擇下去，最終一定可以選擇完全部的物品。計(jì)算目前選擇物品的totalValue

14、值。繼續(xù)回溯，如果的到新的totalValue值，如果大于前一個(gè)值，那么更新該值，并且更新保存選擇的數(shù)組中?？偨Y(jié)：從8皇后問題可以發(fā)現(xiàn)回溯法的一般方法。經(jīng)過代入到這個(gè)問題中，發(fā)現(xiàn)確實(shí)可行?；厮莘ㄐ枰粋€(gè)合理的遞歸函數(shù)，這個(gè)函數(shù)的終止條件也需要認(rèn)真的分析。比如這一題和8皇后問題都可以使用元素的個(gè)數(shù)作為一個(gè)結(jié)束條件，另外還需要注意導(dǎo)致“回溯”的位置。二、題目：Solve the 8-Queen problem using back-tracking algorithm.分析：8皇后問題是回溯法的一個(gè)典型的例題。假設(shè)目前已經(jīng)在奇葩的前i（i<8）行放置了i和皇后并且位置合法。然后我們放置第j（

15、j=i+1）個(gè)皇后，先將j放置在第一列，如果合法就放置第j+1個(gè)皇后；如果放置在當(dāng)前列不合法，就將j皇后放置在第二列以此類推，如果全部不行，將會(huì)返回調(diào)用該函數(shù)的上一層函數(shù)。如果i的值等于8，說明已經(jīng)完全擺放成功，就可以輸出結(jié)果，輸出后返回上一層調(diào)用，繼續(xù)查找其他的符合題意的皇后擺放。總結(jié)：使用回溯法，能后很好的解決8皇后問題。在使用回溯法是，應(yīng)當(dāng)注意如何使用遞歸調(diào)用，尤其是遞歸調(diào)用的結(jié)束條件。第2份 算法導(dǎo)論上機(jī)實(shí)驗(yàn)報(bào)告冊(cè) 班級(jí)： 學(xué)號(hào)： 姓名： 周家煒 教師： 張立勇 實(shí)驗(yàn)一 排序算法題目一： 1、題目描述：描述一個(gè)運(yùn)行時(shí)間為(nlgn)的算法，給定n個(gè)整數(shù)的集合S和另一個(gè)整數(shù)x，該算法能確

16、定S中是否存在兩個(gè)其和剛好為x的元素。 2、所用算法：1、運(yùn)用歸并排序算法 2、在已經(jīng)排好序的基礎(chǔ)上，對(duì)其運(yùn)用二分查找。 3、算法分析：（1）歸并排序運(yùn)用的是分治思想，時(shí)間復(fù)雜度為 (nlgn)，能夠滿足題目要求的運(yùn)行時(shí)間。歸并排序的分解部分是每次將數(shù)組劃分兩個(gè)部分，時(shí)間復(fù)雜度為（1）；再對(duì)已經(jīng)分解的兩個(gè)部分再進(jìn)行分解直到將數(shù)組分解成單個(gè)元素為止；解決部分是遞歸求解排序子序列；合并部分是將已經(jīng)排序的子序列進(jìn)行合并得到所要的答案，時(shí)間復(fù)雜度為(lgn)。（2）二分查找算法的時(shí)間復(fù)雜度為(lgn)在題目要求的范圍內(nèi)，二分查找的條件為待查的數(shù)組為有序序列。算法的主要思想為設(shè)定兩個(gè)數(shù)，low指向最低元

17、素，high指向最高元素，然后比較數(shù)組中間的元素與待查元素進(jìn)行比較。如果待查元素小于中間元素，那么表明查找元素在數(shù)組的前半段；反之，如果待查元素大于中間元素，那么表明查找元素在數(shù)組的后半段。 4、結(jié)果截圖： 5、總結(jié)：（1）在主函數(shù)中調(diào)用二分查找的時(shí)候，參數(shù)應(yīng)該為BinSearch(a,j+1,n,x-aj），從j+1開始遍歷而不是都是從第一個(gè)開始。（2）遇到的困難為：由于程序語言規(guī)定數(shù)組的下標(biāo)從0開始，而算法偽代碼要求從1開始，因此在定義數(shù)組大小的時(shí)候?qū)?shù)字加1，但是在編譯運(yùn)行的時(shí)候會(huì)得不到想要的結(jié)果，出現(xiàn)數(shù)組下標(biāo)訪問錯(cuò)誤。 采取的解決方案為：在開始定義數(shù)組的時(shí)候，將數(shù)組的大小定義為一個(gè)較大

18、的數(shù)字，如1000。避免在運(yùn)行時(shí)出現(xiàn)錯(cuò)誤，但是造成了空間的浪費(fèi)。較好的方案為使用動(dòng)態(tài)數(shù)組，如malloc函數(shù)。題目二： 1、題目描述：實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列，即需要支持以下操作：INSERT(S,x):把元素x插入到集合S中；MAXMUM(S):返回S中具有最大key的元素；EXTRACT-MAX(S):去掉并返回S中的具有最大key的元素；INCREASE-KEY(S,x,k)：將元素x的關(guān)鍵字值增到k。 2、所用算法：堆排序，運(yùn)用堆來實(shí)現(xiàn)優(yōu)先隊(duì)列。 3、算法分析： （1）堆排序算法是引用堆這個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行信息管理。堆排序的時(shí)間復(fù)雜度是(nlgn),但是與歸并排序不同的是堆排序具有空間的原址性，任何

19、時(shí)候都只需要常數(shù)個(gè)額外的元素空間存儲(chǔ)臨時(shí)數(shù)據(jù)。堆排序算法分為3個(gè)過程，MAX-HEAPIEY:調(diào)整堆以滿足小頂堆性質(zhì)，其時(shí)間復(fù)雜度為(lgn)；BUILD-MAXHEAP:從無序的輸入數(shù)據(jù)數(shù)組中構(gòu)造小頂堆，其時(shí)間復(fù)雜度為線性時(shí)間;HEAP-SORT:對(duì)數(shù)組進(jìn)行原址排序，其時(shí)間復(fù)雜度為(nlgn)。 （2）在堆的基礎(chǔ)上實(shí)現(xiàn)優(yōu)先隊(duì)列INSERT、MAXMUM、EXTRACT-MAX、INCREASE-KEY，時(shí)間復(fù)雜度為(lgn)。 4、結(jié)果截圖： 5、總結(jié)： 遇到的困難：沒有理解將一個(gè)序列轉(zhuǎn)換成小頂堆的過程，因此剛開始很難將偽代碼用c語言進(jìn)行實(shí)現(xiàn)。從結(jié)果可以看出，在編寫MAX-EXSTRACT函

20、數(shù)的時(shí)候，當(dāng)去掉第一個(gè)元素后，程序沒有調(diào)用MAX-HEAP進(jìn)行調(diào)整堆，因此最后序列是無序狀態(tài)。題目三： 1、題目描述：實(shí)現(xiàn)quick_sort算法，并且回答以下兩個(gè)問題：（1）待排數(shù)組中的元素值都相同的情況下，運(yùn)用quick_sort需要進(jìn)行多少次比較？（2）對(duì)于n個(gè)元素的數(shù)組，運(yùn)用quick_sort舉出需要進(jìn)行比較次數(shù)的上限和下限是多少？ 2、所用算法：快速排序算法 3、算法分析：快速排序采用分治策略，時(shí)間復(fù)雜度為(nlgn),但是最壞情況下為(n2),并且快速排序算法屬于原地排序，并不需要開辟空間。快速排序復(fù)雜的步驟為其分解的步驟，分解的過程：數(shù)組Ap.r被劃分為兩個(gè)子數(shù)組Ap.q-1和

21、Aq+1.r,使得Ap.q-1中的每個(gè)元素都小于Aq,而Aq也小于等于Aq+1.r中的每個(gè)元素。而在實(shí)現(xiàn)的過程總是選擇將Ar作為基準(zhǔn)點(diǎn)進(jìn)行劃分Ap.r數(shù)組。 4、結(jié)果截圖： 5、總結(jié)： 問題答案：（1）當(dāng)選取第一個(gè)或者最后一個(gè)為基準(zhǔn)點(diǎn)時(shí)，當(dāng)n個(gè)元素相同的時(shí)候?yàn)樽顗那闆r，比較次數(shù)為n*(n-1)/2;(2)快速排序比較次數(shù)最少為(nlgn),最大的比較次數(shù)為(n2)。題目四： 1、題目描述：運(yùn)用分治的策略將兩個(gè)已經(jīng)排好序的序列中，找出第k大的元素，且要求時(shí)間復(fù)雜度為(lgm+lgn),其中m和n分別為兩個(gè)序列的長(zhǎng)度。 2、所用策略：分治策略 3、算法分析： （1）分解：因?yàn)橐呀?jīng)是兩個(gè)獨(dú)立的的序列

22、，所以不用進(jìn)行分解。 （2）解決：因?yàn)閮蓚€(gè)序列為已經(jīng)排好的序列，因此不用分開進(jìn)行排序。 （3）利用歸并排序中的merge函數(shù)，將這兩個(gè)序列分別看成是L和R兩個(gè)數(shù)組，通過開辟一個(gè)新的數(shù)組，將兩個(gè)數(shù)組合并成一個(gè)新的排好序的序列，在根據(jù)要求的k值，對(duì)新的數(shù)組進(jìn)行取值。4、 結(jié)果截圖：5、 總結(jié)： （1）理解分治策略的三個(gè)步驟：分解、解決和合并對(duì)于具體問題的具體表現(xiàn)，要善于根據(jù)時(shí)間復(fù)雜度與所學(xué)的算法進(jìn)行結(jié)合，找出可以利用的地方。 實(shí)驗(yàn)二 動(dòng)態(tài)規(guī)劃題目一： 1、題目描述：用動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)矩陣鏈乘，保證相乘的次數(shù)最少。 2、所用策略：動(dòng)態(tài)規(guī)劃 3、算法分析： （1）最優(yōu)子結(jié)構(gòu)為：如果最優(yōu)的加括號(hào)的方式將其分

23、解為Ai.k與Ak+1.j的乘積，則分別對(duì)Ai.k與Ak+1.j加括號(hào)的方式也一定是最優(yōu)的。 （2）定義mi,j為計(jì)算矩陣Ai.j所需標(biāo)量乘法次數(shù)的最小值，對(duì)于i=j時(shí),矩陣鏈乘只包含唯一的矩陣Ai,因此不需要做任何標(biāo)量乘法運(yùn)算，所以mi,i=0;當(dāng)i<j時(shí)利用最優(yōu)子結(jié)構(gòu)來計(jì)算mi,j。 （3）矩陣鏈乘的遞歸式： （4）在算法設(shè)計(jì)的時(shí)候，需要m數(shù)組記錄Ai.j最小相乘次數(shù)，s數(shù)組記錄構(gòu)造最優(yōu)解所需要的信息，其記錄的k值指出了AiAi+1Aj的最優(yōu)括號(hào)化方案的分割點(diǎn)應(yīng)在AkAk+1之間。 （5）矩陣鏈乘的時(shí)間復(fù)雜度為(n3) 4、結(jié)果截圖： 5、總結(jié)： 遇到的問題：在構(gòu)建m數(shù)組和s數(shù)組的時(shí)

24、候需要構(gòu)建二維數(shù)組，而c語言中函數(shù)的參數(shù)列表中二維數(shù)組要指明數(shù)組大小，但是還沒有輸入信息的時(shí)候并沒有方法確定數(shù)組大小。 采取的方案：由于此次的例子只有兩種情況，因此對(duì)于 MATRIX_CHAIN_ORDER函數(shù)和PRINT_OPTIMAL_PARENS函數(shù)寫兩遍，大體的實(shí)現(xiàn)過程相同，只是數(shù)組的大小有所改變。并沒有解決這個(gè)情況，造成代碼的冗余。題目二： 1、題目描述：用動(dòng)態(tài)規(guī)劃求下列字符串的最長(zhǎng)公共子序列（LCS） 2、所用策略：動(dòng)態(tài)規(guī)劃 3、算法分析：（1） 最優(yōu)子結(jié)構(gòu)：令X=<x1,x2,.xm>和Y=<y1,y2,.,yn>為兩個(gè)序列，Z=<z1,z2,.,z

25、k>為X和Y的任意LCS。1、如果xm=yn,則zk=xm=yn且Zk-1是Xm-1和Yn-1的一個(gè)LCS.2、如果xmyn,則zkxm意味著Z是Xm-1和Y的一個(gè)LCS；3、如果xmyn,則zkyn意味著Z是X和Yn-1的一個(gè)LCS。（2） 定義一個(gè)bi,j指向表項(xiàng)對(duì)應(yīng)計(jì)算ci,j時(shí)所選擇的子問題最優(yōu)解，過程返回表b和表c，cm,n保持X和Y的LCS長(zhǎng)度。（3） LCS的遞歸式為： （4） LCS的時(shí)間復(fù)雜度為(m+n),b表的空間復(fù)雜度為(mn)。 4、結(jié)果截圖： 5、總結(jié)： 用動(dòng)態(tài)規(guī)劃求取最長(zhǎng)公共子序列的時(shí)候，要理解b數(shù)組的用途和使用。 遇到的困難：編寫的代碼無法針對(duì)字符串大小未定

26、情況下，進(jìn)行求解LCS這導(dǎo)致了代碼的冗余。題目三： 1、題目描述：用動(dòng)態(tài)規(guī)劃求取以下字符串的最長(zhǎng)公共子串。 2、所用策略：動(dòng)態(tài)規(guī)劃 3、算法分析： （1）最優(yōu)子結(jié)構(gòu)：令X=<x1,x2,.xm>和Y=<y1,y2,.,yn>為兩個(gè)序列，Z=<z1,z2,.,zk>為X和Y的任意最長(zhǎng)公共子串。1、如果xm=yn,則zk=xm=yn且Zk-1是Xm-1和Yn-1的一個(gè)最長(zhǎng)公共子串.2、如果xmyn,則zkxm意味著Z是Xm-1和Y的一個(gè)最長(zhǎng)公共子串；3、如果xmyn,則zkyn意味著Z是X和Yn-1的一個(gè)最長(zhǎng)公共子串。 （2）定義Li,j為以xi和yj為結(jié)尾的相

27、同子串的最大長(zhǎng)度。記錄著X和Y的最長(zhǎng)公共子串的最大長(zhǎng)度。 （3）最長(zhǎng)公共子串的遞歸式： （4）最長(zhǎng)公共子串的時(shí)間復(fù)雜度為(mn)，空間復(fù)雜度為(mn)。 4、結(jié)果截圖： 5、總結(jié)： 要同上述的最長(zhǎng)公共子序列進(jìn)行對(duì)比，區(qū)分他們的不同之處。也要理解用動(dòng)態(tài)規(guī)劃求解時(shí)的相同之處和不同之處。題目四： 1、題目描述：給定n個(gè)整數(shù)（可能為負(fù)數(shù)）組成的序列，a1,a2.an,求該序列ai+ai+1.aj的子段和的最大值。 2、所用策略：動(dòng)態(tài)規(guī)劃 3、算法分析: (1)最優(yōu)子結(jié)構(gòu)：定義當(dāng)所給整數(shù)全為負(fù)數(shù)的時(shí)候，最大子段和為0,則最大子段和為max0,ai+ai+1.+aj,1ijn (2)引入一個(gè)輔助數(shù)組b,動(dòng)

28、態(tài)規(guī)劃的分解分為兩步：(1)計(jì)算輔助數(shù)組的值；(2)計(jì)算輔助數(shù)組的最大值。輔助數(shù)組bj用來記錄以j為尾的子段以及集合中的最大子段和。 (3)最大子段和的遞歸式： (4)最大子段和使用動(dòng)態(tài)規(guī)劃進(jìn)行計(jì)算的時(shí)間復(fù)雜度為(n)。 4、結(jié)果截圖： 5、總結(jié)： 在求解集合的最大子段和的時(shí)候，要對(duì)比不同解決方法的不同之處，感受用動(dòng)態(tài)規(guī)劃解決的便捷。題目五： 1、題目描述：利用動(dòng)態(tài)規(guī)劃求出多段圖中的最短路徑 2、所用策略：動(dòng)態(tài)規(guī)劃 3、算法分析： （1）可以由圖可知，圖中的頂點(diǎn)講圖劃分7個(gè)階段，分別了解每個(gè)階段可以有幾種可供選擇的店，引入fk表示狀態(tài)k到終點(diǎn)狀態(tài)的最短距離。最優(yōu)子結(jié)構(gòu)為：當(dāng)前狀態(tài)的fk由上個(gè)狀

29、態(tài)的fk-1和狀態(tài)k-1到狀態(tài)k的距離決定決策：當(dāng)前狀態(tài)應(yīng)在前一個(gè)狀態(tài)的基礎(chǔ)上獲得。決策需要滿足規(guī)劃方程,規(guī)劃方程：f(k)表示狀態(tài)k到終點(diǎn)狀態(tài)的最短距離。 （2）多段圖最短路徑的遞歸式： 4、結(jié)果截圖： 無。 5、總結(jié)： （1）遇到的問題：無法將多段圖的每個(gè)階段點(diǎn)的狀態(tài)表示并記錄下來。并不了解如何將動(dòng)態(tài)規(guī)劃與貪心算法的如迪杰斯特拉算法進(jìn)行對(duì)比，真正從最優(yōu)子結(jié)構(gòu)將最短路徑表示出來。實(shí)驗(yàn)三 貪心算法題目一： 1、題目描述：背包問題，即分別計(jì)算出在0-1背包和分?jǐn)?shù)背包情況下的計(jì)算結(jié)果。 2、所用策略：動(dòng)態(tài)規(guī)劃和貪心策略 3、算法分析： （1）0-1背包問題：所選擇的的貪心策略為按照選擇單位重量?jī)r(jià)值

30、最大的物品順序進(jìn)行挑選。算法的步驟：設(shè)背包容量為C，共有n個(gè)物品，物品重量存放在數(shù)組Wn中，價(jià)值存放在數(shù)組Vn中，問題的解存放在數(shù)組Xn中。第一步：改變數(shù)組W和V的排列順序，使其按單位重量?jī)r(jià)值Vi/Wi降序排列，并將數(shù)組Xn初始化為0；第二步初始化i=0，設(shè)計(jì)一個(gè)循環(huán)，循環(huán)終止條件為（Wi>C），循環(huán)體為將第i個(gè)物品放入背包：Xi=1;C=C-Wi;i+；最后一步：將結(jié)果存入到X數(shù)組中。 （2）分?jǐn)?shù)背包問題：所選擇的的貪心策略為按照選擇單位重量?jī)r(jià)值最大的物品順序進(jìn)行挑選。算法的步驟：設(shè)背包容量為C，共有n個(gè)物品，物品重量存放在數(shù)組Wn中，價(jià)值存放在數(shù)組Vn中，問題的解存放在數(shù)組Xn中。第

31、一步：改變數(shù)組W和V的排列順序，使其按單位重量?jī)r(jià)值Vi/Wi降序排列，并將數(shù)組Xn初始化為0；第二步初始化i=0，設(shè)計(jì)一個(gè)循環(huán)，循環(huán)終止條件為（Wi>C），循環(huán)體為將第i個(gè)物品放入背包：Xi=1;C=C-Wi;i+；最后一步：將結(jié)果存入到X數(shù)組中Xi=C/Wi。 （3）分?jǐn)?shù)背包問題所采用的貪心策略之不能得到最優(yōu)解，是由于物品不允許分割，因此，無法保證最終能將背包裝滿，部分閑置的背包容量使背包的單位重量?jī)r(jià)值降低了。 （4）分?jǐn)?shù)背包問題采用選擇單位重量?jī)r(jià)值最大的物品順序進(jìn)行挑選，其算法的時(shí)間復(fù)雜度為(nlgn)。 4、結(jié)果截圖： 5、總結(jié)： 使用貪心策略解決0-1背包問題得出的結(jié)果并不是最優(yōu)

32、解，這是由于所用的選擇策略不同。題目二： 1、題目描述：一個(gè)簡(jiǎn)單的調(diào)度問題，給予工作編號(hào)為J1，J2.Jn，已知所以工作的運(yùn)行時(shí)間分別為T1，T2.TN。有一個(gè)單獨(dú)的處理器，為了安排這些工作以到達(dá)減少平均完成時(shí)間的最好方法是什么。假定它是一個(gè)非搶占式調(diào)度：一旦工作開始，它必須運(yùn)行完成。 2、所用策略：貪心策略 3、算法分析： （1）由于是非搶占式調(diào)度，所以應(yīng)該盡量讓時(shí)間短的工作先做，然后再讓時(shí)間長(zhǎng)的工作做。這里我們使用堆進(jìn)行排序，建立一個(gè)小頂堆，然后每次拿出小頂堆上的最小元素，并使用sum中的公式就可以算出平均完成時(shí)間。堆排序的時(shí)間復(fù)雜度是O(nlgn)，其中BuildMinHeap的時(shí)間復(fù)雜

33、度是O(n)，而BuildMinHeap()的時(shí)間復(fù)雜度是O(lgn)。其中HeapExtractMin(N)的時(shí)間復(fù)雜度是O(lgn)。 4、結(jié)果截圖： 5、總結(jié)： 由于前面對(duì)于堆排序和優(yōu)先隊(duì)列的MIN-EXTRACT函數(shù)的錯(cuò)誤沒有解決，導(dǎo)致在調(diào)度中，需要每次去運(yùn)行時(shí)間最短的工作時(shí)發(fā)生了錯(cuò)誤。題目三： 1、題目描述:以A為源點(diǎn)，求出下圖的單源點(diǎn)最短路徑。 2、所用算法：由于圖中存在負(fù)權(quán)值，所以Dijkstra算法無法使用，因此采用Bellman-Ford算法求取圖的單源點(diǎn)最短路徑。 3、算法分析： （1）Bellman-Ford算法通過對(duì)邊進(jìn)行松弛操作來漸近地降低從源點(diǎn)A到每個(gè)結(jié)點(diǎn)的最短路徑

34、的估計(jì)值，直到該估計(jì)值與實(shí)際的最短路徑權(quán)重(A,v)相同為止。該算法返回TRUE值當(dāng)且僅當(dāng)輸入圖中不包含可以從源結(jié)點(diǎn)到達(dá)的權(quán)重為負(fù)值的環(huán)路。 （2）Bellman-Ford算法的執(zhí)行步驟：1、初始化：將除源點(diǎn)外的所有頂點(diǎn)的最短距離估計(jì)值dv+, ds0；2、迭代求解：反復(fù)對(duì)邊集E中的每條邊進(jìn)行松弛操作，使得頂點(diǎn)集V中的每個(gè)頂點(diǎn)v的最短距離估計(jì)值逐步逼近其最短距離；（運(yùn)行|v|-1次）3、檢驗(yàn)負(fù)權(quán)回路：判斷邊集E中的每一條邊的兩個(gè)端點(diǎn)是否收斂。如果存在未收斂的頂點(diǎn)，則算法返回false表明問題無解；否則算法返回true，并且從源點(diǎn)可達(dá)的頂點(diǎn)v的最短距離保存在dv中。 （3）算法適用范圍和條件： 1.單源最短路徑(從源點(diǎn)A到其它所有頂點(diǎn)v)； 2.有向圖&無向圖(無向圖可以看作(u,v),(v,u)同屬于邊