算法分析與設(shè)計(jì)復(fù)習(xí)題及參考答案

1、網(wǎng)絡(luò)教育課程考試復(fù)習(xí)題及參考答案算法分析與設(shè)計(jì)程序子問(wèn)題的重疊性質(zhì) 多機(jī)調(diào)度問(wèn)題、名詞解釋：1. 算法2.3. 遞歸函數(shù)4.5. 隊(duì)列式分支限界法6.7.最小生成樹二、簡(jiǎn)答題：1. 備忘錄方法和動(dòng)態(tài)規(guī)劃算法相比有何異同？簡(jiǎn)述之。2. 簡(jiǎn)述回溯法解題的主要步驟。3. 簡(jiǎn)述動(dòng)態(tài)規(guī)劃算法求解的基本要素。4. 簡(jiǎn)述回溯法的基本思想。5. 簡(jiǎn)要分析在遞歸算法中消除遞歸調(diào)用，將遞歸算法轉(zhuǎn)化為非遞歸算法的方法。6. 簡(jiǎn)要分析分支限界法與回溯法的異同。7. 簡(jiǎn)述算法復(fù)雜性的概念，算法復(fù)雜性度量主要指哪兩個(gè)方面？8. 貪心算法求解的問(wèn)題主要具有哪些性質(zhì)？簡(jiǎn)述之。9. 分治法的基本思想是什么？合并排序的基本思想是

2、什么？請(qǐng)分別簡(jiǎn)述之。10. 簡(jiǎn)述分析貪心算法與動(dòng)態(tài)規(guī)劃算法的異同。三、算法編寫及算法應(yīng)用分析題：1. 已知有 3 個(gè)物品：(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容積 M=2Q 根據(jù) 0-1 背包動(dòng)態(tài)規(guī)劃的遞推式求出最優(yōu)解。2. 按要求完成以下關(guān)于排序和查找的問(wèn)題。 對(duì)數(shù)組A=15，29，135，18，32，1，27，25，5，用快速排序方法將其排成遞減序。 請(qǐng)描述遞減數(shù)組進(jìn)行二分搜索的基本思想，并給出非遞歸算法。 給出上述算法的遞歸算法。 使用上述算法對(duì)所得到的結(jié)果搜索如下元素，并給出搜索過(guò)程：18, 31，135。3.已知Akr 6=50

3、， 7=6,(a (k)(aij)ri*ri d，k=1，2，3，4，5，6，n=5，r2=10，r3=3，r4=12，r5=5,求矩陣鏈積 AX A2X AsX A4X A5X A的最佳求積順序(要求給出計(jì)算步驟) 。4. 根據(jù)分枝限界算法基本過(guò)程，求解0-1背包問(wèn)題。已知 n=3,M=20，(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。5. 試用貪心算法求解汽車加油問(wèn)題：已知一輛汽車加滿油后可行駛n公里，而旅途中有若干個(gè)加油站。試設(shè)計(jì)一個(gè)有效算法，指出應(yīng)在哪些加油站停靠加油，使加油次數(shù)最少，請(qǐng)寫出該算法。6. 試用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)下列問(wèn)題：設(shè)A和B是

4、兩個(gè)字符串。我們要用最少的字符操作，將字符串A轉(zhuǎn)換為字符串B，這里所說(shuō)的字符操作包括： 刪除一個(gè)字符。 插入一個(gè)字符。 將一個(gè)字符改為另一個(gè)字符。請(qǐng)寫出該算法。7. 對(duì)于下圖使用 Dijkstra 算法求由頂點(diǎn)a到頂點(diǎn)h的最短路徑。8. 試寫出用分治法對(duì)數(shù)組 An實(shí)現(xiàn)快速排序的算法。9. 有n個(gè)活動(dòng)爭(zhēng)用一個(gè)活動(dòng)室。已知活動(dòng) i占用的時(shí)間區(qū)域?yàn)镾i, f i，活動(dòng)i,j相容的條件是：sj > f i ,問(wèn)題的解表示為（xi|x i=1，2，n,） , Xi表示順序?yàn)閕的活動(dòng)編號(hào)活動(dòng)，求一個(gè)相容的活動(dòng)子集， 且安排的活動(dòng)數(shù)目最多。10. 設(shè)XI、X2、X3是一個(gè)三角形的三條邊，而且X計(jì)X2+

5、X3=14。請(qǐng)問(wèn)有多少種不同的三角形？給出解答過(guò)程。11. 設(shè)數(shù)組A有n個(gè)元素，需要找出其中的最大最小值。 請(qǐng)給出一個(gè)解決方法，并分析其復(fù)雜性。 把n個(gè)元素等分為兩組 A1和A2,分別求這兩組的最大值和最小值， 然后分別將這兩組的最大值和最小值相比較，求出全部元素的最大值和最小值。如果A1和A2中的元素多于兩個(gè)，則再用上述方法各分為兩個(gè)子集。直至子集中元素至多兩個(gè)元素為止。這是什么方法的思想？請(qǐng)給出該方法的算法描述，并分析其復(fù)雜性。n12. 有n個(gè)程序和長(zhǎng)度為L(zhǎng)的磁帶，程序i的長(zhǎng)度為a，已知送q a L，求最優(yōu)解（Xi, X2 , . , Xi，i 4nXn）, Xi =0,1, x i =1

6、，表示程序i存入磁帶，Xi =0 ,表示程序i不存入磁帶，滿足 v xia： L，且存放的程序數(shù)目最多。13. 試用分治法實(shí)現(xiàn)有重復(fù)元素的排列問(wèn)題：設(shè)R =12,.片）是要進(jìn)行排列的n個(gè)元素，其中元素r1,r2,.,rn可能相同，試設(shè)計(jì)計(jì)算 R的所有不同排列的算法。14. 試用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn) 0-1閉包問(wèn)題，請(qǐng)寫出該算法。15. 試用貪心算法求解下列問(wèn)題：將正整數(shù)n分解為若干個(gè)互不相同的自然數(shù)之和，使這些自然數(shù)的乘積最大，請(qǐng)寫出該算法。16. 試寫出用分治法對(duì)一個(gè)有序表實(shí)現(xiàn)二分搜索的算法。17. 試用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)最長(zhǎng)公共子序列問(wèn)題，請(qǐng)寫出該算法。18. 假設(shè)有7個(gè)物品，它們的重量和價(jià)值如

7、下表所示。若這些物品均不能被分割，且背包容量M= 150,使用回溯方法求解此背包問(wèn)題，請(qǐng)寫出狀態(tài)空間搜索樹。物品ABCDEFG重量35306050401025價(jià)值1040305035403019. 求解子集和問(wèn)題：對(duì)于集合S=1 , 2 , 6, 8，求子集，要求該子集的元素之和d=9。 畫出子集和問(wèn)題的解空間樹； 該樹運(yùn)用回溯算法，寫出依回溯算法遍歷節(jié)點(diǎn)的順序； 如果S中有n個(gè)元素，指定d,用偽代碼描述求解子集和問(wèn)題的回溯算法。20. 求解填字游戲問(wèn)題：在 3X 3個(gè)方格的方陣中要填入數(shù)字1到N （ N10）內(nèi)的某9個(gè)數(shù)字，每個(gè)方格填一個(gè)整數(shù)，似的所有相鄰兩個(gè)方格內(nèi)的兩個(gè)整數(shù)之和為質(zhì)數(shù)。試采

8、用回溯法寫出滿足這個(gè)要求的一種數(shù)字填法的算法和滿足這個(gè)要求的全部數(shù)字填法的算法。21. 試用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)最大子矩陣和問(wèn)題：求m n矩陣A的一個(gè)子矩陣，使其各元素之和為最大。22. 試用回溯法解決下列整數(shù)變換問(wèn)題：關(guān)于整數(shù)i的變換f和g定義如下：f （i）二3i; g（i） - lli /2。對(duì)于給定的兩個(gè)整數(shù) n和m，要求用最少的變換 f和g變換次數(shù)將n變?yōu)閙。23. 關(guān)于15謎問(wèn)題。在一個(gè)4X 4的方格的棋盤上，將數(shù)字 1到15代表的15個(gè)棋子以任意的順序置入各 方格中，空出一格。要求通過(guò)有限次的移動(dòng)，把一個(gè)給定的初始狀態(tài)變成目標(biāo)狀態(tài)。移動(dòng)的規(guī)則是：每次只能把空格周圍的四格數(shù)字（棋子）中

9、的任意一個(gè)移入空格，從而形成一個(gè)新的狀態(tài)。為了有效的移動(dòng)，設(shè)計(jì)了估值函數(shù)Ci(x)，表示在結(jié)點(diǎn)x的狀態(tài)下，沒(méi)有到達(dá)目標(biāo)狀態(tài)下的正確位置的棋子的個(gè)數(shù)。請(qǐng)使用該估計(jì)函數(shù)，對(duì)圖示的初始狀態(tài)，給出使用分支限界方法轉(zhuǎn)換到目標(biāo)狀態(tài)的搜索樹。124563791012813141115123456789101112131415初始狀態(tài)目標(biāo)狀態(tài)參考答案、名詞解釋：1. 算法： 算法是指解決問(wèn)題的一種方法或一個(gè)過(guò)程。算法是若干指令的有窮序列，滿足性質(zhì)：（1）輸入有零個(gè)或多個(gè)外部量作為算法的輸入； （ 2）輸出：算法產(chǎn)生至少一個(gè)量作為輸出； （ 3）確定性：組成 算法的每條指令清晰、無(wú)歧義； （ 4）有限性：算法中

10、每條指令的執(zhí)行次數(shù)有限，執(zhí)行每條指令的時(shí)間 也有限。2. 程序： 程序是算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。3. 遞歸函數(shù)： 用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。4. 子問(wèn)題的重疊性質(zhì)： 遞歸算法求解問(wèn)題時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì) 算多次，這種性質(zhì)稱為子問(wèn)題的重疊性質(zhì)。5. 隊(duì)列式分支限界法： 隊(duì)列式 （FIFO） 分支限界法是將活結(jié)點(diǎn)表組織成一個(gè)隊(duì)列，并按照隊(duì)列的先進(jìn)先出 （FIFO）原則選取下一個(gè)結(jié)點(diǎn)為擴(kuò)展結(jié)點(diǎn)。6. 多機(jī)調(diào)度問(wèn)題： 多機(jī)調(diào)度問(wèn)題要求給出一種作業(yè)調(diào)度方案， 使所給的 n 個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由 臺(tái)機(jī)器加工處理完成。同時(shí)約定每個(gè)作業(yè)均可在任何一

11、臺(tái)機(jī)器上加工處理，但未完工前不允許中斷處 理。作業(yè)不能拆分成更小的子作業(yè)。7. 最小生成樹：G=（V,E）是無(wú)向連通帶權(quán)圖， G的子圖稱為 G的生成樹，生成樹上各邊權(quán)的總和稱為該生成樹的耗費(fèi)，在 G的所有生成樹中，耗費(fèi)最小的生成樹稱為G的最小生成樹。、簡(jiǎn)答題：1. 備忘錄方法和動(dòng)態(tài)規(guī)劃算法相比有何異同？簡(jiǎn)述之。 備忘錄方法是動(dòng)態(tài)規(guī)劃算法的變形。與動(dòng)態(tài)規(guī)劃算法一樣，備忘錄方法用表格保存已解決的子問(wèn)題的 答案，在下次需要解此問(wèn)題時(shí)，只要簡(jiǎn)單地查看該子問(wèn)題的解答，而不必重新計(jì)算。 備忘錄方法與動(dòng)態(tài)規(guī)劃算法不同的是，備忘錄方法的遞歸方式是自頂向下的，而動(dòng)態(tài)規(guī)劃算法則是自 底向上遞歸的。因此，備忘錄方法

12、的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法 為每個(gè)解過(guò)的子問(wèn)題建立了備忘錄以備需要時(shí)查看，避免了相同的子問(wèn)題的重復(fù)求解，而直接遞歸方 法沒(méi)有此功能。2. 簡(jiǎn)述回溯法解題的主要步驟。 回溯法解題的主要步驟包括：1）針對(duì)所給問(wèn)題，定義問(wèn)題的解空間；2）確定易于搜索的解空間結(jié)構(gòu)；3）以深度優(yōu)先方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索。3. 簡(jiǎn)述動(dòng)態(tài)規(guī)劃算法求解的基本要素。 動(dòng)態(tài)規(guī)劃算法求解的基本要素包括：1）最優(yōu)子結(jié)構(gòu)是問(wèn)題能用動(dòng)態(tài)規(guī)劃算法求解的前提；2）動(dòng)態(tài)規(guī)劃算法，對(duì)每一個(gè)子問(wèn)題只解一次，而后將其解保存在一個(gè)表格中，當(dāng)再次需要解此子問(wèn)題 時(shí)，只是簡(jiǎn)單地用常數(shù)時(shí)間查看一

13、下結(jié)果，即重疊子問(wèn)題。4. 簡(jiǎn)述回溯法的基本思想。 回溯法的基本做法是搜索，在問(wèn)題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算 法搜索至解空間樹的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問(wèn)題的解。如果肯定不包含，則跳過(guò)對(duì)該結(jié) 點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。5. 簡(jiǎn)要分析在遞歸算法中消除遞歸調(diào)用，將遞歸算法轉(zhuǎn)化為非遞歸算法的方法。 將遞歸算法轉(zhuǎn)化為非遞歸算法的方法主要有：1）采用一個(gè)用戶定義的棧來(lái)模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，只不 過(guò)人工做了本來(lái)由編譯器做的事情，優(yōu)化效果不明顯。2）用遞推來(lái)實(shí)現(xiàn)遞歸函數(shù)。3

14、）通過(guò) Cooper 變換、反演變換能將一些遞歸轉(zhuǎn)化為尾遞歸，從而迭代求出結(jié)果。 后兩種方法在時(shí)空復(fù)雜度上均有較大改善，但其適用范圍有限。6. 簡(jiǎn)要分析分支限界法與回溯法的異同。 1）求解目標(biāo)：回溯法的求解目標(biāo)是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標(biāo) 則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。 2)搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗 費(fèi)優(yōu)先的方式搜索解空間樹。7. 簡(jiǎn)述算法復(fù)雜性的概念，算法復(fù)雜性度量主要指哪兩個(gè)方面？ 算法復(fù)雜性是算法運(yùn)行所需要的計(jì)算機(jī)資源的量，需要時(shí)間資源的量稱為時(shí)

15、間復(fù)雜性，需要的空間資 源的量稱為空間復(fù)雜性。這個(gè)量應(yīng)該只依賴于算法要解的問(wèn)題的規(guī)模、算法的輸入和算法本身的函數(shù)。 如果分別用 N、I 和 A 表示算法要解問(wèn)題的規(guī)模、 算法的輸入和算法本身， 而且用 C 表示復(fù)雜性， 那么， 應(yīng)該有 C=F(N,I,A) 。算法復(fù)雜性度量主要包括算法的時(shí)間復(fù)雜性和算法的空間復(fù)雜性。8. 貪心算法求解的問(wèn)題主要具有哪些性質(zhì)？簡(jiǎn)述之。 貪心算法求解的問(wèn)題一般具有二個(gè)重要的性質(zhì)： 一是貪心選擇性質(zhì)，這是貪心算法可行的第一個(gè)基本要素； 另一個(gè)是最優(yōu)子結(jié)構(gòu)性質(zhì)，問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用貪心算法求解的關(guān)鍵特征。9. 分治法的基本思想是什么？合并排序的基本思想是什

16、么？請(qǐng)分別簡(jiǎn)述之。 分治法的基本思想：將 n 個(gè)輸入分成 k 個(gè)不同子集合， 得到 k 個(gè)不同的可獨(dú)立求解的子問(wèn)題， 其中 1<k w n,而且子問(wèn)題與原問(wèn)題性質(zhì)相同，原問(wèn)題的解可由這些子問(wèn)題的解合并得出。 合并排序基本思想：將待排序元素分成大小大致相同的 2 個(gè)子集合，分別對(duì) 2 個(gè)子集合進(jìn)行排序，最 終將排好序的子集合合并成為所要求的排好序的集合。10. 簡(jiǎn)述分析貪心算法與動(dòng)態(tài)規(guī)劃算法的異同。 貪心算法和動(dòng)態(tài)規(guī)劃算法都要求問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì),這是兩類算法的一個(gè)共同點(diǎn)。 動(dòng)態(tài)規(guī)劃算法通常以自底向上的方式解各子問(wèn)題,而貪心算法則通常以自頂向下的方式進(jìn)行,以迭代 的方式作出相繼的貪心選

17、擇,每作一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為規(guī)模更小的子問(wèn)題。三、算法編寫及算法應(yīng)用分析題：1.已知有 3 個(gè)物品：(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10), 背包的容積 M=2Q 根據(jù) 0-1 背包動(dòng)態(tài)規(guī)劃的遞推式求出最優(yōu)解。解：根據(jù)遞推式f i (X)= maxfj_i (X) , f i-i (Xw )+P i |X > wi 從 i=1 開始，最后得到 f n( M)f1(1) f1(11)= 0f1(12) f1(20)= p1=15f2(1) f2(9)= 0f2(10) f2(11)= maxf1(10), f1(10 - w2)+p2

18、 =13f2(12) f2(20)= maxf1(12), f1(12 - w2)+p2=15f3(20)=maxf2(20)，f2(20 - w3)+p3 = f2(20- 6)+10=25可獲得的最大利潤(rùn)為 25，最優(yōu)解為：( 1，0，1)2. 按要求完成以下關(guān)于排序和查找的問(wèn)題。( 1) 對(duì)數(shù)組 A=15 ，29，135，18，32，1，27，25，5 ，用快速排序方法將其排成遞減序。( 2) 請(qǐng)描述遞減數(shù)組進(jìn)行二分搜索的基本思想，并給出非遞歸算法。( 3) 給出上述算法的遞歸算法。( 4)使用上述算法對(duì)( 1)所得到的結(jié)果搜索如下元素，并給出搜索過(guò)程：18，31，135。解：( 1 )

19、第一步： 15 29 135 18 32 1 27 25 5第二步：29 13518 32 27 251515第三步：135 3229 18 27 251551第四步：135 3229 27 25 181551(2) 基本思想：首先將待搜索元素v與數(shù)組的中間元素 A n進(jìn)行比較，如果v . A -，則在前半部分122元素中搜索v；若v=A n，則搜索成功；否則在后半部分?jǐn)?shù)組中搜索v。2非遞歸算法：輸入：遞減數(shù)組 Aleft:right，待搜索元素 V。輸出：v在A中的位置pos，或者不在A中的消息(-1 )。步驟：【3分】int Bin arySearch(i nt A,i nt left,i

20、 nt right, int v)int mid;while (left<=right)mid=i nt(left+right)/2);if (v=Amid) return mid;else if (v>Amid) right=mid-1;else left=mid+1;return -1;(3) 遞歸算法：輸入：遞減數(shù)組 Aleft:right，待搜索元素 V。輸出：v在A中的位置pos，或者不在A中的消息(-1 )。步驟：int Bin arySearch(i nt A,i nt left,i nt right, int v)int mid;if (left<=right

21、)mid=i nt(left+right)/2);if (v=Amid) return mid;else if (v>Amid) retur n Bin arySearch(A,left,mid-1,v);else return Bin arySearch(A,mid+1,right,v);elsereturn -1;(4) 搜索18:首先與27比較，18<27,在后半部分搜索；再次與 18比較，搜索到，返回 5。搜索31:首先與27比較，31>27,在前半部分搜索；再次 32比較，31<32，在后半部分搜索，與29比較，31>29,此時(shí)只有一個(gè)元素，未找到，返回

22、 -1。搜索135 :首先與27比較，135>27，在前半部分搜索；再次 32比較，135>32,在前半部分搜索；與 135比較，相同，返回 0。(k)、3.已知(aij) ri * ri1 ，k=1，2，3，4，5，6，r 1=5，2=10，3=3，4=12，5=5，6=50，7=6，求1234561015033040516552010 :20360330243019503018093017704030001860501500 :60矩陣鏈積 AX AaX AX AX A X A的最佳求積順序(要求給出計(jì)算步驟) 解：使用動(dòng)態(tài)規(guī)劃算法進(jìn)行求解。求解矩陣為：123456101224

23、220222230344404450560因此，最佳乘積序列為(A1A2)(A3A4)(A5A6),共執(zhí)行乘法2010次。4.根據(jù)分枝限界算法基本過(guò)程，求解0-1背包問(wèn)題。已知， n=3，M=20, (w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。解：用x(i)表示第i步選擇的物品號(hào)，x(1)=1, C( 2 ) = 0, U(2) = 23 ;x(1)=2 , C(3) = 15, U(3) = 25,x(1)=3 , c(4) = 28, U (4) = 28 ,U=min23,25,28=23,由于c(4) = 28>U所以節(jié)點(diǎn)4刪除?；罟?jié)點(diǎn)表

24、L=2,3，取最小代價(jià)估值節(jié)點(diǎn)2作為擴(kuò)展節(jié)點(diǎn)：x(2)=2 , w1+w2>M節(jié)點(diǎn)5是不合理節(jié)點(diǎn)；x(2)=3，這是答案節(jié)點(diǎn)c(6)=13，即找到了代價(jià)為13的解，修改U= 13,由于活節(jié)點(diǎn)表中的節(jié)點(diǎn)3有c(3) = 25,所以節(jié)點(diǎn)3可以刪除。這時(shí)L=,算法結(jié)束。最優(yōu)解 X=1,3搜索產(chǎn)生的狀態(tài)空間樹如下圖：X1=1X1=323X1=228U=23X2=2X2=315節(jié)點(diǎn)6是答 案節(jié)點(diǎn)2531523156035、試用貪心算法求解汽車加油問(wèn)題：已知一輛汽車加滿油后可行駛n 公里，而旅途中有若干個(gè)加油站。試設(shè)計(jì)一個(gè)有效算法，指出應(yīng)在哪些加油站停靠加油，使加油次數(shù)最少，請(qǐng)寫出該算法。解： in

25、t greedy(vecter<int>x,int n)int sum=0,k=x.size();for(int j=0;j<k;j+) if(xj>n)cout<< ” No solution ” <<endl;return -1;for(int i=0,s=0;i<k;i+)s+=xi;if(s>n) sum+;s=xi;return sum;6、 試用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)下列問(wèn)題：設(shè)A和B是兩個(gè)字符串。我們要用最少的字符操作，將字符串 換為字符串B,這里所說(shuō)的字符操作包括：(1) 刪除一個(gè)字符。(2) 插入一個(gè)字符。(3) 將一個(gè)字

26、符改為另一個(gè)字符。 請(qǐng)寫出該算法。解：此題用動(dòng)態(tài)規(guī)劃算法求解：int dist( )int m=a.size( );int n=b.size( ); vector<int>d(n+1,0);for(int i=1;i<=n;i+) di=i; for(i=1;i<=m;i+) int y=i-1;for(int j=1;j<=n;j+)int x=y;y=dj;int z=j>1?dj-1:i;int del=ai-1= =bj-1?0:1; dj=min(x+del,y+1,z+1);return dn;7、對(duì)于下圖使用 Dijkstra 算法求由頂點(diǎn) a

27、 到頂點(diǎn) h 的最短路徑。最短路徑中的邊，E2為與Vi中的頂點(diǎn)相鄰接且距離最短的路徑。步驟V 1V2 E1E21.abab2.a,bdabbd3.a,b,dc,fab,bddc,df4.a,b,d,cfab,bddf5.a,b,c,d,feab,bd,dc,dffe6.a,b,c,d,e,fgab,bd,dc,df,feeg7.a,b,c,d,e,f,ghab,bd,dc,df,fe,eggh8.a,b,c,d,e,f,g,h ab,bd,de,df,fe,eg,gh 結(jié)果:從a到h的最短路徑為a： b： d ： f ； e： g ： h，權(quán)值為 18。解：用V表示已經(jīng)找到最短路徑的頂點(diǎn),求所

28、有頂點(diǎn)對(duì)之間的最短路徑可以使用Dijkstra 算法，使其起始節(jié)點(diǎn)從到其他節(jié)點(diǎn)的最短路徑，最終可以求得所有頂點(diǎn)對(duì)之間的最短路徑。8、試寫出用分治法對(duì)數(shù)組An實(shí)現(xiàn)快速排序的算法。解：用分治法求解的算法代碼如下：int partiti on( float A,i nt p,i nt r)V2表示與Vi中某個(gè)頂點(diǎn)相鄰接且不在Vi中的頂點(diǎn)；Ei表示加入到a循環(huán)到h，每次求起始節(jié)點(diǎn)int i=p,j=r+1;float x=ap;while (1) while(a+i<x);while(a_-j>x);if(i>=j) break;ai匚 a j;ap=aj;aj=x;return j

29、;void Quicksort float a, int p, int r )if( p<r) int q=partiti on( a,p,r);Quicksort(a,p,q-1);Quicksort(a,q+1,r);Quicksort(a,0, n-1);9、 有n個(gè)活動(dòng)爭(zhēng)用一個(gè)活動(dòng)室。已知活動(dòng)i占用的時(shí)間區(qū)域?yàn)閟 i, f i，活動(dòng)i,j相容的條件是：sj >f i,問(wèn)題的解表示為(Xi | x i =1，2，n,) , Xi表示順序?yàn)閕的活動(dòng)編號(hào)活動(dòng)，求一個(gè)相容的活動(dòng)子集，且安排的活動(dòng)數(shù)目最多。解：解決這個(gè)問(wèn)題的基本思路是在安排時(shí)應(yīng)該將結(jié)束時(shí)間早的活動(dòng)盡量往前安排，好給后

30、面的活動(dòng)安排 留出更多的空間，從而達(dá)到安排最多活動(dòng)的目標(biāo)。據(jù)此，貪心準(zhǔn)則應(yīng)當(dāng)是：在未安排的活動(dòng)中挑選結(jié)束時(shí) 間最早的活動(dòng)安排。在貪心算法中，將各項(xiàng)活動(dòng)的開始時(shí)間和結(jié)束時(shí)間分別用兩個(gè)數(shù)組s和f存儲(chǔ)，并使得數(shù)組中元素的順序按結(jié)束時(shí)間非減排列：fl < f2蘭< fn。算法如下：GreedyAction(s, f , n) / s1:n、f1:n 分別代表 n 項(xiàng)活動(dòng)的起始/時(shí)間和結(jié)束時(shí)間，并且滿足f1 < f2 乍fnj=1; solutio n=1; /解向量初始化為空集for i j 2 to n doif si_fj the nsolution=solutionj; / 將

31、 j 加入解中j=i;en difendforretur n( soluti on);end Greedy10、 設(shè)X1、X2、X3是一個(gè)三角形的三條邊，而且X1+X2+X3=14。請(qǐng)問(wèn)有多少種不同的三角形？給出解答過(guò)程。解：由于 x1、x2、x3 是三角形的三條邊，從而 xi+xj>xk , |xi-xj|<xk , (i,j,k=1,2,3)，根據(jù) x1+x2+x3=14可知1<xi<7 (i=1,2,3 )。利用回溯法求解得到：x1=6X2=65 4 35IIX3=2即有 4 個(gè)可行解：(6, 6, 2), (6, 5, 3), (6, 4, 4,) ( 5, 5

32、, 4 )。11、設(shè)數(shù)組A有n個(gè)元素，需要找出其中的最大最小值。(1) 請(qǐng)給出一個(gè)解決方法，并分析其復(fù)雜性。(2) 把n個(gè)元素等分為兩組 A1和A2,分別求這兩組的最大值和最小值，然后分別將這兩組的最大值和最小值相比較，求出全部元素的最大值和最小值。如果A1和A2中的元素多于兩個(gè)，則再用上述方法各分為兩個(gè)子集。直至子集中元素至多兩個(gè)元素為止。這是什么方法的思想？請(qǐng)給出該方法的算法描述，并分析其復(fù)雜性。解：(1)基本思想：從頭到尾逐個(gè)掃描，紀(jì)錄最大和最小元素。輸入：具有n個(gè)元素的數(shù)組輸出：最大值和最小值步驟：void Fin dMaxM in (i nt A, int n, int max, i

33、nt min)max=mi n=A0;for (i=1;i <n ;i+)if (Ai>max) max=Ai;if (Ai<min) min=Ai;復(fù)雜性分析：由于是從頭到尾掃描各個(gè)元素，而每個(gè)元素都要與max和min比較一遍，從而時(shí)間復(fù)雜性為：0(n)。(2) void FindMaxMin(int left,int right, int max, int min)if (left=right) max=min=Aleft;else if (left=right-1)max=(Aleft<Aright?Aright:Aleft);min=( Aleft<Ari

34、ght?Aleft:Aright);elsemid=(left+right)/2;Fi ndMaxMi n( left,mid,gmax,gmi n);Fin dMaxM in( mid+1,right,hmax,hm in);max=(gmax<hmax?hmax:gmax);min=(gmi n<hmi n? gmi n:hmi n);n12、有n個(gè)程序和長(zhǎng)度為L(zhǎng)的磁帶，程序i的長(zhǎng)度為ai，已知q - L ,求最優(yōu)解(Xi,X2,.,為，i=1nXn), Xi =0 , 1, x i =1，表示程序i存入磁帶，Xi =0 ,表示程序i不存入磁帶，滿足v xia L ,且存放i

35、J的程序數(shù)目最多。解：由于目標(biāo)是存放的程序數(shù)目最多，所以最優(yōu)量度應(yīng)該是mina i | a i為程序i的長(zhǎng)度,即每次選入的程序都是當(dāng)前最短的。我們可以將n個(gè)程序按a1 <a2 ww an順序排序，然后從i=1開始依次選擇。算法如下：procedure program min g(L ,n, a, x)beginn個(gè)程序按a1 wa2an順序排序x J 0;i=1;while (ai w L and i w n) do xi j 1; L j L-ai ; i J i+ 1;en d.13、 試用分治法實(shí)現(xiàn)有重復(fù)元素的排列問(wèn)題：設(shè)R r1,r2,.,rn)是要進(jìn)行排列的n個(gè)元素，其中元素r

36、1,r2,.,rn可能相同，試設(shè)計(jì)計(jì)算R的所有不同排列的算法。解：解答如下：Template<class Type>void Perm(Type list,int k,int m)if(k= =m)for(int i=0;i<=m;i+) cout<<listi;cout<<endl;else for(int i=k;i<=m;i+) if(ok(list,k,i) swap(listk,listi); Perm(list,k+1,m); swap(listk,listi);其中 ok 用于判別重復(fù)元素。Template<class>

37、int ok(Type list,int k,int i)if(i>k)for(int t=k;t<I;t+)if(listt= =listi) return 0;return 1;14、試用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn) 0-1 閉包問(wèn)題，請(qǐng)寫出該算法。 解：解答如下：Template<class>void Knapsack(Type v,int w,int c,int n,Type *m)Int jMax=min(wn-1,c);for(int j=0;j<=jMax;j+) mnj=0;for(int j=wn;j<=c;j+) mnj=vn;for(int i=n

38、-1;i>1;i-) jMax=min(wi-1,c); for(int j=0;j<=jMax;j+) mij=mi+1j;for(int j=wi;j<=c;j+) mij=max(mi+1j,mi+1j-wi+vi); ;m1c=m2c; if(c>=w1) m1c=max(m1c,m2c-w1+v1);Template<class>Void Traceback(Type *m,int w,int c,int n,int x)for(int i=1;i<n;i+) if(mic= =mi+1c) xi=0;else xi=1,c-=wi; xn=

39、(mnc)?1:0;15、試用貪心算法求解下列問(wèn)題：將正整數(shù)n 分解為若干個(gè)互不相同的自然數(shù)之和，使這些自然數(shù)的乘積最大，請(qǐng)寫出該算法。解：解答如下：void dicomp(int n,int a)k=1;if(n<3) a1=0;return;if(n<5) ak=1;a+k=n-1;return;a1=2;n-=2;while(n>ak)k+;ak=ak-1+1;n-=ak;if(n= =ak) ak+;n-;for(int i=0;i<n;i+) ak-i+;16、試寫出用分治法對(duì)一個(gè)有序表實(shí)現(xiàn)二分搜索的算法。解：解答如下：Template<class>

40、;int BinarySearch(Type a,const Type& x,int n)/ 否則返回 -1/ 假定數(shù)組 a 已按非遞減有序排列，本算法找到 x 后返回其在數(shù)組 a 中的位置， int left=0,right=n-1;while(left<=right)int middle=(left+right)/2;if(x= =amiddle) return middle+1;if(x>amiddle) left=middle+1;else right=middle-1;return -1;17、試用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)最長(zhǎng)公共子序列問(wèn)題，請(qǐng)寫出該算法。 解：用動(dòng)態(tài)規(guī)劃

41、算法求解的算法代碼如下：int lcs_len(char *a,char *b,int cN)int m=strlen(a),n=strlen(b),i,j;for(i=0;i<=m;i+) ci0=0;for(j=1;j<=n;j+) c0j=0;for(i=1;i<=m;i+)for(j=1;j<=n;j+)if(ai-1= =bj-1) cij=ci-1j-1+1;else if(ci-1j>=cij-1)cij=ci-1j;else cij=cij-1;return cmn;char *build_lcs(char s,char *a,char *b)in

42、t k,i=strle n( a),j=strle n(b),cNN;k=lcs_le n( a,b,c);sk=' 0 'while(k>0)if(cij= =ci-1j) i-;else if(cij= =cij-1) j-;elses-k=ai-1;i-,j-;return s;18、假設(shè)有7個(gè)物品，它們的重量和價(jià)值如下表所示。若這些物品均不能被分割，且背包容量用回溯方法求解此背包問(wèn)題，請(qǐng)寫出狀態(tài)空間搜索樹。物品ABCDEFG重量35306050401025價(jià)值10403050354030解：按照單位效益從大到小依次排列這7個(gè)物品為：FBGDECA將它們的序號(hào)分別記

43、為 1M= 150,使7。則可生產(chǎn)如aaaiaxdeX4bhegcXsX5 =0X4 TX4 zz0X3 JX 二 1X2弓X-i =1X4 二1a. 40 +40 +30 +50 +35 J50 i15 =190.625 (1,1,1,1,-,0,0)408A C Q _ A A C-7b. 40 +40 *30 +50 +30 X=一 =177.5 (11110丄 0)6012c. 40 40 30 50 10 =170(1,1,1,1,0,0,1)d. 40 +40 +30 +35 +30 J50 一105 =167.5 (1 1 1 0 1 3 0)60k4 7下的狀態(tài)空間搜索樹。其中

44、各個(gè)節(jié)點(diǎn)處的限界函數(shù)值通過(guò)如下方式求得：e.4040 50 35 - 30 150 -13° =17560(1,1Q1,1=0)f.150 -13040 4050 3510170.7135(1,1,0,1,1,0,»g.40 40 50 30 =160(1,1,0,1,0,1,0)h.40 40 35 30 10 150 一14° =146.8535(1,1,0,0,1,1,-2)i.40 30 50 35 30 150 一125605.g,0,1,1,1,®0)j.40 +30 +50 +35 +30 丿50 一145 =157.5(01111丄 0)

45、60 12 '丿在Q處獲得該問(wèn)題的最優(yōu)解為(1, 1,1,1, 0,0 , 1),背包效益為170。即在背包中裝入物品到最大效益，為 170,重量為150。19、求解子集和問(wèn)題：對(duì)于集合S=1，2，6，8，求子集，要求該子集的元素之和 畫出子集和問(wèn)題的解空間樹； 該樹運(yùn)用回溯算法，寫出依回溯算法遍歷節(jié)點(diǎn)的順序； 如果S中有n個(gè)元素，指定d，用偽代碼描述求解子集和問(wèn)題的回溯算法。解答：滿足要求的子集有1，2，6，1，8解空間樹如下：F、B、G D A 時(shí)達(dá) d=9。BFED0L?!0eG N ? ? O ? ?A BK V W C F L X Y M Z0 1八00 1/ 1 0 1 &

46、#39;1,0 1 110I： 遍歷結(jié)點(diǎn)的順序?yàn)椋?用偽代碼描述算法如下:#in clude<stdio.h>#define N 100int as=0,t=0;int sum;void backtrackiter(i nt i,i nt s,i nt n ,i nt d,i nt sum) if(i> n) return;elseif(as=d)t+;return;sum-=si;if(as+si<=d)as+=si;backtrackiter(i+1,s,n,d,sum);as-=si;if(as+sum>=d)backtrackiter(i+1,s,n,d,

47、sum);sum+=si;20、求解填字游戲問(wèn)題：在3X 3個(gè)方格的方陣中要填入數(shù)字1到N( N10)內(nèi)的某9個(gè)數(shù)字，每個(gè)方格填一個(gè)整數(shù)，似的所有相鄰兩個(gè)方格內(nèi)的兩個(gè)整數(shù)之和為質(zhì)數(shù)。試采用回溯法寫出滿足這個(gè)要求的一種數(shù) 字填法的算法和滿足這個(gè)要求的全部數(shù)字填法的算法。解：為找到一個(gè)滿足要求的 9 個(gè)數(shù)的填法，從還未填一個(gè)數(shù)開始，按某種順序(如從小到大的順序)每次在當(dāng)前位置填入一個(gè)整數(shù)，然后檢查當(dāng)前填入的整數(shù)是否能滿足要求。在滿足要求的情況下，繼續(xù)用 同樣的方法為下一方格填入整數(shù)。如果最近填入的整數(shù)不能滿足要求，就改變填入的整數(shù)。如對(duì)當(dāng)前方格 試盡所有可能的整數(shù)，都不能滿足要求，就得回退到前一方格，并調(diào)整前一方格填入的整數(shù)。如此重復(fù)執(zhí) 行擴(kuò)展、檢查或調(diào)整、檢查，直到找到一個(gè)滿足問(wèn)題要求的解，將解輸出?；厮莘ㄕ乙粋€(gè)解的算法： int m=0,ok=1;int n=8;doif (ok) 擴(kuò)展 ;else 調(diào)整 ;ok=檢查前m個(gè)整數(shù)填放的合理性； while (!ok|m!=n)&&(m!=0)if (m!=0)輸出解 ；else輸出無(wú)解報(bào)告；如果要找全部解，則在