西電算法導(dǎo)論上機實驗報告(共25頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 算法導(dǎo)論上機實驗報告冊 班級： xxxxxx 學(xué)號： xxxxxxx 姓名： xxxx 教師： xxxxxx 專心-專注-專業(yè)目 錄實驗一 排序算法1題目一：11、題目描述：12、所用算法：13、算法分析：14、結(jié)果截圖：15、總結(jié)：2題目二：31、題目描述：32、所用算法：33、算法分析：34、結(jié)果截圖：35、總結(jié)：4題目三：41、題目描述：42、所用算法：43、算法分析：54、結(jié)果截圖：55、總結(jié)：5題目四：61、題目描述：62、所用策略：63、算法分析：64、 結(jié)果截圖：65、 總結(jié)：7實驗二 動態(tài)規(guī)劃7題目一：71、題目描述：72、所用策略：73、算法分析：

2、74、結(jié)果截圖：85、總結(jié)：8題目二：91、題目描述：92、所用策略：93、算法分析：94、結(jié)果截圖：95、總結(jié)：10題目三：101、題目描述：102、所用策略：103、算法分析：104、結(jié)果截圖：115、總結(jié)：11題目四：111、題目描述：122、所用策略：123、算法分析:124、結(jié)果截圖：125、總結(jié)：13題目五：131、題目描述：132、所用策略：133、算法分析：134、結(jié)果截圖：145、總結(jié)：14實驗三 貪心算法14題目一：141、題目描述：142、所用策略：143、算法分析：144、結(jié)果截圖：155、總結(jié)：16題目二：161、題目描述：162、所用策略：163、算法分析：164、

3、結(jié)果截圖：175、總結(jié)：17題目三：171、題目描述:172、所用算法：173、算法分析：174、結(jié)果截圖：185、總結(jié)：18題目四：181、題目描述：192、所用算法：193、算法分析：19實驗四 回溯法19題目一：191、題目描述：192、所用策略：193、算法分析：19題目二：201、題目描述：212、所用策略：213、算法分析：21實驗一 排序算法題目一： 1、題目描述：描述一個運行時間為(nlgn)的算法，給定n個整數(shù)的集合S和另一個整數(shù)x，該算法能確定S中是否存在兩個其和剛好為x的元素。 2、所用算法：1、運用歸并排序算法 2、在已經(jīng)排好序的基礎(chǔ)上，對其運用二分查找。 3、算法分析

4、：（1）歸并排序運用的是分治思想，時間復(fù)雜度為 (nlgn)，能夠滿足題目要求的運行時間。歸并排序的分解部分是每次將數(shù)組劃分兩個部分，時間復(fù)雜度為（1）；再對已經(jīng)分解的兩個部分再進(jìn)行分解直到將數(shù)組分解成單個元素為止；解決部分是遞歸求解排序子序列；合并部分是將已經(jīng)排序的子序列進(jìn)行合并得到所要的答案，時間復(fù)雜度為(lgn)。（2）二分查找算法的時間復(fù)雜度為(lgn)在題目要求的范圍內(nèi)，二分查找的條件為待查的數(shù)組為有序序列。算法的主要思想為設(shè)定兩個數(shù)，low指向最低元素，high指向最高元素，然后比較數(shù)組中間的元素與待查元素進(jìn)行比較。如果待查元素小于中間元素，那么表明查找元素在數(shù)組的前半段；反之，如

5、果待查元素大于中間元素，那么表明查找元素在數(shù)組的后半段。 4、結(jié)果截圖： 5、總結(jié)：（1）在主函數(shù)中調(diào)用二分查找的時候，參數(shù)應(yīng)該為BinSearch(a,j+1,n,x-aj），從j+1開始遍歷而不是都是從第一個開始。（2）遇到的困難為：由于程序語言規(guī)定數(shù)組的下標(biāo)從0開始，而算法偽代碼要求從1開始，因此在定義數(shù)組大小的時候?qū)?shù)字加1，但是在編譯運行的時候會得不到想要的結(jié)果，出現(xiàn)數(shù)組下標(biāo)訪問錯誤。 采取的解決方案為：在開始定義數(shù)組的時候，將數(shù)組的大小定義為一個較大的數(shù)字，如1000。避免在運行時出現(xiàn)錯誤，但是造成了空間的浪費。較好的方案為使用動態(tài)數(shù)組，如malloc函數(shù)。題目二： 1、題目描述：

6、實現(xiàn)優(yōu)先級隊列，即需要支持以下操作：INSERT(S,x):把元素x插入到集合S中；MAXMUM(S):返回S中具有最大key的元素；EXTRACT-MAX(S):去掉并返回S中的具有最大key的元素；INCREASE-KEY(S,x,k)：將元素x的關(guān)鍵字值增到k。 2、所用算法：堆排序，運用堆來實現(xiàn)優(yōu)先隊列。 3、算法分析： （1）堆排序算法是引用堆這個數(shù)據(jù)結(jié)構(gòu)進(jìn)行信息管理。堆排序的時間復(fù)雜度是(nlgn),但是與歸并排序不同的是堆排序具有空間的原址性，任何時候都只需要常數(shù)個額外的元素空間存儲臨時數(shù)據(jù)。堆排序算法分為3個過程，MAX-HEAPIEY:調(diào)整堆以滿足小頂堆性質(zhì)，其時間復(fù)雜度為(

7、lgn)；BUILD-MAXHEAP:從無序的輸入數(shù)據(jù)數(shù)組中構(gòu)造小頂堆，其時間復(fù)雜度為線性時間;HEAP-SORT:對數(shù)組進(jìn)行原址排序，其時間復(fù)雜度為(nlgn)。 （2）在堆的基礎(chǔ)上實現(xiàn)優(yōu)先隊列INSERT、MAXMUM、EXTRACT-MAX、INCREASE-KEY，時間復(fù)雜度為(lgn)。 4、結(jié)果截圖： 5、總結(jié)： 遇到的困難：沒有理解將一個序列轉(zhuǎn)換成小頂堆的過程，因此剛開始很難將偽代碼用c語言進(jìn)行實現(xiàn)。從結(jié)果可以看出，在編寫MAX-EXSTRACT函數(shù)的時候，當(dāng)去掉第一個元素后，程序沒有調(diào)用MAX-HEAP進(jìn)行調(diào)整堆，因此最后序列是無序狀態(tài)。題目三： 1、題目描述：實現(xiàn)quick_

8、sort算法，并且回答以下兩個問題：（1）待排數(shù)組中的元素值都相同的情況下，運用quick_sort需要進(jìn)行多少次比較？（2）對于n個元素的數(shù)組，運用quick_sort舉出需要進(jìn)行比較次數(shù)的上限和下限是多少？ 2、所用算法：快速排序算法 3、算法分析：快速排序采用分治策略，時間復(fù)雜度為(nlgn),但是最壞情況下為(n2),并且快速排序算法屬于原地排序，并不需要開辟空間?？焖倥判驈?fù)雜的步驟為其分解的步驟，分解的過程：數(shù)組Ap.r被劃分為兩個子數(shù)組Ap.q-1和Aq+1.r,使得Ap.q-1中的每個元素都小于Aq,而Aq也小于等于Aq+1.r中的每個元素。而在實現(xiàn)的過程總是選擇將Ar作為基準(zhǔn)點

9、進(jìn)行劃分Ap.r數(shù)組。 4、結(jié)果截圖： 5、總結(jié)： 問題答案：（1）當(dāng)選取第一個或者最后一個為基準(zhǔn)點時，當(dāng)n個元素相同的時候為最壞情況，比較次數(shù)為n*(n-1)/2;(2)快速排序比較次數(shù)最少為(nlgn),最大的比較次數(shù)為(n2)。題目四： 1、題目描述：運用分治的策略將兩個已經(jīng)排好序的序列中，找出第k大的元素，且要求時間復(fù)雜度為(lgm+lgn),其中m和n分別為兩個序列的長度。 2、所用策略：分治策略 3、算法分析： （1）分解：因為已經(jīng)是兩個獨立的的序列，所以不用進(jìn)行分解。 （2）解決：因為兩個序列為已經(jīng)排好的序列，因此不用分開進(jìn)行排序。 （3）利用歸并排序中的merge函數(shù)，將這兩個

10、序列分別看成是L和R兩個數(shù)組，通過開辟一個新的數(shù)組，將兩個數(shù)組合并成一個新的排好序的序列，在根據(jù)要求的k值，對新的數(shù)組進(jìn)行取值。4、 結(jié)果截圖：5、 總結(jié)： （1）理解分治策略的三個步驟：分解、解決和合并對于具體問題的具體表現(xiàn)，要善于根據(jù)時間復(fù)雜度與所學(xué)的算法進(jìn)行結(jié)合，找出可以利用的地方。 實驗二 動態(tài)規(guī)劃題目一： 1、題目描述：用動態(tài)規(guī)劃實現(xiàn)矩陣鏈乘，保證相乘的次數(shù)最少。 2、所用策略：動態(tài)規(guī)劃 3、算法分析： （1）最優(yōu)子結(jié)構(gòu)為：如果最優(yōu)的加括號的方式將其分解為Ai.k與Ak+1.j的乘積，則分別對Ai.k與Ak+1.j加括號的方式也一定是最優(yōu)的。 （2）定義mi,j為計算矩陣Ai.j所需

11、標(biāo)量乘法次數(shù)的最小值，對于i=j時,矩陣鏈乘只包含唯一的矩陣Ai,因此不需要做任何標(biāo)量乘法運算，所以mi,i=0;當(dāng)i<j時利用最優(yōu)子結(jié)構(gòu)來計算mi,j。 （3）矩陣鏈乘的遞歸式： （4）在算法設(shè)計的時候，需要m數(shù)組記錄Ai.j最小相乘次數(shù)，s數(shù)組記錄構(gòu)造最優(yōu)解所需要的信息，其記錄的k值指出了AiAi+1Aj的最優(yōu)括號化方案的分割點應(yīng)在AkAk+1之間。 （5）矩陣鏈乘的時間復(fù)雜度為(n3) 4、結(jié)果截圖： 5、總結(jié)： 遇到的問題：在構(gòu)建m數(shù)組和s數(shù)組的時候需要構(gòu)建二維數(shù)組，而c語言中函數(shù)的參數(shù)列表中二維數(shù)組要指明數(shù)組大小，但是還沒有輸入信息的時候并沒有方法確定數(shù)組大小。 采取的方案：由

12、于此次的例子只有兩種情況，因此對于 MATRIX_CHAIN_ORDER函數(shù)和PRINT_OPTIMAL_PARENS函數(shù)寫兩遍，大體的實現(xiàn)過程相同，只是數(shù)組的大小有所改變。并沒有解決這個情況，造成代碼的冗余。題目二： 1、題目描述：用動態(tài)規(guī)劃求下列字符串的最長公共子序列（LCS） 2、所用策略：動態(tài)規(guī)劃 3、算法分析：（1） 最優(yōu)子結(jié)構(gòu)：令X=<x1,x2,.xm>和Y=<y1,y2,.,yn>為兩個序列，Z=<z1,z2,.,zk>為X和Y的任意LCS。1、如果xm=yn,則zk=xm=yn且Zk-1是Xm-1和Yn-1的一個LCS.2、如果xmyn,則

13、zkxm意味著Z是Xm-1和Y的一個LCS；3、如果xmyn,則zkyn意味著Z是X和Yn-1的一個LCS。（2） 定義一個bi,j指向表項對應(yīng)計算ci,j時所選擇的子問題最優(yōu)解，過程返回表b和表c，cm,n保持X和Y的LCS長度。（3） LCS的遞歸式為： （4） LCS的時間復(fù)雜度為(m+n),b表的空間復(fù)雜度為(mn)。 4、結(jié)果截圖： 5、總結(jié)： 用動態(tài)規(guī)劃求取最長公共子序列的時候，要理解b數(shù)組的用途和使用。 遇到的困難：編寫的代碼無法針對字符串大小未定情況下，進(jìn)行求解LCS這導(dǎo)致了代碼的冗余。題目三： 1、題目描述：用動態(tài)規(guī)劃求取以下字符串的最長公共子串。 2、所用策略：動態(tài)規(guī)劃 3

14、、算法分析： （1）最優(yōu)子結(jié)構(gòu)：令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為結(jié)尾的相同子串的最大長度。記錄著X和Y的最長公共子串的最大長度。 （3）最長公共子串的遞歸式： （4）最長公共子串的時間復(fù)雜度為(mn)，空間

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

16、(3)最大子段和的遞歸式： (4)最大子段和使用動態(tài)規(guī)劃進(jìn)行計算的時間復(fù)雜度為(n)。 4、結(jié)果截圖： 5、總結(jié)： 在求解集合的最大子段和的時候，要對比不同解決方法的不同之處，感受用動態(tài)規(guī)劃解決的便捷。題目五： 1、題目描述：利用動態(tài)規(guī)劃求出多段圖中的最短路徑 2、所用策略：動態(tài)規(guī)劃 3、算法分析： （1）可以由圖可知，圖中的頂點講圖劃分7個階段，分別了解每個階段可以有幾種可供選擇的店，引入fk表示狀態(tài)k到終點狀態(tài)的最短距離。最優(yōu)子結(jié)構(gòu)為：當(dāng)前狀態(tài)的fk由上個狀態(tài)的fk-1和狀態(tài)k-1到狀態(tài)k的距離決定決策：當(dāng)前狀態(tài)應(yīng)在前一個狀態(tài)的基礎(chǔ)上獲得。決策需要滿足規(guī)劃方程,規(guī)劃方程：f(k)表示狀態(tài)k

17、到終點狀態(tài)的最短距離。 （2）多段圖最短路徑的遞歸式： 4、結(jié)果截圖： 無。 5、總結(jié)： （1）遇到的問題：無法將多段圖的每個階段點的狀態(tài)表示并記錄下來。并不了解如何將動態(tài)規(guī)劃與貪心算法的如迪杰斯特拉算法進(jìn)行對比，真正從最優(yōu)子結(jié)構(gòu)將最短路徑表示出來。實驗三 貪心算法題目一： 1、題目描述：背包問題，即分別計算出在0-1背包和分?jǐn)?shù)背包情況下的計算結(jié)果。 2、所用策略：動態(tài)規(guī)劃和貪心策略 3、算法分析： （1）0-1背包問題：所選擇的的貪心策略為按照選擇單位重量價值最大的物品順序進(jìn)行挑選。算法的步驟：設(shè)背包容量為C，共有n個物品，物品重量存放在數(shù)組Wn中，價值存放在數(shù)組Vn中，問題的解存放在數(shù)組X

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

19、止條件為（Wi>C），循環(huán)體為將第i個物品放入背包：Xi=1;C=C-Wi;i+；最后一步：將結(jié)果存入到X數(shù)組中Xi=C/Wi。 （3）分?jǐn)?shù)背包問題所采用的貪心策略之不能得到最優(yōu)解，是由于物品不允許分割，因此，無法保證最終能將背包裝滿，部分閑置的背包容量使背包的單位重量價值降低了。 （4）分?jǐn)?shù)背包問題采用選擇單位重量價值最大的物品順序進(jìn)行挑選，其算法的時間復(fù)雜度為(nlgn)。 4、結(jié)果截圖： 5、總結(jié)： 使用貪心策略解決0-1背包問題得出的結(jié)果并不是最優(yōu)解，這是由于所用的選擇策略不同。題目二： 1、題目描述：一個簡單的調(diào)度問題，給予工作編號為J1，J2.Jn，已知所以工作的運行時間分別

20、為T1，T2.TN。有一個單獨的處理器，為了安排這些工作以到達(dá)減少平均完成時間的最好方法是什么。假定它是一個非搶占式調(diào)度：一旦工作開始，它必須運行完成。 2、所用策略：貪心策略 3、算法分析： （1）由于是非搶占式調(diào)度，所以應(yīng)該盡量讓時間短的工作先做，然后再讓時間長的工作做。這里我們使用堆進(jìn)行排序，建立一個小頂堆，然后每次拿出小頂堆上的最小元素，并使用sum中的公式就可以算出平均完成時間。堆排序的時間復(fù)雜度是O(nlgn)，其中BuildMinHeap的時間復(fù)雜度是O(n)，而BuildMinHeap()的時間復(fù)雜度是O(lgn)。其中HeapExtractMin(N)的時間復(fù)雜度是O(lgn

21、)。 4、結(jié)果截圖： 5、總結(jié)： 由于前面對于堆排序和優(yōu)先隊列的MIN-EXTRACT函數(shù)的錯誤沒有解決，導(dǎo)致在調(diào)度中，需要每次去運行時間最短的工作時發(fā)生了錯誤。題目三： 1、題目描述:以A為源點，求出下圖的單源點最短路徑。 2、所用算法：由于圖中存在負(fù)權(quán)值，所以Dijkstra算法無法使用，因此采用Bellman-Ford算法求取圖的單源點最短路徑。 3、算法分析： （1）Bellman-Ford算法通過對邊進(jìn)行松弛操作來漸近地降低從源點A到每個結(jié)點的最短路徑的估計值，直到該估計值與實際的最短路徑權(quán)重(A,v)相同為止。該算法返回TRUE值當(dāng)且僅當(dāng)輸入圖中不包含可以從源結(jié)點到達(dá)的權(quán)重為負(fù)值的

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

23、； 3.邊權(quán)可正可負(fù)(如有負(fù)權(quán)回路輸出錯誤提示)。 （4）Bellman-Ford算法的時間復(fù)雜度為(VE)。 4、結(jié)果截圖： 無 5、總結(jié)： 這次的實驗并沒有成功，按照偽代碼進(jìn)行編寫代碼，編譯通過的時候卻沒有辦法輸出結(jié)果，或者結(jié)果是錯誤的。題目四： 1、題目描述：求題3圖中每對結(jié)點的最短路徑問題 2、所用算法：Floyd-Warshall算法。 3、算法分析： （1）設(shè)G的頂點為V=1,2,3.n，對于任意一對頂點i,j屬于V，假設(shè)i到j(luò)有路徑且中間節(jié)點皆屬于集合1,2,3.k，P是其中的一條最小權(quán)值路徑。就是i到j(luò)的最短路徑P所通過的中間頂點最大不超過k。 （2）設(shè)d(k)ij為從結(jié)點i到結(jié)點j的所有中間結(jié)點全部取自結(jié)合1,2,.,k的一條最短路徑的權(quán)重。d(k)ij的遞歸定義為 （3）F