1、算法設計與分析試題D及答案1 .填空題：(第小題每題4分，共20分)1 .一個算法的優劣通常用 時間復雜度和空間復雜度 來度量。2 .遞歸函數的兩大基本要素是遞歸方程 和 邊界條件。3 .貪心算法和動態規劃算法都要求問題具有共同的性質是最優子結構性質 。4 .實例特征是指_決定問題規模的因素，如輸入數的大小及數據的數量等 。5 .在回溯法中，一個問題的解空間是指一個大的決策可由若干小的決策組成， 所有可能的決策序列 構成該問題的解空間。具有 限界函數 的深度優先生成法稱為回溯法。2 .簡答題：(每題5分，共20分)1 .分支限界法與回溯法的不同主要表現在兩個方面。(1)求解目標：回溯法的求解目

2、標是找出解空間樹中滿足約束條件的所有解，而分支限界 法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意 義下的最優解。(2)搜索方式的不同：回溯法常以深度優先的方式搜索解空間樹，而分支限界法則以廣度 優先或以最小耗費優先的方式搜索解空間樹。2 .給定如下二分搜索算法，請分析算法的復雜性。int BinarySearch(Type a口，const Type& x, int l, int r)while (r >= l)int m = (l+r)/2;if (x = am) return m;if (x < am) r = m-1; else l

3、= m+1;return -1;每執行一次算法的 while循環，待搜索數組的大小減少一半。因此，在最壞情況下，while循環被執行了 O(logn)、次。循環體內運算需要O(1)時間，因此整個算法在最壞情況下的計算時間復雜性為 O(logn)3 .什么是貪心選擇性質和最優子結構性質？當一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構性質。所謂貪心選擇性質是指所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心 選擇來達到。4.動態規劃算法的基本思想是什么？它和分治法有什么區別和聯系？答：動態規劃算法的基本思想為：該方法的思路也是將待求解的大問題分成規模較小的子問題，但所得的

4、各子問題之間有重復子問題，為了避免子問題的重復計算，可依自底向上的方式計算最優值，并根據子問題的最優值合并得到更大問題的最優值，進而可 構造出所求問題的最優解。分 治 法 也是將待求解的大問題分成若干個規模較小的相同子問題，即該問題具有最優子結構性質。規模縮小到一定的程度就可以容易地解決。所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題；利用該問題分解出的子問題的解可以合 并為該問題的解。三算法分析解答題：( (每小題20 分 , 共 60 分) )1 .給定給的n個作業1 , 2, 3,，n,每個作業所需處理的時間是Ti, T2,，Tn.請設計一個算法，給出作業調度方案，使

5、n個作業在盡可能短的時間內由m臺機器加工處理完成。約定，每個作業均可在任何一臺機器上加工處理，但未完工前不允許中斷處理。作業不能拆分成更小的子作業。寫出求解問題的貪心算法。解：這個問題是NP完全問題，到目前為止還沒有有效的解法。對于這一類問題，用貪心選擇策略有時可以設計出較好的近似算法。采用最長處理時間作業優先的貪心選擇策略可以設計出解多機調度問題的較好的近似算法。int Min(int E,m)k=0;min=maxint;for(i=1;i<=m;i+) if Ei< min min=Ei;k=i return k;void treat(int T,int Q, int E,

6、int n, int m)Sort(T, t, n); / h(i)=作業 i 的排序序號, 按需要的處理時間的升序排序。for (int i = 1; i <= m; i+) Ei=0;for (int j = 1; j <=n; i+) Qij = -1; for (int i = 1; i <= n; i+) k=Min(E,m) ;Qkhi = i; / 作業 i 分配給機器k 處理Ek+=Ti; Totalt=0;for (int i = 1; i <= m; i+) if Totalt < Ei Totalt = Ei;/ Totalt= 由m臺機器加

7、工處理完 n個作業所需的時間。2 .給定n種物品和一背包。物品i的重量是wi,其價值為vi ,背包的容量為 C。問應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?請寫出動態規劃算法求解0-1 背 包問題。解答：1）定義最優值設m（i, j）是背包容量為j ,可選擇物品為i , i+1 ,，n時0-1背包問題的最優解的值。由 0-1 背包問題的最優子結構性質，可以建立計算m（i ， j） 的遞歸式如下：m(i,j)maxm(i 1, j),m(i 1, j m(i 1,j)wi) vi cjwii ii (1)0 jwivnjwnm(n,j)0n 0 j nwn(2)2) 計算最優值v

8、oid knapsack(int v , int w , int c, int m )int n=v.length-1;int jMax=min(wn-1,c);/進行(1)式賦值for( int j=0; j<=jMax; j+) mnj=0;for( int j=wn; j<=c; j+) mnj=vn;/進行(2)式賦值for( int i=n-1; i>1; i-) /當0<=j<wn/ j 為背包容量/當 wn <= j ， m(n,j) 賦值jMax=min(wi-1,c);for( int j=0; j<=jMax; j+) mij=mi

9、+1j;for(int j=wi; j<=c; j+)/當0<=j<wi/當 wi <= j <= cmij=max(mi+1j, mi+1j-wi+vi);m1c=m2c;/當0<=j<w1if (c>=w1)/當w1 <= jm1c=max(m1c, m2c-w1+v1);3) 根據最優值計算最優解void traceback( int m , int w , int c, int x ) int n=w.length-1;for(int i=1; i<n; i+)if (mic=mi+1c) xi=0;else xi=1; c-=wi; xn=(mnc>0)? 1:0;/物品 i 沒有被選擇33 .設有n件工作分配給n個人。將工作i分配給j個人所需的費用為 Cj .現要求為每 個人都分配1件不同的工作，并使總費用達到最小。1）畫出該問題的解空間樹;2）設計回溯算法求解該問題解答：1）該問題的解空間樹是一棵排列樹，4件工作分配給4個人的排列樹如下:2)參考代碼如下：Void backtrack(int t)if ( t>n ) Compute。；elsefor (int j=t; j<=n; j+)swap(rt,rj);backtrack(t