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

2、間復雜度計算：i=1；while ( i<=n )i=i*2； 答：語句執行次數1次，語句執行次數 f(n), 2Af(n)<=n, 則f(n) <=log2n;算法執行時間： T(n)= 2log2n +1時間復雜度：記為 O(log2n) ；7. 遞歸算法的特點？(遞歸終止條答：每個遞歸函數都必須有非遞歸定義的初值；否則，遞歸函數無法計算;件)遞歸中用較小自變量函數值來表達較大自變量函數值；(遞歸方程式)8、算法設計中常用的算法設計策略？答：蠻力法；倒推法；循環與遞歸；分治法；動態規劃法；貪心法；回溯法；分治限界法9、設計算法：遞歸法：漢諾塔問題？兔子序列(上樓梯問題)？

3、整數劃分問題？蠻力法：百雞百錢問題？倒推法：穿越沙漠問題？答：算法如下：(1) 遞歸法漢諾塔問題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); 兔子序列(fibonaci 數列)遞歸實現：Int F(int n)if(n<=2) return 1;elsereturn F(n-1)+ F(n-2);上樓梯問題Int F(int n)if(n=1) return 1if(n=2) return 2;elsereturn F(n-1)+

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

5、se return q(n,m-1)+q(n-m,m);( 2 ) 蠻力法：百雞百錢問題算法設計 1 ：設 x ， y ， z 分 別為 公雞 、母 雞、 小雞 的數量。 約束條 件： 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) print(the cock number is",x) ；print(the hen number is

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

7、cock number is",x)print(the hen number is", y);print(the chick number is "z);算法分析：以上算法只需要枚舉嘗試20*33=660次。實現時約束條件又限定Z能被3整除時,才會判斷“ 5*x+3*y+z/3=100 ”。這樣省去了 z不整除3時的算術計算和條件判斷，進一步 提高了算法的效率。(3)倒推法：穿越沙漠問題desert () int dis , k, oil,k; 2)相同：都是將原問題分解成小問題，通過小問 題求解得到原問題解。不同：用分治法求解時，分解的子問題是互相獨立的，且與原

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

9、答：最優子結構設序列X= X 1, X2,x m 與序列Y= y i, y2,y n 的一個最長公共子序列 Z= zi, Z2,z k I、若 xm= y n, 則 Zk=xm= y n, 且 z i, Z2, z k-i 是序歹U Xm-i 與序列Yn-i的最長公共自序列；II、若XmWy n,且XmW Z k,則Z是Xm-1與Y的最長公共子序列；出、若XmWy n,且ynW Z k,則Z是X與Yn-1的最長公共子序列；由此可見，2個序列的最長公共子序列包含了這2個序列的前綴(去掉一個元素)的最長公共子序列。即，原問題最優解，包含子問題最優解；因此，最長公共子序列問題具有最優子結構性質。寫出

10、遞歸方程循環實現,計算最優值C i j ,算法描述Int lcsLength( x , y , b) int m=;n=;for(int i=1; i<m;i+)Ci0=0;游客可在這些游艇出租站租用游艇，并在下游的任何一個游艇出租站歸還游艇。游艇出租站i到游艇出租站j之間的租金為r(i , j),其中1<=i<j<=n ;試設計一個算法，計算出游艇從出租站1到出租站n所需最少租金？(見習題集第三章算法設計與計算題T2)4、掌握動態規劃方法求解0 - 1背包問題？答：分析問題的最優解結構設（yi,y2,丫口）所給01背包容量為M的解；則，（y2,丫口）相應子問題背包容量

11、為M- w的解;（即原問題最優解，包含了子問題最優解）遞歸定義最優值計算最優值 m（i ， j） void knapsack( int v , int w , int M, int m )ntValue();ntValue(); ntValue(); ntValue(); /int n=;if ( M<w n )取下一擴展結點i+/ 進入下一層計算上界函數double bound（int i）/ 計算當前價值與剩余價值和double cleft = c - cw; / 剩余容量double b = cp; / 當前物品價值while (i <= n && w i &

12、lt;= cleft) / 剩余物品單位重量價值遞減序裝入物品 cleft = cleft -w i;b= b + pi;i+;/ w i> cleft跳出循環，物品部分裝入背包if (i <= n) b += pi/wi * cleft;return b; / 當前物品價值與剩余物品價值之和時間復雜度分析：計算上界時間為 O（n）;在最壞的情況下，有2n個右孩子節點需要計算上界；故該算法的時間復雜度為 O（n*2 n）5、利用FIFO 分支限界算法, 給出下列 0 1 背包最優裝載的求解步驟？背包載重：Ml= 10;物品重量：w1=6、w2= 5、w3= 5;物品價值：p1 =

13、42、p2 = 25、p3= 30解： 1） 解空間：2）求解過程：第8章NP完全性理論1、什么是易解問題？什么是難解問題？難解問題分為哪兩類？答： 1）易解問題：人們將存在多項式時間 算法的問題稱為易解問題 ;2）難解問題：將需要在指數時間內解決的問題稱為難解問題；3）難解問題有兩類：1 ）不可判定問題 2 ）非決定的難處理問題 。2、什么是不可判定問題？什么是非決定的難處理問題？答： 1）不可判定問題 ：該類問題是不能解問題，它們太難了，以至于根本就不存在能求解它們的任何算法。2 ）非決定的難處理問題： 這類問題是可判定的（即可解的） 。 但是，這類問題即使使用非決定的計算機，也不能在多項式時間內求解它們。3、什么是P類問題？什么是NP完全問題？答： 1） P 類問題：是一類能夠用確定性算法在多項式時間內求解的判斷問題。事實上，所有易解問題都屬于P 類問題。2） NP完全問題：對于某問題，很難找到其多項式時間的算法（或許根本不存在），但是如果給了該問題的一個答案，則可以在多