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

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

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

3、，r4=12，r5=5，r6=50，r7=6，求矩陣鏈積A1×A2×A3×A4×A5×A6的最佳求積順序（要求給出計算步驟）。4.根據(jù)分枝限界算法基本過程,求解0-1背包問題。已知n=3,M=20，(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。5.試用貪心算法求解汽車加油問題：已知一輛汽車加滿油后可行駛n公里，而旅途中有若干個加油站。試設(shè)計一個有效算法，指出應(yīng)在哪些加油站?？考佑?，使加油次數(shù)最少，請寫出該算法。6.試用動態(tài)規(guī)劃算法實現(xiàn)下列問題：設(shè)A和B是兩個字符串。我們要用最少的字符操作，將字符串A轉(zhuǎn)換為

4、字符串B，這里所說的字符操作包括：刪除一個字符。插入一個字符。將一個字符改為另一個字符。請寫出該算法。7.對于下圖使用Dijkstra算法求由頂點a到頂點h的最短路徑。8.試寫出用分治法對數(shù)組An實現(xiàn)快速排序的算法。9.有n個活動爭用一個活動室。已知活動i占用的時間區(qū)域為si，f i，活動i,j相容的條件是：sjf i，問題的解表示為(xi| xi =1，2，n,)，xi表示順序為i的活動編號活動，求一個相容的活動子集，且安排的活動數(shù)目最多。10.設(shè)x1、x2、x3是一個三角形的三條邊，而且x1+x2+x3=14。請問有多少種不同的三角形？給出解答過程。11.設(shè)數(shù)組A有n個元素，需要找出其中的

5、最大最小值。請給出一個解決方法，并分析其復(fù)雜性。把n個元素等分為兩組A1和A2，分別求這兩組的最大值和最小值，然后分別將這兩組的最大值和最小值相比較，求出全部元素的最大值和最小值。如果A1和A2中的元素多于兩個，則再用上述方法各分為兩個子集。直至子集中元素至多兩個元素為止。這是什么方法的思想？請給出該方法的算法描述，并分析其復(fù)雜性。12.有n個程序和長度為L的磁帶，程序i的長度為ai，已知，求最優(yōu)解(xi，x2 ，.，xi， xn)，xi =0，1, xi =1，表示程序i存入磁帶，xi =0，表示程序i不存入磁帶，滿足，且存放的程序數(shù)目最多。13.試用分治法實現(xiàn)有重復(fù)元素的排列問題：設(shè)是要進

6、行排列的個元素，其中元素可能相同，試設(shè)計計算的所有不同排列的算法。14.試用動態(tài)規(guī)劃算法實現(xiàn)0-1閉包問題，請寫出該算法。15.試用貪心算法求解下列問題：將正整數(shù)n分解為若干個互不相同的自然數(shù)之和，使這些自然數(shù)的乘積最大，請寫出該算法。16.試寫出用分治法對一個有序表實現(xiàn)二分搜索的算法。17.試用動態(tài)規(guī)劃算法實現(xiàn)最長公共子序列問題，請寫出該算法。18.假設(shè)有7個物品，它們的重量和價值如下表所示。若這些物品均不能被分割，且背包容量M150，使用回溯方法求解此背包問題，請寫出狀態(tài)空間搜索樹。物品ABCDEFG重量35306050401025價值1040305035403019.求解子集和問題：對于

7、集合S=1，2 ，6，8，求子集，要求該子集的元素之和d=9。畫出子集和問題的解空間樹；該樹運用回溯算法，寫出依回溯算法遍歷節(jié)點的順序；如果S中有n個元素，指定d，用偽代碼描述求解子集和問題的回溯算法。20.求解填字游戲問題：在3×3個方格的方陣中要填入數(shù)字1到N（N10）內(nèi)的某9個數(shù)字，每個方格填一個整數(shù)，似的所有相鄰兩個方格內(nèi)的兩個整數(shù)之和為質(zhì)數(shù)。試采用回溯法寫出滿足這個要求的一種數(shù)字填法的算法和滿足這個要求的全部數(shù)字填法的算法。21.試用動態(tài)規(guī)劃算法實現(xiàn)最大子矩陣和問題：求矩陣A的一個子矩陣，使其各元素之和為最大。22.試用回溯法解決下列整數(shù)變換問題：關(guān)于整數(shù)的變換和定義如下：

8、。對于給定的兩個整數(shù)和，要求用最少的變換和變換次數(shù)將變?yōu)椤?3.關(guān)于15謎問題。在一個4×4的方格的棋盤上，將數(shù)字1到15代表的15個棋子以任意的順序置入各方格中，空出一格。要求通過有限次的移動，把一個給定的初始狀態(tài)變成目標(biāo)狀態(tài)。移動的規(guī)則是：每次只能把空格周圍的四格數(shù)字（棋子）中的任意一個移入空格，從而形成一個新的狀態(tài)。為了有效的移動，設(shè)計了估值函數(shù)C1(x)，表示在結(jié)點x的狀態(tài)下，沒有到達目標(biāo)狀態(tài)下的正確位置的棋子的個數(shù)。請使用該估計函數(shù)，對圖示的初始狀態(tài)，給出使用分支限界方法轉(zhuǎn)換到目標(biāo)狀態(tài)的搜索樹。1245637910128131411151234567891011121314

9、15 初始狀態(tài) 目標(biāo)狀態(tài)參考答案一、名詞解釋：1.算法：算法是指解決問題的一種方法或一個過程。算法是若干指令的有窮序列，滿足性質(zhì)：（1）輸入：有零個或多個外部量作為算法的輸入；（2）輸出：算法產(chǎn)生至少一個量作為輸出；（3）確定性：組成算法的每條指令清晰、無歧義；（4）有限性：算法中每條指令的執(zhí)行次數(shù)有限，執(zhí)行每條指令的時間也有限。2.程序：程序是算法用某種程序設(shè)計語言的具體實現(xiàn)。3.遞歸函數(shù)：用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。4.子問題的重疊性質(zhì)：遞歸算法求解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計算多次，這種性質(zhì)稱為子問題的重疊性質(zhì)。5.隊列式分支限界法：隊列式(FIF

10、O)分支限界法是將活結(jié)點表組織成一個隊列，并按照隊列的先進先出（FIFO）原則選取下一個結(jié)點為擴展結(jié)點。6.多機調(diào)度問題：多機調(diào)度問題要求給出一種作業(yè)調(diào)度方案，使所給的n個作業(yè)在盡可能短的時間內(nèi)由m臺機器加工處理完成。同時約定每個作業(yè)均可在任何一臺機器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。7.最小生成樹：G=(V,E)是無向連通帶權(quán)圖，G的子圖稱為G的生成樹，生成樹上各邊權(quán)的總和稱為該生成樹的耗費，在G的所有生成樹中，耗費最小的生成樹稱為G的最小生成樹。二、簡答題：1.備忘錄方法和動態(tài)規(guī)劃算法相比有何異同？簡述之。備忘錄方法是動態(tài)規(guī)劃算法的變形。與動態(tài)規(guī)劃算法一樣，

11、備忘錄方法用表格保存已解決的子問題的答案，在下次需要解此問題時，只要簡單地查看該子問題的解答，而不必重新計算。備忘錄方法與動態(tài)規(guī)劃算法不同的是，備忘錄方法的遞歸方式是自頂向下的，而動態(tài)規(guī)劃算法則是自底向上遞歸的。因此，備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法為每個解過的子問題建立了備忘錄以備需要時查看，避免了相同的子問題的重復(fù)求解，而直接遞歸方法沒有此功能。2.簡述回溯法解題的主要步驟?；厮莘ń忸}的主要步驟包括：1）針對所給問題，定義問題的解空間；2）確定易于搜索的解空間結(jié)構(gòu)；3）以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。3.簡述動態(tài)規(guī)劃算法求

12、解的基本要素。動態(tài)規(guī)劃算法求解的基本要素包括：1）最優(yōu)子結(jié)構(gòu)是問題能用動態(tài)規(guī)劃算法求解的前提；2）動態(tài)規(guī)劃算法，對每一個子問題只解一次，而后將其解保存在一個表格中，當(dāng)再次需要解此子問題時，只是簡單地用常數(shù)時間查看一下結(jié)果，即重疊子問題。4.簡述回溯法的基本思想。回溯法的基本做法是搜索，在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷該結(jié)點是否包含問題的解。如果肯定不包含，則跳過對該結(jié)點為根的子樹的搜索，逐層向其祖先結(jié)點回溯；否則，進入該子樹，繼續(xù)按深度優(yōu)先策略搜索。5.簡要分析在遞歸算法中消除遞歸調(diào)用，將遞歸算法轉(zhuǎn)化為非遞歸算法的方法。將遞歸

13、算法轉(zhuǎn)化為非遞歸算法的方法主要有：1）采用一個用戶定義的棧來模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強，但本質(zhì)上還是遞歸，只不過人工做了本來由編譯器做的事情，優(yōu)化效果不明顯。2）用遞推來實現(xiàn)遞歸函數(shù)。3）通過Cooper變換、反演變換能將一些遞歸轉(zhuǎn)化為尾遞歸，從而迭代求出結(jié)果。后兩種方法在時空復(fù)雜度上均有較大改善，但其適用范圍有限。6.簡要分析分支限界法與回溯法的異同。1）求解目標(biāo)：回溯法的求解目標(biāo)是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。 2）搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而

14、分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹。7.簡述算法復(fù)雜性的概念，算法復(fù)雜性度量主要指哪兩個方面？算法復(fù)雜性是算法運行所需要的計算機資源的量，需要時間資源的量稱為時間復(fù)雜性，需要的空間資源的量稱為空間復(fù)雜性。這個量應(yīng)該只依賴于算法要解的問題的規(guī)模、算法的輸入和算法本身的函數(shù)。如果分別用N、I和A表示算法要解問題的規(guī)模、算法的輸入和算法本身，而且用C表示復(fù)雜性，那么，應(yīng)該有C=F(N,I,A)。算法復(fù)雜性度量主要包括算法的時間復(fù)雜性和算法的空間復(fù)雜性。8.貪心算法求解的問題主要具有哪些性質(zhì)？簡述之。貪心算法求解的問題一般具有二個重要的性質(zhì)：一是貪心選擇性質(zhì)，這是貪心算法可行的第

15、一個基本要素；另一個是最優(yōu)子結(jié)構(gòu)性質(zhì)，問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用貪心算法求解的關(guān)鍵特征。9.分治法的基本思想是什么？合并排序的基本思想是什么？請分別簡述之。分治法的基本思想：將n個輸入分成k個不同子集合，得到k個不同的可獨立求解的子問題，其中1<kn，而且子問題與原問題性質(zhì)相同，原問題的解可由這些子問題的解合并得出。合并排序基本思想：將待排序元素分成大小大致相同的2個子集合，分別對2個子集合進行排序，最終將排好序的子集合合并成為所要求的排好序的集合。10.簡述分析貪心算法與動態(tài)規(guī)劃算法的異同。貪心算法和動態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是兩類算法的一個共同點。動態(tài)規(guī)劃算法

16、通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。三、算法編寫及算法應(yīng)用分析題：1.已知有3個物品：(w1,w2,w3)=(12,10,6), (p1,p2,p3)=(15,13,10), 背包的容積M=20，根據(jù)0-1背包動態(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)=

17、 maxf1(10)，f1(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可獲得的最大利潤為25，最優(yōu)解為：（1，0，1）2.按要求完成以下關(guān)于排序和查找的問題。（1） 對數(shù)組A=15，29，135，18，32，1，27，25，5，用快速排序方法將其排成遞減序。（2） 請描述遞減數(shù)組進行二分搜索的基本思想，并給出非遞歸算法。（3） 給出上述算法的遞歸算法。（4） 使用上述算法對（1）所得到的結(jié)果搜索如下元素，并給出搜索過程：18，31，135。

18、解：（1）第一步：15 29 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ù)組的中間元素進行比較，如果，則在前半部分元素中搜索v；若，則搜索成功；否則在后半部分?jǐn)?shù)組中搜索v。非遞歸算法：輸入：遞減數(shù)組Aleft:right，待搜索元素v。輸出：v在A中的位置pos，或者不在A中的消息（-1）。步驟：【3分】int BinarySearch(int A,int left,int righ

19、t,int v)int mid;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

20、)/2);if (v=Amid) 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，此時只有一個元素，未找到，返回-1。 搜索135：首先與27比較，135>2

21、7，在前半部分搜索；再次32比較，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的最佳求積順序（要求給出計算步驟）。解：使用動態(tài)規(guī)劃算法進行求解。求解矩陣為：12345610150330405165520102036033024301950301809301770403000186050150060123456101224220222230344404450560因此，最

22、佳乘積序列為（A1A2）（A3A4）（A5A6），共執(zhí)行乘法2010次。4.根據(jù)分枝限界算法基本過程，求解0-1背包問題。已知，n=3，M=20，(w1,w2,w3)=(12,10,6), (p1,p2,p3)=(15,13,10)。解：用x(i)表示第i步選擇的物品號， 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é)點刪除。活節(jié)點表=2,3，取最小代價估值節(jié)點作為擴展節(jié)點：x(2)=2，w1+w2>M，節(jié)點5是不合理節(jié)點；x(2)=3，這是

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

24、nt 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、試用動態(tài)規(guī)劃算法實現(xiàn)下列問題：設(shè)A和B是兩個字符串。我們要用最少的字符操作，將字符串A轉(zhuǎn)換為字符串B，這里所說的字符操作包括：(1)刪除一個字符。(2)插入一個字符。(3)將一個字符改為另一個字符。請寫出該算法。解：此題用動態(tài)規(guī)劃算法求解：int dist( ) int m=a.size( ); i

25、nt 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、對于下圖使用Dijkstra算法求由頂點a到頂點h的最短路徑。解：用V1表示已經(jīng)找到最短路徑的頂點，V2表示與V1中某個頂點相鄰接且不在V1中的頂點；

26、E1表示加入到最短路徑中的邊，E2為與V1中的頂點相鄰接且距離最短的路徑。步驟 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。求所有頂點對之間的最短路徑可以使用Dijkstr

27、a算法，使其起始節(jié)點從a循環(huán)到h，每次求起始節(jié)點到其他節(jié)點的最短路徑，最終可以求得所有頂點對之間的最短路徑。8、試寫出用分治法對數(shù)組An實現(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)

28、int q=partition(a,p,r); Quicksort(a,p,q-1); Quicksort(a,q+1,r); ; Quicksort(a,0,n-1); 9、有n 個活動爭用一個活動室。已知活動i占用的時間區(qū)域為si，f i，活動i,j相容的條件是：sjf i，問題的解表示為(xi| xi =1，2，n,)，xi表示順序為i的活動編號活動，求一個相容的活動子集，且安排的活動數(shù)目最多。解：解決這個問題的基本思路是在安排時應(yīng)該將結(jié)束時間早的活動盡量往前安排，好給后面的活動安排留出更多的空間，從而達到安排最多活動的目標(biāo)。據(jù)此，貪心準(zhǔn)則應(yīng)當(dāng)是：在未安排的活動中挑選結(jié)束時間最早的活動安

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

30、ion);end Greedy10、設(shè)x1、x2、x3是一個三角形的三條邊，而且x1+x2+x3=14。請問有多少種不同的三角形？給出解答過程。解：由于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個可行解：（6，6，2），（6，5，3），（6，4，4，）（5，5，4）。11、設(shè)數(shù)組A有n個元素，需要找出其中的最大最小值。（1） 請給出一個解決方法，并分析其復(fù)雜性。（2） 把n個元素等分為兩組A1和A2，分別求這兩組的最大值

31、和最小值，然后分別將這兩組的最大值和最小值相比較，求出全部元素的最大值和最小值。如果A1和A2中的元素多于兩個，則再用上述方法各分為兩個子集。直至子集中元素至多兩個元素為止。這是什么方法的思想？請給出該方法的算法描述，并分析其復(fù)雜性。解：（1）基本思想：從頭到尾逐個掃描，紀(jì)錄最大和最小元素。輸入：具有n個元素的數(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ù)雜性分析：由

32、于是從頭到尾掃描各個元素，而每個元素都要與max和min比較一遍，從而時間復(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,rig

33、ht,hmax,hmin);max=(gmax<hmax?hmax:gmax);min=(gmin<hmin?gmin:hmin);12、有n個程序和長度為L的磁帶，程序i的長度為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的長度，即每次選入的程序都是當(dāng)前最短的。我們可以將n個程序按a1a2an順序排序，然后從i=1開始依次選擇。算法如下：procedure programming

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

35、i<=m;i+) if(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、試用動態(tài)規(guī)劃算法實現(xiàn)0-1閉包問題，請寫出該算法。解：解答如下：Template<class>void Knapsack(Type v,

36、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-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); Temp

37、late<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=(mnc)?1:0;15、試用貪心算法求解下列問題：將正整數(shù)n分解為若干個互不相同的自然數(shù)之和，使這些自然數(shù)的乘積最大，請寫出該算法。解：解答如下：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; wh

38、ile(n>ak) k+; ak=ak-1+1; n-=ak;if(n= =ak) ak+;n-;for(int i=0;i<n;i+) ak-i+;16、試寫出用分治法對一個有序表實現(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; i

39、f(x= =amiddle) return middle+1; if(x>amiddle) left=middle+1; else right=middle-1;return -1;17、試用動態(tài)規(guī)劃算法實現(xiàn)最長公共子序列問題，請寫出該算法。解：用動態(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<

40、=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) 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è)有

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

42、，8，求子集，要求該子集的元素之和d=9。畫出子集和問題的解空間樹；該樹運用回溯算法，寫出依回溯算法遍歷節(jié)點的順序； 如果S中有n個元素，指定d，用偽代碼描述求解子集和問題的回溯算法。解答：滿足要求的子集有1，2，6， 1，8解空間樹如下：R1P1T1X1V1Ô1Z1Â1U0S0W0Y0Ê0Û0Î0Q0遍歷結(jié)點的順序為：A 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

43、>#define N 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、求解填字游戲問題：在3×3個方格的方陣中要填入數(shù)字1到N（N10）內(nèi)的某9個數(shù)字，每個方格填一個整數(shù)，似的所有相鄰兩個方格內(nèi)的兩個整數(shù)之和為質(zhì)數(shù)。試采用回溯法寫出滿足這個要求的一種數(shù)字填法的算法和滿足這個要求的全部數(shù)字填法的算法。解：為找到一個滿足要求的9個數(shù)的填法，從還未填一個數(shù)開始，按某種順序（如從小到大的順序）每次在當(dāng)前位置填入一個整數(shù)，然后檢查當(dāng)前填入的整數(shù)是否能滿足要求。在滿足要求的情況下，繼續(xù)用同樣的方法為下一方格填入整數(shù)