湖南大學復習算法分析期末答案大題

1、1.機器調度問題問題描述：現(xiàn)在有n件任務和無限多臺的機器，任務可以在機器上得到 處理。每件任務的開始時間為Si，完成時間為f i，Si65275808555507037V65250808555757046V652505585807570465570758085655022、歸并排序算法對下列實例排序，寫出算法執(zhí)行過程。A=(48,12,61,3,5,19,32,7)解: 48,12,61,35,19,32,748,1261,35,1932,712,483,615,197,323, 12, 48, 615, 7, 19,323,5,7,12, 19,32, 48,61Xk是否合理的過程。3、寫出

2、圖著色問題的回溯算法的判斷解：i 0while i P(i+1)/W(i+1)的順序。CUJ 25,X J 0W1 CU: x1J1; CU JCU-W1=13;W2CU: x3 J CU/ W3=3/8;實例的解為：(1 , 1, 3/8 , 0)11、有一個有序表為1 , 3, 9, 12, 32, 41, 45, 62, 75, 77, 82, 95, 100，當使用 二分查找值為82的結點時，經(jīng)過多少次比較后查找成功并給出過程。解：有一個有序表為1 , 3, 9, 12, 32, 41, 45, 62, 75, 77, 82, 95, 100，當使用二分 查找值為82的結點時，經(jīng)過多少

3、次比較后查找成功并給出過程。一共要要執(zhí)行四次才能找到值為82的數(shù)。12、使用prim算法構造出如下圖 G的一棵最小生成樹。dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5; dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=6 解：使用普里姆算法構造出如下圖G的一棵最小生成樹。dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5;dist(1,3)=1;dist(2,3)=5;dist(3,4)

4、=5;dist(3,6)=4;dist(5,3)=613、有如下函數(shù)說明int f(int x,i nt y)f=x Mod y +1;后，k的值是多少并寫出詳細過程。后，k的值是多少并寫出詳細過程。已知 a=10,b=4,c=5 則執(zhí)行 k=f(f(a+c,b),f(b,c)解：有如下函數(shù)說明int f(int x,i nt y)f=x Mod y +1;已知 a=10,b=4,c=5 則執(zhí)行 k=f(f(a+c,b),f(b,c) K的值是5四、設計算法1.設有n項獨立的作業(yè)1,2,n,由m臺相同的機器加工處理。作業(yè) i所需要的處 理時間為ti。約定：任何一項作業(yè)可在任何一臺機器上處理，但

5、未完工前不準中斷處理；任何作業(yè)不能拆分更小的子作業(yè)。多機調度問題要求給出一種調度方案，使所給的n個作業(yè)在盡可能短的時間內由m臺機器處理完。設計算法，并討論是否可獲最優(yōu)解。解：對于處理機j，用Sj表示處理機j已有的作業(yè)數(shù)，用Pj,k表示處理機j的第k個作業(yè)的序號。1)將作業(yè)按照t1 t2 tn排序2) S1:m清零j - 0設有n種面值為：dl d2 dn的錢幣，需要找零錢M,如何選擇錢幣dk，的數(shù)目兀，滿足diX X +dnX % M ,使得X +最小請選擇貪心策略，并設計貪心算法。解：貪心原則：每次選擇最大面值硬幣。CU-M;i J 1;X J0有 n 個物品，已知 n=7,利潤為 P=(1

6、0,5,15,7,6,18,3) ，重量W=(2,3,5,7,1,4,1)，背包容積 M=15,物品只能選擇全部裝入背包或不裝入背包，設計貪心 算法，并討論是否可獲最優(yōu)解。解：定義結構體數(shù)組G,將物品編號、利潤、重量作為一個結構體：例如Gk=1,10,2求最優(yōu)解，按利潤/重量的遞減序，有5,6,1,6 1,10,2,56,18,4,9/2 3,15,5,3 7,3,1,32,5,3,5/3 4,7,7,1算法procedure KNAPSACK(P、,W MX n)f(n)(g( n)f(n)(g( n)f(n) 2n;g (n)100 n2;f(n)2n;g( n)nnnnn2(3 ) Av

7、A -v A222a b d f e g h2f (n) log n ; g(n) log n 5;3n; log n2 (log n 5) 2n(100n2)1xaX2daxbxcX740 40 30 50 35竺竺 190.6254071,1,/0)404030503060C.4040305010 170d.150 4040303530 -15060105115177.5711,%,0)(1,1,1,1,0,0,1)167.53(1,1,1Q1,0)4e.40405035 30150 130601751何匕,0）f.40405035 1015013035170.714(1,1,0,1,1雋

8、)g.4040 50 30160(1,1,0,1,0,1,0)h.4040 35 30 10 150 140146.8535(1,1,0,0,1,1,|)i.4030 50 35 30167.5(1,0,1,1,12。)1260j.4030 50 35 30 150 145 157.5(0,1,w丄,0)1260在Q處獲得該問題的最優(yōu)解為(1,1,1,1,0,0,1),背包效益為170。即在背包中裝入物品G D、A時達到最大效益，為170，重量為150?！窘Y論2分】已知 Ak(aij(k)r,*r,1，k=1，2，3，4，5，6，r 1=5，2=10,3=3,4=12，r5=5,6=50,7=

9、6，求矩陣鏈積 AX AaX AbX A4X A5X A的最佳求積順序。（要求：給出計算步驟）（20分）答案：使用動態(tài)規(guī)劃算法進行求解。求解矩陣為：【每個矩陣18分】123456101503304051655201020360330243019503018093017704030001860123可5610124220222230p4440445060為（AA2）（ A5A4） （A5A5）,共執(zhí)行乘法2010次?！窘Y論2分】因此，最佳乘積序列50150060五、算法理解題（本題 5分）設有n=2k個運動員要進行循環(huán)賽，現(xiàn)設計一個滿足以下要求的比賽日程表： 每個選手必須與其他 n-1名選手比賽

10、各一次； 每個選手一天至多只能賽一次； 循環(huán)賽要在最短時間內完成。（1）如果n=2k，循環(huán)賽最少需要進行幾天；（2）當n=23=8時，請畫出循環(huán)賽日程表。六、算法設計題（本題 15分）分別用貪心算法、動態(tài)規(guī)劃法、回溯法設計0-1背包問題。要求：說明所使用的算法策略；寫出算法實現(xiàn)的主要步驟；分析算法的時間。七、算法設計題（本題 10分）通過鍵盤輸入一個高精度的正整數(shù)n（n的有效位數(shù)w 240），去掉其中任意s個數(shù)字后，剩下的數(shù)字按原左右次序將組成一個新的正整數(shù)。編程對給定的n和s，尋找一種方案，使得剩下的數(shù)字組成的新數(shù)最小。【樣例輸入】178543S=4【樣例輸出】1 2 3 45 6 7138

11、2 1 4 36 5 873 4 1 27 8 5五、（1） 8天（2分）；6（2）當n-23-8時，循環(huán)賽日程表（3分）。4 3 2 18 7 6六、算法設計題（本題 15分）5(1)貪心算法 0 (nlog (n)5 6 7 8首先計算每種物品單位重量的價值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內的物品 總重量未超過 C,則選擇單位重量價值次高的物品并盡可能多地裝入背包。依此策 略一直地進行下去，直到背包裝滿為止。（2）動態(tài)規(guī)劃法 0（ nc）m（i，j）是背包容量為j，可選擇物品為0-1背包問題的最優(yōu)子結構性質，可以

12、建立計算maxm（i 1, j）, m（i 1, jm（i 1,j）m(i, j)Wi)i+1 ,，n時0-1背包問題的最優(yōu)值。由 m（i，j）Vi0的遞歸式如下。jWij Wiom(n, j)V0Wnj)Wn(3)回溯法 0(2 cw:當前重量cp:void backtrack( int當前價值 bestpi）當前最優(yōu)值1(0n log n 2亦 2nn2 3n log 3 nlog 2 n階的關系:(1) f(n )= O(g( n)(2) f(n)=(g( n)(3) f(n)=(g( n)(4) f(n)= O(g( n)(5) f(n)=(g( n)階最低的函數(shù)是：100階最高的函數(shù)

13、是：3n四.算法設計題（15分）1. 一個旅行者要駕車從 A地到B地，A、B兩地間距離為s。A、B兩地之間有n 個加油站，已知第i個加油站離起點A的距離為di公里， O=dj d2 dn s，車加滿油后可行駛m公里，出發(fā)之前汽車油箱為空。 應如何加油使得從A地到B地沿途加油次數(shù)最少？給出用貪心法求解該最優(yōu) 化問題的貪心選擇策略，寫出求該最優(yōu)化問題的最優(yōu)值和最優(yōu)解的貪心算法， 并分析算法的時間復雜性。算法設計題：1. 貪心選擇策略：從起點的加油站起每次加滿油后不加油行駛盡可能遠，直至油箱中的油耗盡前所能到達的最遠的油站為止，在該油站再加滿油。算法 MINSTOPS輸入：A B兩地間的距離s，A、

14、B兩地間的加油站數(shù) n，車加滿油后可行駛的公里數(shù)m存儲各加油站離起點 A的距離的數(shù)組d1.n。輸出：從A地到B地的最少加油次數(shù) k以及最優(yōu)解x1.k （xi表示第i次加油的加 油站序號），若問題無解，則輸出no solution 。dn+1=s; kMINSTOPS最壞情況下的時間復雜性：E （n）、簡答題：2. 簡述回溯法解題的主要步驟?；厮莘ń忸}的主要步驟包括：1）針對所給問題，定義問題的解空間；2）確定易于搜索的解空間結構；3）以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。3. 簡述動態(tài)規(guī)劃算法求解的基本要素。動態(tài)規(guī)劃算法求解的基本要素包括：1）最優(yōu)子結構是問題能用動態(tài)

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

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

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

18、優(yōu)子結構性質，問題的最優(yōu)子結構性質是該問題可用貪心算法求解的關鍵特征。9. 分治法的基本思想是什么？合并排序的基本思想是什么？請分別簡述之。分治法的基本思想：將 n個輸入分成k個不同子集合，得到 k個不同的可獨立求解的子 問題，其中1 wi 從i=1開始，最后得到fn ( M)f1(1) f1(11)= 0f1(12) f1(20)= p1=15f2(1) f2(9)= 0f2(10) f2(11)= maxf1(10), f1(10 - w2)+p2 =13f2(12) f2(20)= maxf1(12), f1(12- w2)+p2=15f3(20)=maxf2(20), f2(20- w

19、3)+p3 = f2(20- 6)+10=25可獲得的最大利潤為 25,最優(yōu)解為：(1 , 0, 1)2. 按要求完成以下關于排序和查找的問題。(1) 對數(shù)組 A=15, 29, 135, 18, 32, 1 , 27, 25, 5，用快速排序方法將其排成 遞減序。(2) 請描述遞減數(shù)組進行二分搜索的基本思想，并給出非遞歸算法。(3) 給出上述算法的遞歸算法。(4) 使用上述算法對(1)所得到的結果搜索如下元素，并給出搜索過程：18, 31,135。解：(1 )第一步：15 29 135 18 32 1 27 25 5第二步：29 135 18 32 27 25 15 1 5第三步：135 3

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

21、e left=mid+1;return -1;遞歸算法：遞減數(shù)組 Aleft:right，待搜索元素v。v在A中的位置pos，或者不在A中的消息(-1 )。(3) 輸入 輸出 步驟int Bin arySearch(i nt A,i nt left,i nt right,i nt v) int mid;if (leftAmid) retur n Bin arySearch(A,left,mid-1,v);else return Bin arySearch(A,mid+1,right,v); elsereturn -1;(4) 搜索18：首先與27比較，1827,在前半部分搜索；再次 32比較，

22、3129，此時只有一個元素，未找到，返回-1。搜索135:首先與27比較，13527，在前半部分搜索；再次 32比較，13532，在前 半部分搜索；與135比較，相同，返回 0。A ( (k)3.已知Ak(aij)ri*ri1 ，k=1，2，3，4，5，6， n=5，r2=10，3=3，4=12，3=5，6=50，3=6,求矩陣鏈積 AX A2X AsX A4X A5X A的最佳求積順序(要求給出計算步驟) 解：使用動態(tài)規(guī)劃算法進行求解。求解矩陣為：1234561015033040516552010203603302430195030180930177040300018605015006012

23、3456101224220222230344404450560因此，最佳乘積序列為(A1A2) (A3A4)( AA6),共執(zhí)行乘法2010次。4.根據(jù)分枝限界算法基本過程，求解0-1背包問題。已知，n=3,M=2Q(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。解：用x(i)表示第i步選擇的物品號，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=mi n23,25,28=23.由于C(4) = 28U所以節(jié)點4刪除

24、?；罟?jié)點表L=2,3，取最小代價估值節(jié)點2作為擴展節(jié)點：x(2)=2 , w1+w2M節(jié)點5是不合理節(jié)點；x(2)=3，這是答案節(jié)點c(6)=13，即找到了代價為13的解，修改U= 13,由于活節(jié)點表中的節(jié)點3有c(3) = 25,所以節(jié)點3可以刪除。這時L=,算法結束。最優(yōu)解 X=1,3搜索產生的狀態(tài)空間樹如下圖：1X1=223025282015X2=2X2=323155603153X1=1節(jié)點6是答X1=34U=23案節(jié)點5、試用貪心算法求解汽車加油問題：已知一輛汽車加滿油后可行駛n公里，而旅途中有若干個加油站。試設計一個有效算法，指出應在哪些加油站?？考佑停辜佑痛螖?shù)最少，請寫出該算法。

25、解： int greedy(vecterx,int n)int sum=0,k=();for(int j=0;jn)cout ” No solution ” endl;return -1;for(int i=0,s=0;in) sum+;s=xi;return sum;6、 試用動態(tài)規(guī)劃算法實現(xiàn)下列問題：設A和B是兩個字符串。我們要用最少的字符操作, 將字符串A轉換為字符串B,這里所說的字符操作包括：(1) 刪除一個字符。(2) 插入一個字符。(3) 將一個字符改為另一個字符。 請寫出該算法。解：此題用動態(tài)規(guī)劃算法求解：int dist( )int m=( );int n=( ); vecto

26、rd(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;j1?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 的最短路徑。解：用V表示已經(jīng)找到最短路徑的頂點，V2表示與V中某個頂點相鄰接且不在Ei表示加入到最短路徑中的邊,E2為與M中的頂點相鄰接且距離最短的路徑。步驟V 1V2E1E21.abab2.a,bdabbd3.a,b,dc,fab,bddc,df4.a,b

27、,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 結果:從a到h的最短路徑為a b d f e gh，權值為18。求所有頂點對之間的最短路徑可以使用Dijkstra 算法，使其起始節(jié)點從每次求起始節(jié)點到其他節(jié)點的最短路徑，最終可以求得所有頂點對之間的最短路徑。 8、試寫出用分治法對數(shù)組 An實現(xiàn)快速排序的算法。解：用分治法求解的算法代碼如下：int partiti

28、on( float A,i nt p,i nt r)int i=p,j=r+1;float x=ap;while (1) while(a+ix);if(i=j) break;aia j;ap=aj;aj=x;return j;void Quicksort float a, int p, int r )if( p f i,問題的解表示為(xi | Xi =1, 2，n,) , Xi表示順序為i的活動編號活動， 求一個相容的活動子集，且安排的活動數(shù)目最多。解：解決這個問題的基本思路是在安排時應該將結束時間早的活動盡量往前安排，好給 后面的活動安排留出更多的空間，從而達到安排最多活動的目標。據(jù)此，貪

29、心準則應當是： 在未安排的活動中挑選結束時間最早的活動安排。在貪心算法中，將各項活動的開始時間和結束時間分別用兩個數(shù)組s和f存儲，并使得數(shù)組中元素的順序按結束時間非減排列：f1 f2 fn。算法如下：aii 1Xi ,x n) , Xi =0, 1, x i =1，表示程序i存入磁帶,Xi =0 ,表示程序i不存入磁帶，滿? ? ? ?GreedyAction(s,f , n)n足xiaiL ,且存放的程序數(shù)目最多。i 1解：由于目標是存放的程序數(shù)目最多，所以最優(yōu)量度應該是mina i | a i為程序i的長度,即每次選入的程序都是當前最短的。我們可以將n個程序按a1 a2 ww an順序排序

30、，然后從i=1開始依次選擇。算法如下：procedure program min g(L ,n, a, x)begin18、假設有7個物品，它們的重量和價值如下表所示。若這些物品均不能被分割，且背包容 量M= 150,使用回溯方法求解此背包問題，請寫出狀態(tài)空間搜索樹。物品ABCDEFG重量35306050401025價值10403050354030解:按照單位效益從大到小依次排列這7個物品為：FBGDECA將它們的序號分別記為 17。則可生產如下的狀態(tài)空間搜索樹。其中各個節(jié)點處的限界函數(shù)值通過如下方式求得：w,11!,0)b.4040305030150 115601775 (1,1,1,1,0

31、-,0)c.40403050 10 170(1,1,1,1,0,0,1)d.40403035 30150 10560167.53(1 1 1A1,4,0)e.40405035 30150 130175f.40405035 10g.4040 50 30h.40601(1,1A1,130)竺竺170.7135160(1,1,0,1,1,0,40 35 30 10 150 140146.8535(1,1,0,1,0,1,0)(1,1,0,0,1,1,|)i.j.15012540 30 50 35 30167.5 (1,0,1,1,1-,0)6040 30 50 35 30 15 145 157.5(

32、0,1,1,1,1丄,0)12在Q處獲得該問題的最優(yōu)解為(1,1,1,1,0,0,1),背包效益為170。即在背包中裝入物品G D、A時達到最大效益，為 170，重量為150。d=9。19、求解子集和問題：對于集合S=1，2，6，8，求子集，要求該子集的元素之和 畫出子集和問題的解空間樹； 該樹運用回溯算法，寫出依回溯算法遍歷節(jié)點的順序； 如果S中有n個元素，指定d，用偽代碼描述求解子集和問題的回溯算法。 解答：滿足要求的子集有1，2，6，1 ，8解空間樹如下：0ReG N ? ? O遍歷結點的順序為：A B D H P Q I R S E J T U K V W C F L X Y M Z用偽代碼描述算法如下:#in clude #defi ne N 100 int as=0,t=0;int