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

平時作業(yè)1、給定下述二分搜索算法，請判斷算法正確性，指犯錯誤算法產(chǎn)生原因。a)intBinarySearch(Typea[],constType&x,intl,intr){while(r>=l){intm=(l+r)/2;if(x==a[m])returnm;if(x<a[m])r=m-1;elsel=m+1;}return-1;}答：正確b)intBinarySearch(Typea[],constType&x,intl,intr){while(r>=l){intm=(l+r)/2;if(x==a[m])returnm;if(x<a[m])r=m+1;elsel=m-1;}return-1;}答：錯誤if(x<a[m])r=m+1;當(dāng)查找元素在中間元素左邊時，右指針應(yīng)該為m-1位置，修改成if(x<a[m])r=m+1;elsel=m+lc)intBinarySearch(Typea[],constType&x,intl,intr){while(r>l){intm=(l+r)/2;if(x==a[m])returnm;if(x<a[m])r=m-1;elsel=m+1;}return-1;}答：錯誤。while(r>l)要考慮到數(shù)組只有一個元素情況所以應(yīng)該是r>=l;2、O(1)空間子數(shù)組環(huán)衛(wèi)算法：設(shè)a[0:n-1]是一個n維數(shù)組，k（1≤k≤n-1）是一個非負(fù)整數(shù)。試設(shè)計一個算法將子數(shù)組a[0:k-1]與a[k+1:n-1]換位。要求算法在最壞情況下耗時O(n)，且只用O(1)輔助空間。答：最簡單方法就是循環(huán)(n-k-1)次，將a數(shù)組末尾數(shù)字插入到a[0]之前。詳細(xì)做法：(1)首先開辟一個額外空間temp用于存放每一次a數(shù)組末尾數(shù)據(jù)。(2)temp<-a[n-1](3)將a[0:n-2]每個數(shù)據(jù)都依次向后移動一位賦值給a[1:n-1]。(4)a[0]<-temp(5)循環(huán)執(zhí)行(2)-(4)步(n-k+1)次。代價分析：時間代價——O((n-1)*(n-k+1))即O(n^2)數(shù)量級；空間代價：O（1）3、定義：給定一個自然數(shù)n，由n開始依次產(chǎn)生半數(shù)集set(n)中元素以下：1）；2）在n左邊加上一個自然數(shù)，但該自然數(shù)不能超出最近添加數(shù)二分之一；3）按此規(guī)則進(jìn)行處理，直至不能再添加新自然數(shù)為止。比如。其中共有6個元素。半數(shù)集問題：對于給定n，求半數(shù)集set(n)中元素個數(shù)。答：半數(shù)集set(n)中元素個數(shù)求解是個遞歸過程。設(shè)set(n)中元素個數(shù)為f(n)，則顯然有遞歸表示式：f(n)=1+∑f(i)，i=1,2……n/2。即半數(shù)集set(n)元素個數(shù)f(n)=1+f(1)+f(2)+...+f(floor(n/2)).用遞推法求解。C語言代碼以下：#include<stdio.h>#include<stdlib.h>intmain(){intn;inti,j,s;intbuf[106];char*in="input.txt",*out="output.txt";FILE*ip,*op;if((ip=fopen(in,"r"))==NULL)return1;if((op=fopen(out,"w"))==NULL)return2;fscanf(ip,"%d",&n);fclose(ip);buf[1]=1;buf[2]=2;buf[3]=2;for(i=4;i*2<=n;i++){s=1;for(j=1;j<=i/2;j++){s+=buf[j];}buf[i]=s;}s=1;for(j=1;j<=n/2;j++){s+=buf[j];}fprintf(op,"%d",s);fclose(op);/*system("pause");*/return0;}4、設(shè)計一個算法，找出由n個數(shù)組成序列最長單調(diào)遞增子序列長度。答：#include<iostream.h>#definem10//快速排序voidQuickSort(intR[],ints,intt){inti=s,j=t;inttmp;if(s<t){tmp=R[s];while(i!=j){while(j>i&&R[j]>=tmp)j--;R[i]=R[j];while(i<j&&R[i]<=tmp)i++;R[j]=R[i];}R[i]=tmp; QuickSort(R,s,i-1);QuickSort(R,i+1,t);

}}//找出最長公共子序列voidLCSLength(intx[],inty[],intn,intc[m][m],intb[m][m]){inti,j;for(i=0;i<n;i++){c[0][i]=0;c[i][0]=0;}for(i=0;i<n;i++)for(j=0;j<n;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}}voidLCS(inti,intj,int*x,intb[m][m]){if(i<0||j<0)return;if(b[i][j]==1){LCS(i-1,j-1,x,b);cout<<x[i]<<"";}elseif(b[i][j]==2)LCS(i-1,j,x,b);elseLCS(i,j-1,x,b);}voidmain(){intx[m],y[m],d;cout<<"請輸入元素個數(shù)"<<endl;cin>>d;cout<<"請輸入元素"<<endl;for(inti=0;i<d;i++){cin>>x[i];y[i]=x[i];}intc[m][m]={0},b[m][m]={0};QuickSort(x,0,d-1);LCSLength(x,y,d,c,b);cout<<"最長單調(diào)遞增子序列為："<<endl;LCS(d-1,d-1,x,b);}5、會場安排問題：假設(shè)要在足夠多會場里安排一批活動，并希望使用盡可能少會場。設(shè)計一個有效貪心算法進(jìn)行安排。對于給定n個待安排活動，計算使用最少會場個數(shù)。每個活動i都有一個開始時間和結(jié)束時間，分別表示為b(i)，f(i)。答：#include<iostream>usingnamespacestd;#defineM50//最大活動數(shù)structActive{intb;//開始時間intf;//結(jié)束時間intno;//預(yù)安排會場號}a[M];//兩元素交換位置voidswap(Active&a,Active&b){Activet=a;a=b;b=t;}voidmain(){intk,i,j;cout<<"輸入待安排活動數(shù):"<<endl;cin>>k;cout<<"輸入待安排活動開始時間和結(jié)束時間:"<<endl;//輸入活動時間//活動時間排序for(i=1;i<=k;i++){ {for(j=i;j<=k;j++){if(a[i].b>a[j].b)swap(a[i],a[j]);if(a[i].b==a[j].b){

if(a[i].f>a[j].f)swap(a[i],a[j]);}}}intintsum=1;//使用會場數(shù)初始化intn;a[1].no=sum;for(i=2;i<=k;i++){for(n=1;n<i;n++){if(a[n].no!=0&&a[n].f<=a[i].b){a[i].no=a[n].no;a[n].no=0;//已經(jīng)安排過活動就不再比較break;}}if(n==i){sum+=1;a[i].no=sum;}}cout<<"輸出最少會場數(shù):\n"<<sum<<endl;system("pause");}6、最優(yōu)分解問題：設(shè)n是一個正整數(shù)。現(xiàn)要求將n分解為若干個互不相同自然數(shù)和，使得這些自然數(shù)乘積最大。設(shè)計一個算法，得到最優(yōu)分解方案。分析：我們知道假如a+b=常數(shù)，則|a-b|越小，a*b越大。貪心策略：將n分成從2開始連續(xù)自然數(shù)和。假如最終剩下一個數(shù)，將此數(shù)在后項優(yōu)先方式下均勻地分給前面各項。答：voiddicomp(intn,int[]a){intk=1;if(n<3){a[1]=0;return;}if(n<5){a[k]=1;a[++k]=n-1;return;}a[1]=2;n-=2;while(n>a[k]){k++;a[k]=a[k-1]+1;n-=a[k];}if(n==a[k]){a[k]++;n--;}for(inti=0;i<n;i++)a[k-i]++;}7、子集和問題：設(shè)是n個正整數(shù)集合，c是一個正整數(shù)。那么是否存在S一個子集S1，使得子集中元素之和等于c，即。答：#include<stdio.h>intn,c;inta[100];intcurrent[100];//存放當(dāng)前選擇情況intbest[100];//存放最終選擇子集合，best[i]=1，表示包含，反之即不包含。intd=1;//判斷有沒有滿足情況intd2=0;//是否已經(jīng)選出子集和voidBack(intm,intcount);intmain(){inti,j;scanf("%d%d",&n,&c);for(i=0;i<n;i++){scanf("%d",&a[i]);current[i]=best[i]=0;}Back(0,0);if(d)printf("nosolution\n");for(j=0;j<n;j++)//輸出滿足情況子集和{if(best[j]==1)printf("%d\t\t",a[j]);}}voidBack(intm,intcount){intk;if(m>n)return;if(count==c){d=0;//有滿足子集和if(d2)return0;for(k=0;k<=m;k++)best[k]=current[k];d2=1;return0;}else{current[m]=1;//選入子集和count+=a[m];Back(m+1,count);current[m]=0;//不選入子集和count=count-a[m];Back(m+1,count);}}8、設(shè)序列是序列和最長公共子序列。請說明最長公共子序列具備最優(yōu)子結(jié)構(gòu)性質(zhì)。設(shè)c[i][j]統(tǒng)計序列i和最長公共子序列長度。由最長公共子序列問題最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值c[i][j]遞歸關(guān)系。寫出尋找最長公共子序列算法。答：最長公共子序列問題具備最優(yōu)子結(jié)構(gòu)性質(zhì)：1、若xm=yn，則zk=xm=yn，且Z[k-1]是X[m-1]和Y[n-1]最長公共子序列2、若xm!=yn，且zk!=xm,則Z是X[m-1]和Y最長公共子序列3、若xm!=yn,且zk!=yn,則Z是Y[n-1]和X最長公共子序列由性質(zhì)導(dǎo)出子問題遞歸結(jié)構(gòu)：當(dāng)i=0,j=0時,c[i][j]=0當(dāng)i,j>0xi=yi時,c[i][j]=c[i-1][j-1]+1當(dāng)i,j>0xi!=yi時,c[i][j]=max{c[i][j-1],c[i-1][j]}publicclassLSC{privateint[][]c,b;privateintm,n;privatechar[]A,B;publicLSC(char[]A,char[]B){this.A=A;this.B=B;m=A.length;n=B.length;c=newint[m+1][n+1];b=newint[m+1][n+1];for(inti=0;i<n+1;i++){c[0][i]=0;}for(intj=0;j<m+1;j++){c[j][0]=0;}}publicLSC(){}publicintLSCLength(){for(inti=1;i<m+1;i++){for(intj=1;j<n+1;j++){/**假如A[i-1]和Ｂ[j-1]是相等話*/if(A[i-1]==B[j-1]){c[i][j]=c[i-1][j-1]+1;b[i][j]='0';}/**情況１*/elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]='1';}/**情況２*/else{c[i][j]=c[i][j-1];b[i][j]='2';}}}returnc[m][n];}publicvoidprint(inti,intj){if(i<=0||j<=0){return;}elseif(b[i][j]=='0'){print(i-1,j-1);System.out.print(A[i-1]);}elseif(b[i][j]=='1'){print(i-1,j);}else{print(i,j-1);}}

publicintLSCLength2(inti,intj){if(i<0||j<0){return0;}else{if(A[i]==B[j]){return1+LSCLength2(i-1,j-1);}else{inta1=LSCLength2(i,j-1);inta2=LSCLength2(i-1,j);returna1>a2?a1:a2;}}}publicstaticvoidmain(String[]args){char[]A={'g','f','d','a','s','d','a','c'};char[]B={'g','c','f','a','t','0','c','c'};LSClsc=newLSC(A,B);System.out.println(lsc.LSCLength2(7,7));}}9、記矩陣連乘積。確定計算A[1:n]最優(yōu)計算次序，使得所需數(shù)乘次數(shù)最少。1、說明矩陣連乘計算次序問題最優(yōu)解包含著其子問題最優(yōu)解，即最優(yōu)子結(jié)構(gòu)性質(zhì)。2、該問題具備子問題重合性質(zhì)。3、說明采取動態(tài)規(guī)劃方法能夠處理該問題。4、設(shè)計該算法，分析算法復(fù)雜性。答：計算A[i:j]最優(yōu)次序所包含計算矩陣子鏈A[i:k]和A[k+1:j]次序也是最優(yōu)。設(shè)計算A[i:j]，1≤i≤j≤n，所需要最少數(shù)乘次數(shù)m[i,j]，則原問題最優(yōu)值為m[1,n]當(dāng)i=j時，A[i:j]=Ai，無需計算，所以，m[i,j]=0，i=1,2,…,n當(dāng)i<j時，利用最優(yōu)子結(jié)構(gòu)性質(zhì)計算m[i,j].設(shè)A[i:j]最優(yōu)次序在Ak和Ak＋1之間斷開，則ｍ［ｉ，ｊ］＝ｍ［ｉ，ｋ］＋ｍ［ｋ＋１，ｊ］＋ｐi-1ｐkｐj其中Ai維數(shù)為pi-1×pjk位置只有j-i種可能,{i,i+1,…,j-1}，其中使計算量最小那個位置為最優(yōu)解，數(shù)乘次數(shù)m[i,j]最小值為問題最優(yōu)值能夠遞歸地定義m[i,j]為：ｍ［ｉ，ｊ］={min｛ｍ[i，k]+0ｍ[k+1,j]+ｐi-1ｐkｐj｝i=ji<j}將最優(yōu)值m[ij]對應(yīng)斷開位置記為s[ij]，則可遞歸由s[ij]結(jié)構(gòu)出對應(yīng)最優(yōu)解對于1≤i≤j≤n不一樣有序?qū)?i,j)對應(yīng)于不一樣子問題。所以，不一樣子問題個數(shù)最多只有由此可見，在遞歸計算時，許多子問題被重復(fù)計算數(shù)次。這也是該問題可用動態(tài)規(guī)劃算法求解又一顯著特征。用動態(tài)規(guī)劃算法解此問題，可依據(jù)其遞歸式以自底向上方式進(jìn)行計算。在計算過程中，保留已處理子問題答案。每個子問題只計算一次，而在后面需要時只要簡單查一下，從而防止大量重復(fù)計算最終得到多項式時間算法matrixChain已經(jīng)統(tǒng)計了結(jié)構(gòu)最優(yōu)解所需全部信息。從s[1][n]可知，計算A[1:n]最優(yōu)加括號方式為(A[1:s[1][n]])(A[s[1][n]+1:n])計算A[1:s[1][n]]最優(yōu)加括號方式為(A[1:s[1][s[1][n]]])(A[s[1][s[1][n]]+1:s[1][n]])10、考慮分?jǐn)?shù)背包問題，定義以下：給出n個大小為s1,s2,…,sn,價值為v1,v2,…,vn物品，并設(shè)背包容量為C,要找到非負(fù)實(shí)數(shù)x1,x2,…,xn,使和在約束下最大。