算法設計與分析習題

1、精選文檔算法設計與分析習題第一章算法引論1、 算法的定義？答：算法是指在解決問題時，按照某種機械步驟一定可以得到問題結果的處理過程。通俗講，算法：就是解決問題的方法或過程。2、 算法的特征？答：1)算法有零個或多個輸入； )算法有一個或多個輸出； 3)確定性 ； )有窮性3、 算法的描述方法有幾種？答：自然語言、圖形、偽代碼、計算機程序設計語言4、 衡量算法的優(yōu)劣從哪幾個方面？答：(1) 算法實現(xiàn)所耗費的時間（時間復雜度）； (2) 算法實現(xiàn)所所耗費的存儲空間（空間復雜度）； (3) 算法應易于理解，易于編碼，易于調試等等。5、 時間復雜度、空間復雜度定義？答：指的是算法在運行過程中所需要的資

2、源（時間、空間）多少。6、時間復雜度計算： i=1； while（i<=n） i=i*2； 答：語句執(zhí)行次數(shù)1次，語句執(zhí)行次數(shù)f(n), 2f(n)<=n,則f(n) <=log2n;算法執(zhí)行時間： T(n)= 2log2n +1時間復雜度：記為O(log2n) ； 7.遞歸算法的特點？答：每個遞歸函數(shù)都必須有非遞歸定義的初值；否則，遞歸函數(shù)無法計算；（遞歸終止條件）遞歸中用較小自變量函數(shù)值來表達較大自變量函數(shù)值；（遞歸方程式）8、算法設計中常用的算法設計策略？答：蠻力法； 倒推法； 循環(huán)與遞歸； 分治法；動態(tài)規(guī)劃法； 貪心法； 回溯法； 分治限界法9、設計算法：遞歸法：漢諾

3、塔問題？兔子序列（上樓梯問題）？整數(shù)劃分問題？蠻力法：百雞百錢問題？倒推法：穿越沙漠問題？ 答：算法如下：（1） 遞歸法l 漢諾塔問題void hanoi(int n, int a, int b, int c) if (n > 0) hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); l 兔子序列（fibonaci數(shù)列 ） 遞歸實現(xiàn)：Int F(int n) if(n<=2) return 1; else return F(n-1)+ F(n-2);l 上樓梯問題Int F(int n) if(n=1) return 1 if(

4、n=2) return 2; else return F(n-1)+ F(n-2);l 整數(shù)劃分問題問題描述：將正整數(shù)n表示成一系列正整數(shù)之和，n=n1+n1+n3+將最大加數(shù)不大于m的劃分個數(shù)，記作q(n,m)。正整數(shù)n的劃分數(shù)p(n)=q(n,n)。 可以建立q(n,m)的如下遞歸關系：遞歸算法：Int q( int n, int m)if(n<1|m<1) return 0;If(n=1)|(m=1) return 1;If (n<m) return q(n,n);If(n=m) return q(n,m-1)+1;else return q(n,m-1)+q(n-m,

5、m);（2） 蠻力法：百雞百錢問題算法設計1：設x，y，z分別為公雞、母雞、小雞的數(shù)量。 約束條件： x+y+z=100 且 5*x+3*y+z/3=100main( ) int x,y,z; for(x=1;x<=20;x=x+1)    for(y=1;y<=34;y=y+1)      for(z=1;z<=100;z=z+1)          if(100=x+y+z and 100=5*x+3*y+z/3)      prin

6、t(the cock number is",x)； print(the hen number is", y)；print(the chick number is "z);算法分析：以上算法需要枚舉嘗試20*34*100=68000次。算法的效率顯然太低 算法設計2： 在公雞（x）、母雞（y）的數(shù)量確定后，小雞 的數(shù)量  z就固定為100-x-y，無需再進行枚舉了 。  此時約束條件只有一個： 5*x+3*y+z/3=100 main( )  int x,y,z;    for(x=1;

7、x<=20;x=x+1)                       for(y=1;y<=33;y=y+1)                    z=100-x-y;

8、0;                     if(z mod 3=0 and 5*x+3*y+z/3=100)                        

9、                       print(the cock number is",x)； print(the hen number is", y)；print(the chick number is "z);         算法分析：以上算法

10、只需要枚舉嘗試20*33=660次。實現(xiàn)時約束條件又限定Z能被3整除時，才會判斷“5*x+3*y+z/3=100”。這樣省去了z不整除3時的算術計算和條件判斷，進一步提高了算法的效率。(3) 倒推法：穿越沙漠問題desert（ ） int dis，k，oil,k; / dis表示距終點的距離，k表示貯油點從后到前的序號 dis=500;k=1;oil=500; /初始化 while ( dis<1000) print(“storepoint”,k,”distance”, 1000-dis,”oilquantity”,oil) /1000- dis則表示距起點的距離， k=k+1; /k表

11、示儲油點從后到前的序號 dis=dis+500/(2*k-1); oil= 500*k; print(“storepoint”,k,”distance”,dis,”oilquantity”,oil)； 第二章 分治算法1、分治算法基本思想是什么？ 適合用分治算法解決的問題，一般具有幾個特征？ 分治算法基本步驟是什么？答：1) 基本思想: 將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。2) 特征：Ø 該問題的規(guī)?？s小到一定的程度就可以容易解決; Ø 該問題可以分解為若干個規(guī)模較小的相同子問題，即該問題具有最優(yōu)子結構性質；Ø 該問題

12、所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。Ø 4)利用該問題分解出子問題解可以合并為該問題解; 3）基本步驟： 分解、求小問題解、合并2、改寫二分查找算法：設a1n是一個已經(jīng)排好序的數(shù)組，改寫二分查找算法:ü 當搜索元素x不在數(shù)組中時，返回小于x的最大元素位置i，和大于x的最小元素位置j； (即返回x的左、右2個元素)ü 當搜索元素x在數(shù)組中時，i和j相同，均為x在數(shù)組中的位置。并計算其時間復雜度？答：、設計一個合并排序的算法？（分治法解） 并計算其時間復雜度？(要求寫出遞推公式，及其求解過程)答：void MergeSort (int A

13、，int low，int high) int middle; if (low<high) middle=(low+high)/2; /取中點 MergeSort(A,low,middle); MergeSort(A,middle+1,high); Merge(A,low,middle,high); /合并算法 void Merge(int A，int low，int middle，int high) /合并過程描述：int i,j,k; int *B=new inthigh-low+1;i=low; j=middle+1; k=low; while(i<=middle&&a

14、mp;j<=high) /兩個子序列非空 if(Ai<=Aj) Bk+=Ai+; else Bk+=Aj+; while (i<=middle) Bk+=Ai+;/子序列Alow，middle非空，將A復制到Bwhile (j<=high) Bk+=Aj+; /子序列Amiddle+1， high非空，將A復制到Bfor(i=low;i<=high;i+) Ai+=Bi+;/將合并后的序列復制回A 合并排序算法運行時間T(n)的遞歸形式為：u 分析該算法時間復雜度：令T(n)為元素個數(shù)為n時所需比較次數(shù)（時間）：當n=時，時間復雜度記為O(1)。當n>時，T

15、(n)=2 T(n/2) + O(n) =2 (2T(n/22)+O(n/2) ) + O(n) =22T(n/22) + 2 O(n) =23T(n/23) + 3O(n) = =2x T(n/2x) + x*O(n)分解到最后只有2個元素可以求解，n/2x1， x=logn; 故 T(n)=n*T(1)+n*logn ，故時間復雜度記為：O（n * logn）、金塊問題（求最大最小元問題）老板有一袋金塊(共n塊)，最優(yōu)秀的雇員得到其中最重的一塊，最差的雇員得到其中最輕的一塊。假設有一臺比較重量的儀器，我們希望用最少的比較次數(shù)找出最重的金塊。要求：）設計一算法求解該問題？ （分治法解） ）計

16、算其時間復雜度？(要求寫出遞推公式，及其求解過程)答：遞歸求取最大和最小元素 maxmin （int i, int j ,float &fmax, float &fmin） int mid; float lmax, lmin, rmax, rmin;if (i=j) fmax= ai; fmin=ai; /只有1個元素 else if (i=j-1) /只有2個元素 if(ai<aj) fmax=aj；fmin=ai; else fmax=ai; fmin=aj;else /多于2個元素 mid=(i+j)/2; maxmin （i，mid，lmax，lmin）;/遞歸調

17、用算法求最大最小 maxmin （mid+1，j，rmax，rmin）;/遞歸調用算法求最大最小 if(lmax>rmax) fmax=lmax; /合并取大 else fmax=rmax; if(lmin>rmin) fmin=rmin; /合并取小 else fmin=lmin; u 分析該算法時間復雜度：令T(n)為元素個數(shù)為n時所需比較次數(shù)（時間）：當n=2時，查找查找最大最小元只需要1次比較，T(2)=1； 時間復雜度記為O(1)。當n>2時， T(n)=2T(n/2) + 2 T(2) =4T(n/4) + 4 T(2) + 2 T(2) =8T(n/8

18、) + 8 4 2 = =2x T(n/2x) + 2x +2x-1+8+4+2分解到最后只有2個元素可以求解，n/2x2， T(n)= 2x *1 + 2x +2x-1 + 22 + 21 = 2x *1 +(2- 2x*2 )/(1-2） = 2x + 2x+1 - 2 =3n/2 - 2故時間復雜度記為：O（n）、用分治思想設計一個有效的算法，可以進行兩個n位大整數(shù)的乘法運算？ 并計算其時間復雜度？（要求寫出遞推公式，及其求解過程） 答： int mult( int x, int y, int n) /x, y為兩個n位整數(shù) s=sign(x)*sign(y); /s為x* y的符號 x

19、=abs(x); y=abs(y); int mul;if( n=1) mul=s*x*y; return mul; else / 計算XY = ac 2n + (a-b)(d-c)+ac+bd) 2n/2 + bd int a=x左邊n/2位； / 移位操作，把X分為2塊 int b=x右邊n/2位； int c=y左邊n/2位； /移位操作，把Y分為2塊 int d=y右邊n/2位； int m1= mult( a, c, n/2); / a, c還不夠小繼續(xù)分為2塊,直到最后1×1位 int m2= mult( a-b, d-c, n/2); int m3= mult( b,

20、d, n/2); mul=s*( m1*2n+(m1+m2+m3)*2n/2+m3 ); return mul; 、設計一棋盤覆蓋問題算法（分治法）？ 并計算其時間復雜度？（要求寫出遞推公式，及其求解過程） 在一個2k×2k 個方格組成的棋盤中，恰有一個方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋。（該算法中可能用到的變量：tr ：棋盤中左上角方格所在行；tc ：棋盤中左上角方格所在列。 dr： 殘缺方塊所在行；dl ：殘缺方塊所在列。s

21、ize:棋盤的行數(shù)或列數(shù)；用二維數(shù)組board ，模擬棋盤。）答：void chessBoard(int tr, int tc, int dr, int dc, int size) if (size = 1) return; /size:棋盤行數(shù) int t = tile+, / L型骨牌號 s = size/2; / 分割棋盤 / 覆蓋左上角子棋盤 if (dr < tr + s && dc < tc + s) / 特殊方格在此棋盤中 chessBoard(tr, tc, dr, dc, s); else / 此棋盤中無特殊方格 boardtr + s - 1tc

22、 + s - 1 = t; / 用 t 號L型骨牌覆蓋右下角 chessBoard(tr, tc, tr+s-1, tc+s-1, s); / 覆蓋其余方格 / 覆蓋右上角子棋盤 if (dr < tr + s && dc >= tc + s) / 特殊方格在此棋盤中 chessBoard(tr, tc+s, dr, dc, s); else / 此棋盤中無特殊方格 boardtr + s - 1tc + s = t; / 用 t 號L型骨牌覆蓋左下角 chessBoard(tr, tc+s, tr+s-1, tc+s, s); / 覆蓋其余方格 / 覆蓋左下角子棋

23、盤 if (dr >= tr + s && dc < tc + s) / 特殊方格在此棋盤中 chessBoard(tr+s, tc, dr, dc, s); else boardtr + stc + s - 1 = t; / 用 t 號L型骨牌覆蓋右上角 chessBoard(tr+s, tc, tr+s, tc+s-1, s); / 覆蓋其余方格 / 覆蓋右下角子棋盤 if (dr >= tr + s && dc >= tc + s) / 特殊方格在此棋盤中 chessBoard(tr+s, tc+s, dr, dc, s); els

24、e boardtr + stc + s = t; / 用 t 號L型骨牌覆蓋左上角 chessBoard(tr+s, tc+s, tr+s, tc+s, s); / 覆蓋其余方格 第三章動態(tài)規(guī)劃算法、動態(tài)規(guī)劃算法基本思想？動態(tài)規(guī)劃算法與分治算法異同點？適合用動態(tài)規(guī)劃算法求解問題的基本要素？動態(tài)規(guī)劃算法的基本步驟？答：1）基本思想：將待求解問題分解成若干個子問題；由于子問題有重疊，動態(tài)規(guī)劃算法能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復計算. 2）相同：都是將原問題分解成小問題，通過小問題求解得到原問題解。不同： ü 用分治法求解時,分解的子問題是互相

25、獨立的,且與原問題類型一致。分治算法實現(xiàn)一般用遞歸；ü 動態(tài)規(guī)劃方法經(jīng)分解得到的子問題往往不是互相獨立的；動態(tài)規(guī)劃算法實現(xiàn)一般用循環(huán); 3）基本要素：具有最優(yōu)子結構；子問題具有重疊性4）步驟：1)分析最優(yōu)解的性質，并刻劃其結構特征。 2)遞推地定義最優(yōu)值。 3)以自底向上的方式計算出最優(yōu)值. 4)根據(jù)計算最優(yōu)值時得到的信息，構造問題的最優(yōu)解. 、序列X=X1，X2,Xm 和 Y=Y1,Y2Yn的最長公共子序列為Z=Z1,Z2,Zk用動態(tài)規(guī)劃的方法求序列 X 和Y的最長公共子序列長度？（要求按照動態(tài)規(guī)劃寫出動態(tài)規(guī)劃求解問題的步驟分析最優(yōu)子結構寫出遞歸方程算法描述） 注：C 記錄序列X與

26、Y的最長公共子序列的長度答：最優(yōu)子結構設序列X= x1，x2，xm 與 序列Y= y1，y2，yn 的一個 最長公共子序列Z= z1，z2，zk 、若xm= yn, 則zk=xm= yn, 且 z1，z2，zk-1 是序列Xm-1與 序列Yn-1 的最長公共自序列；、若xmyn, 且xm zk, 則Z是Xm-1與Y的最長公共子序列；、若xmyn, 且yn zk, 則Z是X與Yn-1的最長公共子序列; 由此可見，2個序列的最長公共子序列包含了這2個序列的前綴（去掉一個元素）的最長公共子序列。 即，原問題最優(yōu)解，包含子問題最優(yōu)解； 因此，最長公共子序列問題具有最優(yōu)子結構性質。 寫出遞歸方程 循環(huán)實

27、現(xiàn)，計算最優(yōu)值C i j，算法描述Int lcsLength( x , y , b ) int m=x.length-1; n=y.length-1; for(int i=1; i<m;i+) Ci0=0; /y序列空 for(int i=1; i<n;i+) C0i=0; /x序列空 for (int i = 1; i <= m; i+) /x序列長為 for (int j = 1; j <= n; j+) /序列長為n if (xi=yj) Cij=Ci-1j-1+1; bij=1; else if (ci-1j>=cij-1) Cij=Ci-1j; bij=

28、2; else Cij=Cij-1; bij=3;return Cmn;u 時間復雜度分析：該算法時間復雜度：O(m*n)構造最長公共子序列，算法描述：void LCS (char X i, Y j, int b ) if (i =0 | j=0) return; if (b i j= 1) LCS( X i-1, Y j-1, b); system.out.print( x i ); else if (b i j= 2) LCS(Xi-1，Y j，b); else if (b i j= 3) LCS(X i ，Yj-1, b);u 時間復雜度分析：此算法每一次遞歸調用使得i或j減，因此該算法

29、時間復雜度為O(m+n)、長江游艇俱樂部在長江上設置了n個游艇出租站1,2n.游客可在這些游艇出租站租用游艇，并在下游的任何一個游艇出租站歸還游艇。游艇出租站i到游艇出租站j之間的租金為r(i，j)，其中1<=i<j<=n；試設計一個算法，計算出游艇從出租站1到出租站n所需最少租金？（見習題集第三章算法設計與計算題T2）4、掌握動態(tài)規(guī)劃方法求解背包問題？ 答：分析問題的最優(yōu)解結構設（y1,y2,yn）所給01背包容量為M的解；則，（y2,yn）相應子問題背包容量為Mw1的解； （即原問題最優(yōu)解，包含了子問題最優(yōu)解） 遞歸定義最優(yōu)值計算最優(yōu)值m(i，j) void knapsa

30、ck( int v , int w , int M, int m )int n=v.length; if ( M<w n ) / i=n時，只有個物品 m n M=0; else if (M>=w n) m n M=v n; M=M-w n; for( int i=n-1; i>=1; i-) / i<n時，xixn多個物品 if (M<w i) m i M=m i+1 M; else if (M>=w n) m i M=math.max( m i+1 M, m i+1M-w i+vi); M=M-w i; u 該算法時間復雜度：O(c*n) c常數(shù)構造最優(yōu)

31、解void trackack( int m , int w , int M, int x )/x i標記i是否放入背包 int n=w.length; for( int i=1; i<n; i+ ) /判斷前n-1個物體是否放入背包 if (m i M=m i+1 M ) x i=0; else x i=1; M=M-w i; x n=(m n M>0)? 1:0 ; /判斷第n個物體是否放入背包 u 該算法時間復雜度：O(n) 第 4 章 貪心算法1、 貪心算法基本思想？答：從問題的初始解出發(fā)逐步逼近給定的目標，每一步都做出當前看來是最優(yōu)的選擇（貪心選擇），最終得到整個問題的最優(yōu)

32、解2、 貪心算法的基本要素？答：貪心選擇性； 最優(yōu)子結構3、 貪心算法與動態(tài)規(guī)劃算法的異同?答：1 ） 相同點：對于要求解的問題都具有最優(yōu)子結構；2 ）不同點： 算法的基本思想不同； 求解問題的類型不同；例：普通背包問題貪心算法求解0-1背包問題動態(tài)規(guī)劃算法求解4、設計普通背包裝載問題的貪心算法? 并分析其時間復雜度？答：float greedy_knapsack ( float M, float w , float p , float x ) / M 背包載重 x 背包問題最優(yōu)解, w 物品重量， P 物品價值 int n=w.length; /n物品的個數(shù) float pp=0; /pp計

33、算當前背包總價值 float mmM; /mm背包剩余載重for( int i=1;i<=n; i+ ) float ww i= p i / w i； /計算物品單位價值ww x i=0; /初始化，所有物品沒有放入背包Mergesort (w i , ww i，n ); /按單位價值將物品排序，便于貪心選擇for( int i=1; i<=n; i+ ) /貪心選擇，總是選擇價值最大放入背包 if ( w i<=mm ) /當前物品小于背包剩余載重 x i=1; mm=mm - w i; pp=pp + p i; /整個放入背包 else x i=mm/w i; pp=pp

34、 + x i*p i; break; /i部分放入背包 return pp;該算法主要包括以下幾部分：Ø 計算物品單位價值時間，其時間復雜度O(n)； Ø 按照物品單位價值排序時間，其時間復雜度為O(n*logn);(合并排序時間)Ø 貪心選擇時間，其時間復雜度為O(n)；故該算法的時間復雜度為：O(n*logn+2n)；記為： O(n*logn)5、設計找零問題的貪心算法? 并分析其時間復雜度？答：void greedy_zhaoling ( float GZ, int B , int S ) /GZ應發(fā)工資 B j初始化排序；/為了貪心選擇，依次選最大幣種 f

35、or( j=1, j<=6;j+) S j=0； /初始化S j A=GZ/B j; /A表示對應j幣種張數(shù) S j=A; /S j存放對應j幣種總張數(shù) GZ=GZ-A*B j; /每求出一種面額所需的張數(shù)后， 一定要把這部分金額減去： for(i=1;i<=6;i+) print( B i, “-”, S i); /輸出幣種和對應張數(shù) 6、設計活動安排問題的貪心算法? 并分析其時間復雜度？答：偽代碼：Int greedyselector(int s , int f , boolean a )int n=s.length; /n活動的個數(shù) ；a 按活動結束時間遞增排序；/便于貪心選

36、擇a1=true; /活動被選中int j=1; /j記錄最近加入活動集合A的活動j int count=1; /count存儲相容活動個數(shù)for(int i=2; i<=n; i+)/貪心選擇從活動j=2n判是否可加入A if( 活動i的開始時間，大于最近活動j的結束時間 )將活動i加入活動集合A； j=i; /活動i作為最近加入活動集合A的最近活動 count+; else 活動i不加入活動集合A；return count;程序設計語言：Int greedyselector(int s , int f , boolean a ) int n=s.length; /n活動的個數(shù) Mer

37、gesort (a ,f , n ); /按活動結束時間排序，便于貪心選擇 a1=true; /活動被選中int j=1; /j記錄最近依次加入活動集合A的活動j int count=1; /count存儲相容活動個數(shù)for(int i=2; i<=n; i+) /貪心選擇從活動i=2n判是否可加入A if( s i>=f j ) a i=true; /將活動i加入活動集合A j=i; /活動i作為最近加入活動集合A的最近活動 count+; else a i=false; / s i<f j, 活動i不加入活動集合Areturn count;該算法主要包括部分：Ø

38、 按照按活動結束時間對活動排序時間，其時間復雜度為：O(n*logn)；Ø 貪心選擇時間，其需要經(jīng)過n-1次的比較（s i>=f j） 時間復雜度為：O(n-1);故本算法的時間復雜度： O(n*lognn-1)；記為： O(n*logn)。7、掌握例dijkstra算法的求單源最短路徑問題。算法設計？求解過程？答:void dijkstra (int v, float a, float dist) /v表示源,aij表示邊i到j的權值 /disti記錄源到頂點i的最短路徑長度/previ記錄頂點i的前一個點,可以找出最短路徑int n=dist.length;boolean

39、s ; /si標記頂點i是否加入頂點集合sif( v<1 | v>n) return; /源點v不存在for(int i=1;i<=n;i+) disti=avi; /初始化數(shù)組disti、si si=false; if(disti=max-value) /源到頂點i沒有邊 previ=0; else previ=v; distv=0; sv=true; /把源v加入到集合s中for(int i=1; i<n; i+)/剩下n-1個頂點，每次選擇一個加入s中float tempmax-value; int u=v; for(int j=1;j<=n;j+) /貪心

40、選擇，計算V-S中頂點的dist 值，選擇最小的那個頂點jif( (!sj) &&(distj<temp) ) u=j; temp=distj; su=true; /源到頂點u的最短路徑已經(jīng)確定，u加入到s中 for(int j=2;j<=n;j+) /根據(jù)u重新計算dist if( (!sj) &&(auj< max-value) /u到j有邊f(xié)loat newdist=distu+auj;if(newdist<distj)distj=newdist; prevj=u;該算法主體有兩重循環(huán)，故該算法的時間復雜度記為O(n2)8、P126

41、圖求最小生成樹，寫出其prim算法？并給出其選邊過程?答：prim算法描述(偽代碼)void prim(int n, float c)/c存儲邊權值 T=空集； /T表示最小生成樹的邊集合 S= 1 ; /S表示最小生成樹包含的頂點集合 while(S!=V) 選擇邊（i，j），iS 且j V-S；且權值cij最??； /貪心選擇 T=T （i，j）; S=S j ； prim算法描述(程序設計語言)Void prim (int n, float c)float lowcost ; float closest ; boolean s ;s1=true; /初始化，頂點1加入生成樹集合s for(

42、int i=2;i<=n;i+) /初始化，計算與頂點1相鄰頂點邊權值 lowcosti=c1i; colsesti=1; si=false; for(int i=1;i<n;i+) /剩下n-1個頂點，每次選擇一個加入s中 float min=float.max-value; int j=1;for( int k=2;k<=n; k+) /貪心選擇,v-s中找使lowcost最小的頂點kif(lowcostk<min)&&(!sk) min=lowcostk; j=k; sj=true; /把找到的頂點j加入到生成樹集合s中for(int k=2;k&

43、lt;=n; k+) /根據(jù)剛加入的頂點修改lowcost, closestif(cjk<lowcosestk)&&(!sk)lowcostk=cjk; closestk=j; 該算法主體有兩重循環(huán)，故該算法的時間復雜度記為O(n2) Prim算法執(zhí)行過程：首先，找出V-S中使lowcost值最小的頂點j(距離s最近的頂點j);然后，根據(jù)數(shù)組closest選取邊(j,closestj)；最后，將j添加到S中，并對closest和lowcost作必要的修改。選邊過程： 9、P126圖，利用kruskal算法求最小生成樹，給出其選邊過程？答：偽代碼：void krustral

44、(int n, float c)/c存儲邊權值 mergesort（float c, T）; /按邊權值排序 T=空集； /T表示最小生成樹的邊集合 while( |T|<n-1 ) /n個頂點有n-1個邊選擇最小權值邊（i，j）； /貪心選擇 if(iT1&&j T2)/邊(i,j)一端i在T1分支,一端j在T分支 union(i,j); T=T（i，j) else T=T（i，j); 選邊過程：第章 回溯算法1、回溯法基本思想？回溯法解題步驟？答：基本思想：在搜索嘗試中找問題的解，當不滿足條件就”回溯”返回，嘗試別的路徑。 解題步驟：(1)針對所給問題，定義問題的解空

45、間； (2)并確定易于搜索的解空間結構(排列樹，子集樹); (3)以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)，剪去無效的枝，避免無效搜索。2、什么叫子集樹？什么叫排列樹？ 什么叫滿m叉樹？答：1）子集樹 ：當所給問題是在n個元素的集合S中找出S滿足某種性質的子集時，其相應的解空間樹稱作子集樹。2）排列樹 ：當所給問題是在確定的n個元素滿足某種性質的排列中搜索問題的解時，相應的解空間樹被稱作排列樹。3）滿m叉樹： 當所給問題的n個元素中每一個元素均有m種選擇，要求確定其中的一種選擇，使得對這n個元素的選擇結果組成的向量滿足某種性質，即尋找滿足某種特性的n個元素取值的一種組合。 這類問題的

46、解空間樹稱為滿m叉樹。 3、利用回溯法，求解01背包問題，要求設計出相應算法？并分析其時間復雜度？答：算法描述（遞歸實現(xiàn)）double knaspack(double p , double w , double c) /c是背包載重 double cw=0; /當前重量 double cp=0; /當前價值 double bestp=0; /當前最優(yōu)裝載價值 backtrack(1); /深度優(yōu)先搜索解空間 return bestp;double backtrack( int i) /搜索解空間函數(shù)double n=p.length; if ( i>n ) / i表示深度（層），i>n搜索到葉子節(jié)點 bestp=cp; return bestp; /否則，進入左子樹向下深度搜索 else if (cw+w i<=c) /當前物品放入背包不超載 cw=cw+w i; cp=cp+p i; c=c-wi; backtrack(i+1); /繼續(xù)向下深度搜索 else /超載，則回溯進入右子樹 if ( bound(i+1)>bestp ) /通過限界函數(shù)知道右子樹可能包含最優(yōu)解/即，當前價值剩余物品價值大于b