算法與分析平時作業(yè) - 答案

1、.平時作業(yè)1、給定下述二分搜索算法，請判斷算法的正確性，指出錯誤算法的產(chǎn)生原因。 a) 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 = l) int m = (l+r)/2; if (x = am) return m; if (x am) r = m+1; else l = m-1; return -1; 答：錯誤if (x am) r = m+1; 當查找的元素在中間元素的左邊時，右指針應該為m-1位置，修改成i

2、f (x l) int m = (l+r)/2; if (x = am) return m; if (x l) 要考慮到 數(shù)組只有一個元素的情況 所以應該是 r=l ;2、O(1)空間子數(shù)組環(huán)衛(wèi)算法：設(shè)a0:n-1是一個n維數(shù)組，k（1 k n-1）是一個非負整數(shù)。試設(shè)計一個算法將子數(shù)組a0 : k-1與ak+1 : n-1換位。要求算法在最壞情況下耗時O(n)，且只用O(1)的輔助空間。答：最簡單的方法就是循環(huán)(n-k-1)次，將a數(shù)組的末尾數(shù)字插入到a0之前。具體做法： (1) 首先開辟一個額外空間temp用于存放每一次a數(shù)組的末尾數(shù)據(jù)。 (2) temp - an-1 (3) 將a0:

3、n-2 每個數(shù)據(jù)都依次向后移動一位賦值給a1: n-1。 (4) a0 - temp (5) 循環(huán)執(zhí)行(2) -(4) 步 (n-k+1)次。代價分析： 時間代價 O(n-1)*(n-k+1) 即O(n2)數(shù)量級；空間代價： O（1）3、定義： 給定一個自然數(shù)n，由n開始依次產(chǎn)生半數(shù)集set(n)中的元素如下： 1）； 2）在n的左邊加上一個自然數(shù)，但該自然數(shù)不能超過最近添加的數(shù)的一半； 3）按此規(guī)則進行處理，直至不能再添加新的自然數(shù)為止。 例如 。其中共有6個元素。 半數(shù)集問題：對于給定的n，求半數(shù)集set(n) 中元素的個數(shù)。答：半數(shù)集set(n)中元素個數(shù)的求解是個遞歸的過程。設(shè)set(

4、n)中的元素個數(shù)為f(n)，則顯然有遞歸表達式：f(n)=1+f(i)，i=1,2n/2。即半數(shù)集set(n)元素個數(shù)f(n)=1+f(1)+f(2)+.+f(floor(n/2). 用遞推法求解。C語言代碼如下：#include#includeint main() int n; int i,j,s; int buf106; char *in=input.txt,*out=output.txt; FILE *ip,*op; if(ip=fopen(in,r)=NULL)return 1; if(op=fopen(out,w)=NULL)return 2; fscanf(ip,%d,&n); f

5、close(ip); buf1=1; buf2=2; buf3=2; for(i=4;i*2=n;i+) s=1; for(j=1;j=i/2;j+) s+=bufj; bufi=s; s=1; for(j=1;j=n/2;j+) s+=bufj; fprintf(op,%d,s); fclose(op);/* system(pause);*/ return 0;4、設(shè)計一個算法，找出由n個數(shù)組成的序列的最長單調(diào)遞增子序列的長度。答： #include #define m 10 /快速排序 void QuickSort(int R,int s,int t) int i=s,j=t; int t

6、mp; if(si&Rj=tmp) j-; Ri=Rj; while(ij&Ri=tmp) i+; Rj=Ri; Ri=tmp; QuickSort(R,s,i-1); QuickSort(R,i+1,t); /找出最長公共子序列 void LCSLength(int x,int y,int n,int cmm,int bmm) int i,j; for(i=0;in;i+) c0i=0; ci0=0; for(i=0;in;i+) for(j=0;j=cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; void LCS(int i,int j,in

7、t *x,int bmm) if(i0|j0) return; if(bij=1) LCS(i-1,j-1,x,b); coutxi ; else if(bij=2) LCS(i-1,j,x,b); else LCS(i,j-1,x,b); void main() int xm,ym,d; cout請輸入元素個數(shù)d; cout請輸入元素endl; for(int i=0;ixi; yi=xi; int cmm=0,bmm=0; QuickSort(x,0,d-1); LCSLength(x,y,d,c,b); cout最長單調(diào)遞增子序列為：endl; LCS(d-1,d-1,x,b); 5、會

8、場安排問題：假設(shè)要在足夠多的會場里安排一批活動，并希望使用盡可能少的會場。設(shè)計一個有效的貪心算法進行安排。對于給定的n個待安排的活動，計算使用最少會場的個數(shù)。每個活動i都有一個開始時間和結(jié)束時間，分別表示為b(i)，f(i)。答： #include using namespace std;#define M 50/最大活動數(shù)struct Active int b;/開始時間 int f;/結(jié)束時間int no;/預安排會場號 aM; /兩元素交換位置 void swap(Active &a,Active &b) Active t=a; a=b; b=t; void main() int k,

9、i,j; cout輸入待安排活動數(shù):k; cout輸入待安排活動的開始時間和結(jié)束時間:endl; /輸入活動時間 /活動時間排序for(i=1;i=k;i+) for(j=i;jaj.b) swap(ai,aj);if(ai.b=aj.b)if(ai.faj.f) swap(ai,aj); int int sum=1;/使用的會場數(shù)初始化 int n; a1.no=sum; for(i=2;i=k;i+) for(n=1;ni;n+) if(an.no!=0&an.f=ai.b) ai.no=an.no; an.no=0;/已經(jīng)安排過的活動就不再比較 break; if(n=i) sum+=1

10、; ai.no=sum; cout輸出最少會場數(shù):nsumendl; system(pause); 6、最優(yōu)分解問題：設(shè)n是一個正整數(shù)?，F(xiàn)要求將n分解為若干個互不相同的自然數(shù)的和，使得這些自然數(shù)的乘積最大。設(shè)計一個算法，得到最優(yōu)分解方案。 分析：我們知道如果a+b=常數(shù)，則|a-b|越小，a*b越大。 貪心策略：將n分成從2開始的連續(xù)自然數(shù)的和。如果最后剩下一個數(shù)，將此數(shù)在后項優(yōu)先的方式下均勻地分給前面各項。答： void dicomp(int n, int a) int k = 1; if (n 3) a1 = 0; return; if (n ak) k+; ak = ak - 1 + 1

11、; n -= ak; if (n = ak) ak+; n-; for (int i = 0; i n; i+) ak - i+; 7、子集和問題：設(shè)是n個正整數(shù)的集合，c是一個正整數(shù)。那么是否存在S的一個子集S1，使得子集中元素之和等于c，即。答： #includeint n,c; int a100; int current100; /存放當前選擇的情況 int best100; /存放最后選擇的子集合，besti=1，表示包含，反之即不包含。 int d=1; /判斷有無滿足的情況 int d2=0; /是否已經(jīng)選出子集和 void Back(int m,int count); int m

12、ain() int i,j; scanf(%d %d,&n,&c); for(i=0;in;i+) scanf(%d,&ai); currenti=besti=0; Back(0,0); if(d) printf(no solutionn); for(j=0;jn)return; if(count=c) d=0; /有滿足的子集和 if(d2) return 0; for(k=0;k 0 xi = yi 時 , cij = ci-1j-1 + 1 當 i , j 0 xi != yi 時 , cij = max cij-1 , ci-1j public class LSC private in

13、t c,b; private int m,n; private char A,B; public LSC(char A,char B) this.A=A; this.B=B; m=A.length; n=B.length; c=new intm+1n+1; b=new intm+1n+1; for(int i=0;in+1;i+) c0i=0; for(int j=0;jm+1;j+) cj0=0; public LSC() public int LSCLength() for(int i=1;im+1;i+) for(int j=1;j=cij-1) cij=ci-1j; bij=1; /*

14、 * 情況 */ else cij=cij-1; bij=2; return cmn; public void print(int i,int j) if(i=0|j=0) return; else if(bij=0) print(i-1,j-1); System.out.print(Ai-1); else if(bij=1) print(i-1,j); else print(i,j-1); public int LSCLength2(int i,int j) if(i0|ja2?a1:a2; public static void main(String args) char A=g,f,d,

15、a,s,d,a,c; charB=g,c,f,a,t,0,c,c; LSC lsc=new LSC(A,B); System.out.println(lsc.LSCLength2(7,7); 9、記矩陣連乘積 。 確定計算A1:n的最優(yōu)計算次序，使得所需數(shù)乘的次數(shù)最少。 1、說明矩陣連乘計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解，即最優(yōu)子結(jié)構(gòu)性質(zhì)。 2、該問題具備子問題的重疊性質(zhì)。 3、說明采用動態(tài)規(guī)劃方法可以解決該問題。 4、設(shè)計該算法，分析算法的復雜性。答：計算 Ai:j的最優(yōu)次序所包含的計算矩陣子鏈 Ai:k和 Ak+1:j的次序也是最優(yōu)的。 設(shè)計算 Ai:j，1ijn，所需要的最少數(shù)乘

16、次數(shù) mi,j，則原問 題的最優(yōu)值為 m1,n 當 i=j 時，Ai:j=Ai，無需計算，因此，mi,j=0，i=1,2,n 當 ij 時，利用最優(yōu)子結(jié)構(gòu)性質(zhì)計算 mi,j . 設(shè) Ai:j的最優(yōu)次序在 Ak 和 Ak1 之間斷開，則 ，i-1kj其中 Ai 的維數(shù)為 pi-1pj k 的位置只有 j-i 種可能, i, i+1, , j-1，其中使計算量最小的那個位置 為最優(yōu)解，數(shù)乘次數(shù) mi,j最小值為問題的最優(yōu)值可以遞歸地定義 mi,j為： ，= mini，k + 0k +1, j +i-1kj i=jij 將最優(yōu)值 mi j對應的斷開位置記為 si j，則可遞歸的由 si j構(gòu)造出相應

17、的最優(yōu) 解 對于 1ijn 不同的有序?qū)?i,j)對應于不同的子問題。因此，不同子問題的 個數(shù)最多只有 由此可見，在遞歸計算時，許多子問題被重復計算多次。這也是該問題可用動態(tài) 規(guī)劃算法求解的又一顯著特征。 用動態(tài)規(guī)劃算法解此問題， 可依據(jù)其遞歸式以自底向上的方式進行計算。在計算 過程中，保存已解決的子問題答案。每個子問題只計算一次，而在后面需要時只 要簡單查一下，從而避免大量的重復計算最終得到多項式時間的算法 matrixChain 已經(jīng)記錄了構(gòu)造最優(yōu)解所需的全部信息。從 s1n 可知，計算 A1:n的最優(yōu)加括號方式為 ( A 1 : s1n ) (As1n+1: n ) 計算 A 1 : s

18、1n 的最優(yōu)加括號方式為 (A 1 : s1s1n )(A s1s1n +1 : s1n )10、考慮分數(shù)背包問題，定義如下：給出n 個大小為 s1, s2, , sn , 價值為v1, v2, , vn 的物品， 并設(shè)背包容量為C, 要找到非負實數(shù)x1, x2, , xn, 使和 在約束下最大。寫出求解問題的貪心算法，估計算法的時間復雜性。答：從問題的某一初始解出發(fā)；while 能朝給定總目標前進一步 do 求出可行解的 一個解元素； 由所有解元素組合成問題的一個可行解；從問題的某一個初始解出 發(fā)逐步逼近給定的目標， 以盡可能快的地求得更好的解。當達到某算法中的某一 步不能再繼續(xù)前進時，算法停止。 #include #define t