1、精選優質文檔-傾情為你奉上第二次試驗一、問題：Matrix-chain product分析：本題是矩陣鏈乘問題，需要求出最優括號化方案。即在矩陣的乘法鏈上添加括號來改變運算順序以使矩陣鏈乘法的代價降低。可以分析該鏈乘的一個子段總結一些結論。假設mi,j表示Ai*Aj的鏈成需要進行的乘法次數（假設j-i足夠大），我們可以將Ai*Aj分為兩段進行計算：（Ai*Ak）*（Ak+1*Aj）可以得出mi,j的遞推公式可以得出，當i=j的時候，mi,j=0。當i<j的時候。k的取值范圍是i到j-1，對于k的每一個取值都可以得到一個mi,j的值，取出最小值即時mi,j的最優化方案。遞推公式如下：可以根

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

3、,j，都對應著一個公共子序列的長度。假設長度為c，就可以得到一個二維數組cm,n。對于ci,j，當Ai=Bj的時候，問題就轉變為求A1.i-1和B1.j-1的公共子序列長度的問題，所以ci，j的長度就是ci-1，j-1 + 1;同理，當Ai != Bj的時候，ci,j應該在ci-1,j與ci,j-1中取最大值。另外，當i或者j等于0的時候，顯然c的值為0。由上面所述，可以得到遞推公式如下：為了解決這個問題，還如要定義另一個數組用于存放c數組中每一個元素的來源。這個來源其實就反映了公共子串。可以通過箭頭表示來源，相連的箭頭序列中指向左上方的箭頭最多的一串對應的就是最長公共子序列。比如對于題目中給

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

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

6、數時出現問題，后來講max的初始值設置為第一個元素的值后就能正常了。總結：動態規劃能解決很多問題，找到遞推公式非常重要。五、問題：Shortest path in multistage graphs. Find the shortest path from 0 to 15 for the following graph.分析：觀察本題圖的特點，發現可以將圖分解為7個部分，以此可以計算到每一個節點的最短的路徑。即可求出最終的最短路徑。 總結：結合本題中的特殊情況，可以采用適當的方法來處理。第三次實驗一、問題：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.分析：本題是背包問題的兩個解法。對于部分背包來說比較簡單，就是將單位價值大的物品優先放置到背包中，這樣就能在背包中獲取最大的價值。但是對于0/1背包問題來說，就相對復雜了。可以通過貪心算法解決。經過分析，我們轉化這個問題為將n件物品放置到容量為w的容器中。這里，每件物品只可能有一個狀態：放入/不放入，我們用0/1來對應。用

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

9、件物品是否應該放在容量的w的背包中進行分析，最終得到了一個遞推式。二、問題：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。分析：這是一個線程調度問題，通過操作系統課程的學習，我們了解到應當采用短作業優先的調度方式。可以采用快速排序對進程順序進行排序即可得到調度時間。總結：在進程調度問題中，如果想獲取最短的平均周轉時間（單線程）應當使用短作業優先的算法。三、問題：單源點最短路徑分析：本題中，因為路徑中存在負邊，所以應當使用bellman-ford算法。為了方便的使用該算法，需要首先創建合適的邊的數據結構。這樣，在遍歷邊的時候

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

12、最短路徑問題，應當使用Johnson算法。Johnson算法需要用dijkstra和bellman-ford算法作為子程序。如果圖G=（V,E）中所有的邊權重都為非負值，可以通過在每一個節點使用dijkstra算法求出所有節點虹之間的最短路徑；如果該圖包含權值為負的邊，但是沒有權重為負的環路，那么只要計算一組新的非負權重值，然后使用同樣的方法即可。總結：Johnson算法相當于是對dijkstra算法和bellman-ford算法的應用，結合這兩個算法，通過使用重新賦值權重來生成非負權重，最終得到所有節點對之間的最短路徑。第四次實驗一、題目：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背包問題。可以用一個數組來記錄“選中”物品的情況。首先，選擇第一件物品，如果超重的話不選擇該物品；如果沒有超重，繼續添加下一個物品，這樣選擇下去，最終一定可以選擇完全部的物品。計算目前選擇物品的totalValue

14、值。繼續回溯，如果的到新的totalValue值，如果大于前一個值，那么更新該值，并且更新保存選擇的數組中。總結：從8皇后問題可以發現回溯法的一般方法。經過代入到這個問題中，發現確實可行。回溯法需要一個合理的遞歸函數，這個函數的終止條件也需要認真的分析。比如這一題和8皇后問題都可以使用元素的個數作為一個結束條件，另外還需要注意導致“回溯”的位置。二、題目：Solve the 8-Queen problem using back-tracking algorithm.分析：8皇后問題是回溯法的一個典型的例題。假設目前已經在奇葩的前i（i<8）行放置了i和皇后并且位置合法。然后我們放置第j（

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

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

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

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

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

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

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

22、，所以不用進行分解。 （2）解決：因為兩個序列為已經排好的序列，因此不用分開進行排序。 （3）利用歸并排序中的merge函數，將這兩個序列分別看成是L和R兩個數組，通過開辟一個新的數組，將兩個數組合并成一個新的排好序的序列，在根據要求的k值，對新的數組進行取值。4、 結果截圖：5、 總結： （1）理解分治策略的三個步驟：分解、解決和合并對于具體問題的具體表現，要善于根據時間復雜度與所學的算法進行結合，找出可以利用的地方。 實驗二 動態規劃題目一： 1、題目描述：用動態規劃實現矩陣鏈乘，保證相乘的次數最少。 2、所用策略：動態規劃 3、算法分析： （1）最優子結構為：如果最優的加括號的方式將其分

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

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

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

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

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

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

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

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

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

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

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

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