算法設(shè)計與分析習(xí)題（精編版）

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

2、源（時間、空間）多少。6、時間復(fù)雜度計算： i=1； while（i=n ） i=i*2； 答：語句執(zhí)行次數(shù)1 次，語句執(zhí)行次數(shù)f(n), 2f(n)=n,則 f(n) 0) hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); 兔子序列（ fibonaci數(shù)列）遞歸實(shí)現(xiàn)：int f(int n) if(n=2) return 1; else return f(n-1)+ f(n-2); 上樓梯問題int f(int n) if(n=1) return 1 if(n=2) return 2; else return f(n-1)+ f(n-2

3、); 整數(shù)劃分問題問題描述：將正整數(shù)n 表示成一系列正整數(shù)之和，n=n1+n1+n3+ 將最大加數(shù)不大于m 的劃分個數(shù)，記作q(n,m) 。正整數(shù)n 的劃分?jǐn)?shù)p(n)=q(n,n)。 可以建立 q(n,m) 的如下遞歸關(guān)系：遞歸算法：int q( int n, int m) if(n1|m1) return 0; if(n=1)|(m=1) return 1; if (nm) return q(n,n); if(n=m) return q(n,m-1)+1; else return q(n,m-1)+q(n-m,m); 11,1),()1,()1,(1),(1),(mnmnmnmnmmnqmn

4、qnnqnnqmnq（2）蠻力法：百雞百錢問題算法設(shè)計1：設(shè)x ， y ， z 分 別為 公雞 、母 雞、 小雞 的數(shù)量。約束條件：x+y+z=100 且5*x+3*y+z/3=100 main( ) 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) print(the cock number is,x)； print(the hen number is, y)；print(the chick number is z); 算法分析：以

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

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

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

8、該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；?該問題所分解出的各個子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題。?4)利用該問題分解出子問題解可以合并為該問題解; 3）基本步驟：分解、求小問題解、合并2、改寫二分查找算法：設(shè) a1 n 是一個已經(jīng)排好序的數(shù)組，改寫二分查找算法: ?當(dāng)搜索元素x 不在數(shù)組中時，返回小于x 的最大元素位置i ，和大于 x 的最小元素位置j ； (即返回 x 的左、右2 個元素 ) ?當(dāng)搜索元素x 在數(shù)組中時，i 和 j 相同，均為x 在數(shù)組中的位置。并計算其時間復(fù)雜度？答：、設(shè)計一個合并排序的算法？（分治法解）并計算其時間復(fù)雜度？( 要求寫出遞推公式，及其求解過程) 答：vo

9、id mergesort (int a，int low，int high) int middle; if (lowhigh) middle=(low+high)/2; /取中點(diǎn) 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=

10、middle&j=high) /兩個子序列非空 if(ai=aj) bk+=ai+; else bk+=aj+; while (i=middle) bk+=ai+; / 子序列 alow ，middle 非空，將 a復(fù)制到b while (j=high) bk+=aj+; /子序列 amiddle+1 ， high非空，將 a復(fù)制到b for(i=low;i時， t(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) 分

11、解到最后只有2 個元素可以求解，n/2x1， x=logn; 故 t(n)=n*t(1)+n*logn ，故時間復(fù)雜度記為：o（n * logn）o(1)n=1t(n)=2t(n/2)+o(n)n1、金塊問題（求最大最小元問題）老板有一袋金塊( 共 n 塊)，最優(yōu)秀的雇員得到其中最重的一塊，最差的雇員得到其中最輕的一塊。假設(shè)有一臺比較重量的儀器，我們希望用最少的比較次數(shù)找出最重的金塊。要求：）設(shè)計一算法求解該問題？（分治法解）計算其時間復(fù)雜度？( 要求寫出遞推公式，及其求解過程) 答：遞歸求取最大和最小元素maxmin （int i, int j ,float &fmax, float

12、 &fmin） int mid; float lmax, lmin, rmax, rmin; if (i=j) fmax= ai; fmin=ai; /只有 1 個元素else if (i=j-1) /只有 2 個元素 if(airmax) fmax=lmax; /合并取大 else fmax=rmax; if(lminrmin) fmin=rmin; /合并取小 else fmin=lmin; 分析該算法時間復(fù)雜度：令 t(n) 為元素個數(shù)為n 時所需比較次數(shù)（時間）：當(dāng)n=2時 ，查找查 找 最大 最小元 只 需要1次 比較， t(2)=1；時間復(fù)雜度記為o(1) 。當(dāng) n2 時，

13、 t(n)=2t(n/2) + 2 t(2) =4t(n/4) + 4 t(2) + 2 t(2) =8t(n/8) + 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 故時間復(fù)雜度記為：o （n）、用分治思想設(shè)計一個有效的算法，可以進(jìn)行兩個n 位大整數(shù)的乘法運(yùn)算？并計算其時間復(fù)雜度？（要求寫出遞推公式，及其求解過程）答：int mult( int x, i

14、nt y, int n) /x, y為兩個 n 位整數(shù) s=sign(x)*sign(y); /s為 x* y的符號x=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,

15、c還不夠小繼續(xù)分為2 塊, 直到最后11 位 int m2= mult( a-b, d-c, n/2); int m3= mult( b, d, n/2); mul=s*( m1*2n+(m1+m2+m3)*2n/2+m3 ); return mul; 、設(shè)計一棋盤覆蓋問題算法（分治法）？并計算其時間復(fù)雜度？（要求寫出遞推公式，及其求解過程）在一個 2k2k個方格組成的棋盤中，恰有一個方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4 種不同形態(tài)的l 型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2 個 l 型骨牌不得重疊覆蓋。（該算法

16、中可能用到的變量：tr ：棋盤中左上角方格所在行；tc ：棋盤中左上角方格所在列。dr ： 殘缺方塊所在行；dl ：殘缺方塊所在列。size: 棋盤的行數(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

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

18、tc+s, s); / 覆蓋其余方格 / 覆蓋左下角子棋盤 if (dr = tr + s & dc = tr + s & dc = tc + s) / 特殊方格在此棋盤中 chessboard(tr+s, tc+s, dr, dc, s); else 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ī)劃算法與分治算法異同點(diǎn)？適合用動態(tài)規(guī)劃算法求解問題的基本要素？動態(tài)規(guī)劃算法的基本步驟？答： 1）基本思

19、想： 將待求解問題分解成若干個子問題；由于子問題有重疊，動態(tài)規(guī)劃算法能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復(fù)計算 . 2 ）相同： 都是將原問題分解成小問題，通過小問題求解得到原問題解。不同：?用分治法求解時, 分解的子問題是互相獨(dú)立的, 且與原問題類型一致。分治算法實(shí)現(xiàn)一般用遞歸；?動態(tài)規(guī)劃方法經(jīng)分解得到的子問題往往不是互相獨(dú)立的；動態(tài)規(guī)劃算法實(shí)現(xiàn)一般用循環(huán) ; 3）基本要素 ：具有最優(yōu)子結(jié)構(gòu)；子問題具有重疊性4）步驟： 1) 分析最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。 2)遞推地定義最優(yōu)值。 3)以自底向上的方式計算出最優(yōu)值. 4) 根據(jù)計算最優(yōu)值時得到的信

20、息，構(gòu)造問題的最優(yōu)解. 、序列x=x1，x2, xm 和 y=y1,y2 yn的最長公共子序列為z=z1,z2, zk 用動態(tài)規(guī)劃的方法求序列 x 和 y的最長公共子序列長度？（要求按照動態(tài)規(guī)劃寫出動態(tài)規(guī)劃求解問題的步驟分析最優(yōu)子結(jié)構(gòu)寫出遞歸方程算法描述）注： c 記錄序列x與 y的最長公共子序列的長度答：最優(yōu)子結(jié)構(gòu)設(shè)序列 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

21、-1與 y的最長公共子序列；、若 xmyn, 且 yn zk, 則 z是 x與 yn-1的最長公共子序列; 由此可見， 2 個序列的最長公共子序列包含了這2 個序列的前綴（去掉一個元素）的最長公共子序列。即，原問題最優(yōu)解，包含子問題最優(yōu)解；因此，最長公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。寫出遞歸方程循環(huán)實(shí)現(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; im;i+) ci0=0; /y序列空 for(int i=1; in;i+) c0i=0; /x序列空 for (in

22、t i = 1; i = m; i+) /x序列長為 for (int j = 1; j =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; return cmn; 時間復(fù)雜度分析：該算法時間復(fù)雜度：o(m*n)構(gòu)造最長公共子序列，算法描述：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); e

23、lse if (b i j= 3) lcs(x i ，yj-1, b); 時間復(fù)雜度分析：此算法每一次遞歸調(diào)用使得i 或 j 減，因此該算法時間復(fù)雜度為o(m+n)、長江游艇俱樂部在長江上設(shè)置了n 個游艇出租站1,2 n. 游客可在這些游艇出租站租用游艇，并在下游的任何一個游艇出租站歸還游艇。游艇出租站i 到游艇出租站j 之間的租金為r(i，j) ，其中 1=ij=n ；試設(shè)計一個算法，計算出游艇從出租站1 到出租站n 所需最少租金？（見習(xí)題集第三章算法設(shè)計與計算題t2）4、掌握動態(tài)規(guī)劃方法求解背包問題？答： 分析問題的最優(yōu)解結(jié)構(gòu)設(shè)（ y1,y2, yn）所給 01 背包容量為m的解；則， （

24、y2, yn）相應(yīng)子問題背包容量為m w1的解；（即原問題最優(yōu)解，包含了子問題最優(yōu)解）遞歸定義最優(yōu)值計算最優(yōu)值m(i ，j) void knapsack( int v , int w , int m, int m ) int n=v.length; if ( m=w n) m n m=v n; m=m-w n; for( int i=n-1; i=1; i-) / in時，xixn多個物品 if (m=w n) m i m=math.max( m i+1 m, m i+1m-w i+vi); m=m-w i; 該算法時間復(fù)雜度：o(c*n) c 常數(shù)構(gòu)造最優(yōu)解void trackack( in

25、t m , int w , int m, int x ) /x i標(biāo)記 i 是否放入背包 int n=w.length; for( int i=1; i0)? 1:0 ; /判斷第 n 個物體是否放入背包 該算法時間復(fù)雜度：o(n) 第 4 章 貪心算法1、 貪心算法基本思想？答：從問題的初始解出發(fā)逐步逼近給定的目標(biāo)， 每一步都做出當(dāng)前看來是最優(yōu)的選擇（貪心選擇） ，最終得到整個問題的最優(yōu)解2、 貪心算法的基本要素？答：貪心選擇性；最優(yōu)子結(jié)構(gòu)3、 貪心算法與動態(tài)規(guī)劃算法的異同? 答： 1 ） 相同點(diǎn)：對于要求解的問題都具有最優(yōu)子結(jié)構(gòu)；2 ）不同點(diǎn)：算法的基本思想不同；求解問題的類型不同；例：普

26、通背包問題貪心算法求解0-1 背包問題動態(tài)規(guī)劃算法求解4、設(shè)計普通背包裝載問題的貪心算法? 并分析其時間復(fù)雜度？答：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計算當(dāng)前背包總價值float mm m; /mm背包剩余載重for( int i=1;i=n; i+ ) float ww i= p i / w i； /計算物品單位價值ww x i=0; /初始化，所有物品沒有

27、放入背包mergesort (w i , ww i，n ); /按單位價值將物品排序，便于貪心選擇for( int i=1; i=n; i+ ) /貪心選擇，總是選擇價值最大放入背包 if ( w i=mm ) /當(dāng)前物品小于背包剩余載重 x i=1; mm=mm - w i; pp=pp + p i; /整個放入背包 else x i=mm/w i; pp=pp + x i*p i; break; /i部分放入背包 return pp; 該算法主要包括以下幾部分：?計算物品單位價值時間，其時間復(fù)雜度o(n) ；?按照物品單位價值排序時間，其時間復(fù)雜度為o(n*logn); (合并排序時間)

28、?貪心選擇時間，其時間復(fù)雜度為o(n) ；故該算法的時間復(fù)雜度為：o(n*logn+2n)；記為： o(n*logn) 5、設(shè)計找零問題的貪心算法? 并分析其時間復(fù)雜度？答： void greedy_zhaoling ( float gz, int b , int s ) /gz應(yīng)發(fā)工資 b j初始化排序；/ 為了貪心選擇，依次選最大幣種 for( j=1, j=6;j+) s j=0； /初始化 s j a=gz/b j; /a表示對應(yīng)j 幣種張數(shù) s j=a; /s j存放對應(yīng) j 幣種總張數(shù) gz=gz-a*b j; /每求出一種面額所需的張數(shù)后，一定要把這部分金額減去： for(i=1

29、;i=6;i+) print( b i, “ -”, s i); /輸出幣種和對應(yīng)張數(shù) 6、設(shè)計活動安排問題的貪心算法? 并分析其時間復(fù)雜度？答：偽代碼：int greedyselector(int s , int f , boolean a ) int n=s.length; /n活動的個數(shù)；a 按活動結(jié)束時間遞增排序；/便于貪心選擇a1=true; /活動被選中int j=1; /j 記錄最近加入活動集合a的活動 j int count=1; /count存儲相容活動個數(shù)for(int i=2; i=n; i+)/貪心選擇從活動j=2 n判是否可加入a if( 活動 i 的開始時間，大于最

30、近活動j 的結(jié)束時間 ) 將活動 i 加入活動集合a； j=i; / 活動 i 作為最近加入活動集合a的最近活動 count+; else 活動 i 不加入活動集合a； return count; 程序設(shè)計語言：int greedyselector(int s , int f , boolean a ) int n=s.length; /n活動的個數(shù)mergesort (a ,f , n ); /按活動結(jié)束時間排序，便于貪心選擇a1=true; /活動被選中int j=1; /j 記錄最近依次加入活動集合a的活動 j int count=1; /count存儲相容活動個數(shù)for(int i=2

31、; i=f j ) a i=true; /將活動 i 加入活動集合a j=i; /活動 i 作為最近加入活動集合a的最近活動 count+; else a i=false; / s i=f j）時間復(fù)雜度為：o(n-1); 故本算法的時間復(fù)雜度： o(n*logn n-1) ；記為： o(n*logn)。7、掌握例dijkstra算法的求單源最短路徑問題。算法設(shè)計？求解過程？答: void dijkstra (int v, float a, float dist) /v表示源 ,aij表示邊 i 到 j 的權(quán)值 /disti記錄源到頂點(diǎn)i 的最短路徑長度/previ記錄頂點(diǎn) i 的前一個點(diǎn) ,

32、 可以找出最短路徑int n=dist.length; boolean s ; /si標(biāo)記頂點(diǎn)i 是否加入頂點(diǎn)集合s if( vn) return; /源點(diǎn) v 不存在for(int i=1;i=n;i+) disti=avi; /初始化數(shù)組disti、si si=false; if(disti=max-value) /源到頂點(diǎn)i 沒有邊 previ=0; else previ=v; distv=0; sv=true; /把源 v 加入到集合s 中for(int i=1; in; i+) / 剩下 n-1 個頂點(diǎn)，每次選擇一個加入s 中float tempmax-value; int u=v;

33、 for(int j=1;j=n;j+) / 貪心選擇，計算v-s 中頂點(diǎn)的dist 值，選擇最小的那個頂點(diǎn)j if( (!sj) &(distjtemp) ) u=j; temp=distj; su=true; /源到頂點(diǎn) 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(newdistdistj) distj=newdist; prevj=u; 該算法主體有兩重循環(huán)，故該算法的時間復(fù)雜度

34、記為o(n2) 8、p126 圖求最小生成樹，寫出其prim 算法？并給出其選邊過程? 答：prim 算法描述 (偽代碼 ) void prim(int n, float c)/c存儲邊權(quán)值 t= 空集； /t表示最小生成樹的邊集合 s= 1 ; /s表示最小生成樹包含的頂點(diǎn)集合 while( s!=v ) 選擇邊（i ，j ） ，i s 且 j v-s；且權(quán)值cij最?。?/貪心選擇 t=t （i ，j ）; s=s j ； prim 算法描述 (程序設(shè)計語言) void prim (int n, float c) float lowcost ; float closest ; boolea

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

36、 加入到生成樹集合s 中for(int k=2;k=n; k+) /根據(jù)剛加入的頂點(diǎn)修改lowcost, closest if(cjklowcosestk)&(!sk) lowcostk=cjk; closestk=j; 該算法主體有兩重循環(huán)，故該算法的時間復(fù)雜度記為o(n2) prim 算法執(zhí)行過程：首先，找出v-s 中使 lowcost值最小的頂點(diǎn)j( 距離 s 最近的頂點(diǎn)j); 然后，根據(jù)數(shù)組closest選取邊 (j,closestj) ；最后，將j 添加到 s中，并對closest和 lowcost作必要的修改。選邊過程： 9 、 p126圖，利用kruskal算法求最小生成

37、樹，給出其選邊過程？答： 偽代碼：void krustral(int n, float c)/c存儲邊權(quán)值 mergesort（float c, t）; /按邊權(quán)值排序t=空集； /t表示最小生成樹的邊集合 while( |t|n ) / i表示深度（層） ，in 搜索到葉子節(jié)點(diǎn) bestp=cp; return bestp; /否則，進(jìn)入左子樹向下深度搜索 else if (cw+w ibestp ) /通過限界函數(shù)知道右子樹可能包含最優(yōu)解/ 即，當(dāng)前價值剩余物品價值大于bestp ，進(jìn)入右子樹 backtrack( i+1 ); double bound(int i) / 限界函數(shù)計算當(dāng)前

38、價值與剩余價值和 double cleft = c - cw; / 剩余容量 double b = cp; / 當(dāng)前物品價值 while (i = n & w i cleft 跳出循環(huán)，背包裝滿, 物品部分裝入背包 if (i = n) b += pi/wi * cleft; return b; / 當(dāng)前物品價值與剩余物品價值之和 算法分析：該算法計算上界函數(shù)bound 時間復(fù)雜度為o(n); 在最壞的情況下， 有 2n個右孩子節(jié)點(diǎn)需要計算上界；故該算法的時間復(fù)雜度為o(n*2n) 4、利用回溯法，求解n 后問題，要求設(shè)計出相應(yīng)算法，并分析其時間復(fù)雜度？答：算法描述（遞歸實(shí)現(xiàn)）doub

39、le nqueen(int nn) int n=nn; int sum=0; / 放置皇后的方案數(shù) int x n; / x i表示皇后i 放在棋盤的第i 行，第 x i列 for (int i=0;in ) / 搜索到葉子節(jié)點(diǎn)，方案數(shù)1，t 是層數(shù) sum+; else for( int i=1; i=n; i+) / for循環(huán)一一判斷皇后所在列 x t=i; / 將第 t 個皇后放在t 行(t 不同 ) ，i 列 if( place(t) ) / 約束函數(shù)，判斷是否有沖突backtrack (t+1); / 放下一個皇后 void place( int k) / 約束函數(shù) for( in

40、t j=1;jk; j+ ) /k之前的皇后1k -1 是否與 k 沖突if( (math.abs(k-j)=math.abs(x k-x j) | (x k=x j) ) /k與之前的皇后1k -1 不能在同一斜線或同一列 return false; else return true; 算法分析：對于 n 皇后問題的解空間共有n! 個葉子節(jié)點(diǎn)，故排列樹最多有n* n!個節(jié)點(diǎn)；最壞的情況下每個節(jié)點(diǎn)都要用place 函數(shù)判斷是否可行，每一個節(jié)點(diǎn)判斷時間為o(n) ；故該算法的時間復(fù)雜度記為o(n* n* n!) 第六章 分支限界算法1、分支限界算法的解題步驟？答： 1）針對所給問題，定義問題的解

41、空間; 2）確定易于搜索的解空間結(jié)構(gòu)( 排列樹，子集樹); 3）以廣度優(yōu)先方式搜索問題的解空間；4) 在搜索過程中用限界函數(shù)，剪去無效的枝，避免無效搜索。2、常用的兩種分支限界算法？并說明其思想？答： 1）隊(duì)列式（ fifo 先進(jìn)先出）分支限界算法將活動結(jié)點(diǎn)表組織成一個隊(duì)列，并按照隊(duì)列先進(jìn)先出原則取下一個結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)基本思想：開始，根結(jié)點(diǎn)是唯一的活結(jié)點(diǎn)，根結(jié)點(diǎn)入隊(duì)列；從活結(jié)點(diǎn)隊(duì)中取出根結(jié)點(diǎn)后，作為當(dāng)前擴(kuò)展結(jié)點(diǎn)。對當(dāng)前擴(kuò)展結(jié)點(diǎn)，先從左到右地產(chǎn)生它的所有兒子( 分支 ) ，用約束條件檢查（限界），把所有滿足約束函數(shù)的兒子結(jié)點(diǎn)加入活結(jié)點(diǎn)隊(duì)列中。再從活結(jié)點(diǎn)表中取出隊(duì)首結(jié)點(diǎn)（隊(duì)中最先進(jìn)來的結(jié)點(diǎn)）為當(dāng)

42、前擴(kuò)展結(jié)點(diǎn)， 直到找到一個解或活結(jié)點(diǎn)隊(duì)列為空為止。2）優(yōu)先隊(duì)列式分支限界算法將活結(jié)點(diǎn)表組織成一個優(yōu)先隊(duì)列（堆），并按照優(yōu)先隊(duì)列中規(guī)定的結(jié)點(diǎn)優(yōu)先級，選取優(yōu)先級最高的結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)?；舅枷耄焊Y(jié)點(diǎn)是唯一的活結(jié)點(diǎn)，根結(jié)點(diǎn)入堆；從活結(jié)點(diǎn)隊(duì)中取出根結(jié)點(diǎn)后，作為當(dāng)前擴(kuò)展結(jié)點(diǎn)。對當(dāng)前擴(kuò)展結(jié)點(diǎn)，先從左到右地產(chǎn)生它的所有兒子節(jié)點(diǎn)；用約束條件檢查（限界） ，把所有滿足約束函數(shù)的兒子結(jié)點(diǎn)加入活結(jié)點(diǎn)表中（堆），并給每個結(jié)點(diǎn)設(shè)置優(yōu)先級。再從活結(jié)點(diǎn)表( 堆) 中取出堆頂結(jié)點(diǎn)( 堆中優(yōu)先級最高結(jié)點(diǎn)) 為當(dāng)前擴(kuò)展結(jié)點(diǎn)，直到活結(jié)點(diǎn)表 ( 堆) 為空。3、分支限界算法與回溯法異同？答：相同點(diǎn)：都屬于搜索算法；都需要在問題

43、的解空間中搜索問題的解；不同點(diǎn)：1）求解目標(biāo)不同：回溯法求解目標(biāo)是找出解空間樹中滿足約束條件所有解；分支限界法求解目標(biāo)則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。2）搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹；分支限界法則以廣度優(yōu)先的方式搜索解空間樹。4、 利用優(yōu)先隊(duì)列分支限界算法，設(shè)計0 1背包問題算法？答：隊(duì)列式分支限界算法（無限界函數(shù)）double knaspack(double p , double w , double c) double cw=0; /當(dāng)前重量 double cp=0; /當(dāng)前價值 double bestp=0; /當(dāng)前最

44、優(yōu)裝載價值 backtrack(1); /分支限界法搜索解空間 return bestp; double backtrack( int i) while (true) / 隊(duì)列不空 / 檢查左兒子結(jié)點(diǎn)if (ew + wi = c) enqueue(ew + wi, i); / 左兒子加入隊(duì)列 /進(jìn)入右孩子，右兒子結(jié)點(diǎn)總是可行的，無上界函數(shù) enqueue(ew, i); / 右兒子加入隊(duì)列 ew = (integer) queue.remove().intvalue();/ 取隊(duì)首下一擴(kuò)展結(jié)點(diǎn) if (ew = -1) / 同一層尾部標(biāo)記ew = -1 ：同一層結(jié)點(diǎn)處理結(jié)束 if (queue.isempty() return bestw; / 判斷隊(duì)列是否為空else queue.put(new integer(-1); / 同層結(jié)點(diǎn)尾部標(biāo)志ew = (integer) queue.remove().intvalue(); / 取下一擴(kuò)展結(jié)點(diǎn) i+; / 進(jìn)入下一層 隊(duì)列式分支限界法（帶上界函數(shù)）double knaspack