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

平時作業(yè)1、給定下述二分搜索算法，請判斷算法正確性，指犯錯誤算法產生原因。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;當查找元素在中間元素左邊時，右指針應該為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)要考慮到數組只有一個元素情況所以應該是r>=l;2、O(1)空間子數組環(huán)衛(wèi)算法：設a[0:n-1]是一個n維數組，k（1≤k≤n-1）是一個非負整數。試設計一個算法將子數組a[0:k-1]與a[k+1:n-1]換位。要求算法在最壞情況下耗時O(n)，且只用O(1)輔助空間。答：最簡單方法就是循環(huán)(n-k-1)次，將a數組末尾數字插入到a[0]之前。詳細做法：(1)首先開辟一個額外空間temp用于存放每一次a數組末尾數據。(2)temp<-a[n-1](3)將a[0:n-2]每個數據都依次向后移動一位賦值給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)數量級；空間代價：O（1）3、定義：給定一個自然數n，由n開始依次產生半數集set(n)中元素以下：1）；2）在n左邊加上一個自然數，但該自然數不能超出最近添加數二分之一；3）按此規(guī)則進行處理，直至不能再添加新自然數為止。比如。其中共有6個元素。半數集問題：對于給定n，求半數集set(n)中元素個數。答：半數集set(n)中元素個數求解是個遞歸過程。設set(n)中元素個數為f(n)，則顯然有遞歸表示式：f(n)=1+∑f(i)，i=1,2……n/2。即半數集set(n)元素個數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、設計一個算法，找出由n個數組成序列最長單調遞增子序列長度。答：#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<<"請輸入元素個數"<<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<<"最長單調遞增子序列為："<<endl;LCS(d-1,d-1,x,b);}5、會場安排問題：假設要在足夠多會場里安排一批活動，并希望使用盡可能少會場。設計一個有效貪心算法進行安排。對于給定n個待安排活動，計算使用最少會場個數。每個活動i都有一個開始時間和結束時間，分別表示為b(i)，f(i)。答：#include<iostream>usingnamespacestd;#defineM50//最大活動數structActive{intb;//開始時間intf;//結束時間intno;//預安排會場號}a[M];//兩元素交換位置voidswap(Active&a,Active&b){Activet=a;a=b;b=t;}voidmain(){intk,i,j;cout<<"輸入待安排活動數:"<<endl;cin>>k;cout<<"輸入待安排活動開始時間和結束時間:"<<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;//使用會場數初始化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;//已經安排過活動就不再比較break;}}if(n==i){sum+=1;a[i].no=sum;}}cout<<"輸出最少會場數:\n"<<sum<<endl;system("pause");}6、最優(yōu)分解問題：設n是一個正整數?，F要求將n分解為若干個互不相同自然數和，使得這些自然數乘積最大。設計一個算法，得到最優(yōu)分解方案。分析：我們知道假如a+b=常數，則|a-b|越小，a*b越大。貪心策略：將n分成從2開始連續(xù)自然數和。假如最終剩下一個數，將此數在后項優(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、子集和問題：設是n個正整數集合，c是一個正整數。那么是否存在S一個子集S1，使得子集中元素之和等于c，即。答：#include<stdio.h>intn,c;inta[100];intcurrent[100];//存放當前選擇情況intbest[100];//存放最終選擇子集合，best[i]=1，表示包含，反之即不包含。intd=1;//判斷有沒有滿足情況intd2=0;//是否已經選出子集和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、設序列是序列和最長公共子序列。請說明最長公共子序列具備最優(yōu)子結構性質。設c[i][j]統計序列i和最長公共子序列長度。由最長公共子序列問題最優(yōu)子結構性質建立子問題最優(yōu)值c[i][j]遞歸關系。寫出尋找最長公共子序列算法。答：最長公共子序列問題具備最優(yōu)子結構性質：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最長公共子序列由性質導出子問題遞歸結構：當i=0,j=0時,c[i][j]=0當i,j>0xi=yi時,c[i][j]=c[i-1][j-1]+1當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)計算次序，使得所需數乘次數最少。1、說明矩陣連乘計算次序問題最優(yōu)解包含著其子問題最優(yōu)解，即最優(yōu)子結構性質。2、該問題具備子問題重合性質。3、說明采取動態(tài)規(guī)劃方法能夠處理該問題。4、設計該算法，分析算法復雜性。答：計算A[i:j]最優(yōu)次序所包含計算矩陣子鏈A[i:k]和A[k+1:j]次序也是最優(yōu)。設計算A[i:j]，1≤i≤j≤n，所需要最少數乘次數m[i,j]，則原問題最優(yōu)值為m[1,n]當i=j時，A[i:j]=Ai，無需計算，所以，m[i,j]=0，i=1,2,…,n當i<j時，利用最優(yōu)子結構性質計算m[i,j].設A[i:j]最優(yōu)次序在Ak和Ak＋1之間斷開，則ｍ［ｉ，ｊ］＝ｍ［ｉ，ｋ］＋ｍ［ｋ＋１，ｊ］＋ｐi-1ｐkｐj其中Ai維數為pi-1×pjk位置只有j-i種可能,{i,i+1,…,j-1}，其中使計算量最小那個位置為最優(yōu)解，數乘次數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]對應斷開位置記為s[ij]，則可遞歸由s[ij]結構出對應最優(yōu)解對于1≤i≤j≤n不一樣有序對(i,j)對應于不一樣子問題。所以，不一樣子問題個數最多只有由此可見，在遞歸計算時，許多子問題被重復計算數次。這也是該問題可用動態(tài)規(guī)劃算法求解又一顯著特征。用動態(tài)規(guī)劃算法解此問題，可依據其遞歸式以自底向上方式進行計算。在計算過程中，保留已處理子問題答案。每個子問題只計算一次，而在后面需要時只要簡單查一下，從而防止大量重復計算最終得到多項式時間算法matrixChain已經統計了結構最優(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、考慮分數背包問題，定義以下：給出n個大小為s1,s2,…,sn,價值為v1,v2,…,vn物品，并設背包容量為C,要找到非負實數x1,x2,…,xn,使和在約束下最大。