1、二、簡(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.分治法的基本思想是什么？合并排序的基本思想是什么？請(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)=(1

2、5,13,10),背包的容積M=20，根據(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.已知，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50，r7=6，求矩陣鏈積A1×A2×A3×A4×A5×A6的最佳求積順序（要求給出

3、計(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是兩個(gè)字符串。我們要用最少的字符操作，將字符串A轉(zhuǎn)換為字符串B，這里所說(shuō)的字符操作包括：刪除一個(gè)字符。插入一個(gè)字符。將一個(gè)字符改為另一個(gè)字符。請(qǐng)寫出該算法。7.對(duì)于下圖使用Dijkstra算法求由頂點(diǎn)a到頂點(diǎn)h的最短路

4、徑。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相容的條件是：sjf i，問(wèn)題的解表示為(xi| xi =1，2，n,)，xi表示順序?yàn)閕的活動(dòng)編號(hào)活動(dòng)，求一個(gè)相容的活動(dòng)子集，且安排的活動(dòng)數(shù)目最多。10.設(shè)x1、x2、x3是一個(gè)三角形的三條邊，而且x1+x2+x3=14。請(qǐng)問(wèn)有多少種不同的三角形？給出解答過(guò)程。11.設(shè)數(shù)組A有n個(gè)元素，需要找出其中的最大最小值。請(qǐng)給出一個(gè)解決方法，并分析其復(fù)雜性。把n個(gè)元素等分為兩組A1和A2，分別求這兩組的最大值和最小值，然后分別將這兩組的最大值和最小值相比較，求出全部元素的

5、最大值和最小值。如果A1和A2中的元素多于兩個(gè)，則再用上述方法各分為兩個(gè)子集。直至子集中元素至多兩個(gè)元素為止。這是什么方法的思想？請(qǐng)給出該方法的算法描述，并分析其復(fù)雜性。12.有n個(gè)程序和長(zhǎng)度為L(zhǎng)的磁帶，程序i的長(zhǎng)度為ai，已知，求最優(yōu)解(xi，x2 ，.，xi， xn)，xi =0，1, xi =1，表示程序i存入磁帶，xi =0，表示程序i不存入磁帶，滿足，且存放的程序數(shù)目最多。13.試用分治法實(shí)現(xiàn)有重復(fù)元素的排列問(wèn)題：設(shè)是要進(jìn)行排列的個(gè)元素，其中元素可能相同，試設(shè)計(jì)計(jì)算的所有不同排列的算法。14.試用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)0-1閉包問(wèn)題，請(qǐng)寫出該算法。15.試用貪心算法求解下列問(wèn)題：將正整數(shù)n

6、分解為若干個(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à)值如下表所示。若這些物品均不能被分割，且背包容量M150，使用回溯方法求解此背包問(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，

7、用偽代碼描述求解子集和問(wèn)題的回溯算法。20.求解填字游戲問(wèn)題：在3×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ù)字填法的算法。21.試用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)最大子矩陣和問(wèn)題：求矩陣A的一個(gè)子矩陣，使其各元素之和為最大。22.試用回溯法解決下列整數(shù)變換問(wèn)題：關(guān)于整數(shù)的變換和定義如下：。對(duì)于給定的兩個(gè)整數(shù)和，要求用最少的變換和變換次數(shù)將變?yōu)椤?3.關(guān)于15謎問(wèn)題。在一個(gè)4×4的方格的棋盤上，將數(shù)字1到15代表的15個(gè)棋子以任意的順序置入

8、各方格中，空出一格。要求通過(guò)有限次的移動(dòng)，把一個(gè)給定的初始狀態(tài)變成目標(biāo)狀態(tài)。移動(dòng)的規(guī)則是：每次只能把空格周圍的四格數(shù)字（棋子）中的任意一個(gè)移入空格，從而形成一個(gè)新的狀態(tài)。為了有效的移動(dòng)，設(shè)計(jì)了估值函數(shù)C1(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)二、簡(jiǎn)答題：1.備忘錄方法和動(dòng)態(tài)規(guī)劃算法相比有何異同？簡(jiǎn)述之。備忘錄方法是動(dòng)態(tài)規(guī)劃算法的變形。與動(dòng)態(tài)規(guī)劃算法一樣，備忘錄方法用表格保存已解決

9、的子問(wèn)題的答案，在下次需要解此問(wèn)題時(shí)，只要簡(jiǎn)單地查看該子問(wèn)題的解答，而不必重新計(jì)算。備忘錄方法與動(dòng)態(tài)規(guī)劃算法不同的是，備忘錄方法的遞歸方式是自頂向下的，而動(dòng)態(tài)規(guī)劃算法則是自底向上遞歸的。因此，備忘錄方法的控制結(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ī)劃算法

10、求解的基本要素包括：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í)間查看一下結(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)化為非遞歸算法的方法

11、主要有：1）采用一個(gè)用戶定義的棧來(lái)模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，只不過(guò)人工做了本來(lái)由編譯器做的事情，優(yōu)化效果不明顯。2）用遞推來(lái)實(shí)現(xiàn)遞歸函數(shù)。3）通過(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)先或以

12、最小耗費(fèi)優(yōu)先的方式搜索解空間樹。7.簡(jiǎn)述算法復(fù)雜性的概念，算法復(fù)雜性度量主要指哪兩個(gè)方面？算法復(fù)雜性是算法運(yùn)行所需要的計(jì)算機(jī)資源的量，需要時(shí)間資源的量稱為時(shí)間復(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)

13、子結(jié)構(gòu)性質(zhì)，問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用貪心算法求解的關(guān)鍵特征。9.分治法的基本思想是什么？合并排序的基本思想是什么？請(qǐng)分別簡(jiǎn)述之。分治法的基本思想：將n個(gè)輸入分成k個(gè)不同子集合，得到k個(gè)不同的可獨(dú)立求解的子問(wèn)題，其中1<kn，而且子問(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ī)劃算法通常以自底向上的方式解各子

14、問(wèn)題，而貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問(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=20，根據(jù)0-1背包動(dòng)態(tài)規(guī)劃的遞推式求出最優(yōu)解。解：根據(jù)遞推式 fi（X）maxfi-1(X)，fi-l(Xwi)+pi |Xwi 從i=1開始，最后得到fn（M）f1(1) f1(11)= 0 f1(12) f1(20)= p1=15f2(1) f2(9)= 0f2(10) f2(11)= maxf1(10)，f1

15、(10 w2)+p2 =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）第一步：15 2

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

17、id;while (left<=right)mid=int(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 BinarySearch(int A,int left,int right,int v)int mid;if (left<=right)mid=int(left+right)/2);if (v=Am

18、id) return mid;else if (v>Amid) return BinarySearch(A,left,mid-1,v);else return BinarySearch(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è)元素，未找到，返回-1。 搜索135：首先與27比較，135>27，在前半部分搜索；再次3

19、2比較，135>32，在前半部分搜索；與135比較，相同，返回0。3.已知，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50，r7=6，求矩陣鏈積A1×A2×A3×A4×A5×A6的最佳求積順序（要求給出計(jì)算步驟）。解：使用動(dòng)態(tài)規(guī)劃算法進(jìn)行求解。求解矩陣為：12345610150330405165520102036033024301950301809301770403000186050150060123456101224220222230344404450560因此，最佳乘積序列為（A1A2）（

20、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，()0，U(2)23 ;x(1)=2，(3)15，U(3)25, x(1)=3，(4)28，U (4)28 , U=min23,25,28=23, 由于(4)28>U 所以節(jié)點(diǎn)刪除。活節(jié)點(diǎn)表=2,3，取最小代價(jià)估值節(jié)點(diǎn)作為擴(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，即

21、找到了代價(jià)為13的解，修改U13，由于活節(jié)點(diǎn)表中的節(jié)點(diǎn)3有(3)25，所以節(jié)點(diǎn)3可以刪除。這時(shí)L ，算法結(jié)束。最優(yōu)解X=1,3搜索產(chǎn)生的狀態(tài)空間樹如下圖：12561230251528U=23734X1=1X1=2X2=3X1=3X2=223013131515節(jié)點(diǎn)6是答案節(jié)點(diǎn)5、試用貪心算法求解汽車加油問(wèn)題：已知一輛汽車加滿油后可行駛n公里，而旅途中有若干個(gè)加油站。試設(shè)計(jì)一個(gè)有效算法，指出應(yīng)在哪些加油站停靠加油，使加油次數(shù)最少，請(qǐng)寫出該算法。解：int greedy(vecter<int>x,int n) int sum=0,k=x.size();for(int j=0;j<k

22、;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è)字符串。我們要用最少的字符操作，將字符串A轉(zhuǎn)換為字符串B，這里所說(shuō)的字符操作包括：(1)刪除一個(gè)字符。(2)插入一個(gè)字符。(3)將一個(gè)字符改為另一個(gè)字符。請(qǐng)寫出該算法。解：此題用動(dòng)態(tài)規(guī)劃算法求解：int dist( ) int m=a.size( ); int n=b.size(

23、); 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到頂點(diǎn)h的最短路徑。解：用V1表示已經(jīng)找到最短路徑的頂點(diǎn)，V2表示與V1中某個(gè)頂點(diǎn)相鄰接且不在V1中的頂點(diǎn)；E1表示加入到最短路徑中的

24、邊，E2為與V1中的頂點(diǎn)相鄰接且距離最短的路徑。步驟 V1 V2 E1 E21. ab ab2. a,bd ab bd3. a,b,d c,f ab,bd dc,df4. a,b,d,c f ab,bd df5. a,b,c,d,f e ab,bd,dc,df fe6. a,b,c,d,e,fg ab,bd,dc,df,fe eg7. a,b,c,d,e,f,gh ab,bd,dc,df,fe,eggh8. a,b,c,d,e,f,g,h ab,bd,de,df,fe,eg,gh 結(jié)果：從a到h的最短路徑為，權(quán)值為18。求所有頂點(diǎn)對(duì)之間的最短路徑可以使用Dijkstra算法，使其起始節(jié)點(diǎn)從a循

25、環(huán)到h，每次求起始節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路徑，最終可以求得所有頂點(diǎn)對(duì)之間的最短路徑。8、試寫出用分治法對(duì)數(shù)組An實(shí)現(xiàn)快速排序的算法。解：用分治法求解的算法代碼如下： int partition(float A,int p,int r) int i=p,j=r+1; float x=ap; while (1) while(a+i<x); while(a-j>x); if(i>=j) break; ai ; ap=aj; aj=x; return j; void Quicksort( float a, int p, int r ) if( p<r) int q=partiti

26、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相容的條件是：sjf i，問(wèn)題的解表示為(xi| xi =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)盡量往前安排，好給后面的活動(dòng)安排留出更多的空間，從而達(dá)到安排最多活動(dòng)的目標(biāo)。據(jù)此，貪心準(zhǔn)則應(yīng)當(dāng)是：在未安排的活動(dòng)中挑選結(jié)束時(shí)間最早的活動(dòng)安排。在貪心算法中，將各項(xiàng)活

27、動(dòng)的開始時(shí)間和結(jié)束時(shí)間分別用兩個(gè)數(shù)組s和f存儲(chǔ)，并使得數(shù)組中元素的順序按結(jié)束時(shí)間非減排列：f1£ f2££ fn。算法如下：GreedyAction(s, f，n) / s1:n、f1:n分別代表n項(xiàng)活動(dòng)的起始/時(shí)間和結(jié)束時(shí)間, 并且滿足f1£ f2££ fnj=1; solution=1; /解向量初始化為空集for i 2 to n do if si³fj then solution=solution È j; / 將j加入解中 j=i; endifendforreturn(solution);end Gree

28、dy10、設(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）。利用回溯法求解得到：即有4個(gè)可行解：（6，6，2），（6，5，3），（6，4，4，）（5，5，4）。11、設(shè)數(shù)組A有n個(gè)元素，需要找出其中的最大最小值。（1） 請(qǐng)給出一個(gè)解決方法，并分析其復(fù)雜性。（2） 把n個(gè)元素等分為兩組A1和A2，分別求這兩組的最大值和最小值，然后分別將這兩組

29、的最大值和最小值相比較，求出全部元素的最大值和最小值。如果A1和A2中的元素多于兩個(gè)，則再用上述方法各分為兩個(gè)子集。直至子集中元素至多兩個(gè)元素為止。這是什么方法的思想？請(qǐng)給出該方法的算法描述，并分析其復(fù)雜性。解：（1）基本思想：從頭到尾逐個(gè)掃描，紀(jì)錄最大和最小元素。輸入：具有n個(gè)元素的數(shù)組輸出：最大值和最小值步驟：void FindMaxMin(int A, int n, int max, int min)max=min=A0;for (i=1;i<n;i+) if (Ai>max) max=Ai;if (Ai<min) min=Ai;復(fù)雜性分析：由于是從頭到尾掃描各個(gè)元素，

30、而每個(gè)元素都要與max和min比較一遍，從而時(shí)間復(fù)雜性為：O(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<Aright?Aleft:Aright);elsemid=(left+right)/2;FindMaxMin(left,mid,gmax,gmin);FindMaxMin(mid+1,right,hmax,hmin)

31、;max=(gmax<hmax?hmax:gmax);min=(gmin<hmin?gmin:hmin);12、有n個(gè)程序和長(zhǎng)度為L(zhǎng)的磁帶，程序i的長(zhǎng)度為ai，已知，求最優(yōu)解(xi，x2 ，.，xi， xn)，xi =0，1, xi =1，表示程序i存入磁帶，xi =0，表示程序i不存入磁帶，滿足，且存放的程序數(shù)目最多。解：由于目標(biāo)是存放的程序數(shù)目最多，所以最優(yōu)量度應(yīng)該是minai | ai為程序i的長(zhǎng)度，即每次選入的程序都是當(dāng)前最短的。我們可以將n個(gè)程序按a1a2an順序排序，然后從i=1開始依次選擇。算法如下：procedure programming(L,n, a, x)be

32、gin /n個(gè)程序按a1a2an順序排序x0; i=1; while (ai L and in) do xi 1; LL-ai；ii+ 1; end.13、試用分治法實(shí)現(xiàn)有重復(fù)元素的排列問(wèn)題：設(shè)是要進(jìn)行排列的個(gè)元素，其中元素可能相同，試設(shè)計(jì)計(jì)算的所有不同排列的算法。解：解答如下： 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+) i

33、f(ok(list,k,i) swap(listk,listi); Perm(list,k+1,m); swap(listk,listi); ; 其中ok用于判別重復(fù)元素。 Template<class> 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,i

34、nt 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-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

35、>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=(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)

36、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> int BinarySearch(Type a,const Type& x,int n)/假定數(shù)組a已按非遞減有序排列，本算法找到x后返回其在數(shù)組a中的位置，/否則返回-1 int left=0,right=n-1; while(left<=right) int middle=(left+right)/2; if(x= =amiddle

37、) 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ī)劃算法求解的算法代碼如下： 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-

38、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) int k,i=strlen(a),j=strlen(b),cNN; k=lcs_len(a,b,c); sk=0; while(k>0) if(cij= =ci-1j) i-; else if(cij= =cij-1) j-; else s-k=ai-1; i-,j-; return s; 18、假設(shè)有7個(gè)物品，它們的重量和價(jià)值

39、如下表所示。若這些物品均不能被分割，且背包容量M150，使用回溯方法求解此背包問(wèn)題，請(qǐng)寫出狀態(tài)空間搜索樹。物品ABCDEFG重量35306050401025價(jià)值10403050354030解：按照單位效益從大到小依次排列這7個(gè)物品為：FBGDECA。將它們的序號(hào)分別記為17。則可生產(chǎn)如下的狀態(tài)空間搜索樹。其中各個(gè)節(jié)點(diǎn)處的限界函數(shù)值通過(guò)如下方式求得：a b. c d. e. f. g. h. i.j. 在Q1處獲得該問(wèn)題的最優(yōu)解為，背包效益為170。即在背包中裝入物品F、B、G、D、A時(shí)達(dá)到最大效益，為170，重量為150。19、求解子集和問(wèn)題：對(duì)于集合S=1，2 ，6，8，求子集，要求該子集的

40、元素之和d=9。畫出子集和問(wèn)題的解空間樹；該樹運(yùn)用回溯算法，寫出依回溯算法遍歷節(jié)點(diǎn)的順序； 如果S中有n個(gè)元素，指定d，用偽代碼描述求解子集和問(wèn)題的回溯算法。解答：滿足要求的子集有1，2，6， 1，8解空間樹如下：R1P1T1X1V1Ô1Z1Â1U0S0W0Y0Ê0Û0Î0Q0遍歷結(jié)點(diǎn)的順序?yàn)椋篈 B D H P Q I R S E J T U K V W C F L X Y M ZÊ G N Ô ÛO Â Î用偽代碼描述算法如下：#include<stdio.h>#define N

41、 100int as=0,t=0;int sum;void backtrackiter(int i,int s,int n,int d,int 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,sum);sum+=si;20、求解填字游戲問(wèn)題：在3×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ù)，都不能滿足要求，就得回退到前一方格，并