算法与分析平时作业答案

平时作业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)空间子数组环卫算法：设a[0:n-1]是一个n维数组，k（1≤k≤n-1）是一个非负整数。试设计一个算法将子数组a[0:k-1]与a[k+1:n-1]换位。要求算法在最坏情况下耗时O(n)，且只用O(1)辅助空间。答：最简单方法就是循环(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)循环执行(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）按此规则进行处理，直至不能再添加新自然数为止。比如。其中共有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、最优分解问题：设n是一个正整数。现要求将n分解为若干个互不相同自然数和，使得这些自然数乘积最大。设计一个算法，得到最优分解方案。分析：我们知道假如a+b=常数，则|a-b|越小，a*b越大。贪心策略：将n分成从2开始连续自然数和。假如最终剩下一个数，将此数在后项优先方式下均匀地分给前面各项。答：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、设序列是序列和最长公共子序列。请说明最长公共子序列具备最优子结构性质。设c[i][j]统计序列i和最长公共子序列长度。由最长公共子序列问题最优子结构性质建立子问题最优值c[i][j]递归关系。写出寻找最长公共子序列算法。答：最长公共子序列问题具备最优子结构性质：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]最优计算次序，使得所需数乘次数最少。1、说明矩阵连乘计算次序问题最优解包含着其子问题最优解，即最优子结构性质。2、该问题具备子问题重合性质。3、说明采取动态规划方法能够处理该问题。4、设计该算法，分析算法复杂性。答：计算A[i:j]最优次序所包含计算矩阵子链A[i:k]和A[k+1:j]次序也是最优。设计算A[i:j]，1≤i≤j≤n，所需要最少数乘次数m[i,j]，则原问题最优值为m[1,n]当i=j时，A[i:j]=Ai，无需计算，所以，m[i,j]=0，i=1,2,…,n当i<j时，利用最优子结构性质计算m[i,j].设A[i:j]最优次序在Ak和Ak＋1之间断开，则ｍ［ｉ，ｊ］＝ｍ［ｉ，ｋ］＋ｍ［ｋ＋１，ｊ］＋ｐi-1ｐkｐj其中Ai维数为pi-1×pjk位置只有j-i种可能,{i,i+1,…,j-1}，其中使计算量最小那个位置为最优解，数乘次数m[i,j]最小值为问题最优值能够递归地定义m[i,j]为：ｍ［ｉ，ｊ］={min｛ｍ[i，k]+0ｍ[k+1,j]+ｐi-1ｐkｐj｝i=ji<j}将最优值m[ij]对应断开位置记为s[ij]，则可递归由s[ij]结构出对应最优解对于1≤i≤j≤n不一样有序对(i,j)对应于不一样子问题。所以，不一样子问题个数最多只有由此可见，在递归计算时，许多子问题被重复计算数次。这也是该问题可用动态规划算法求解又一显著特征。用动态规划算法解此问题，可依据其递归式以自底向上方式进行计算。在计算过程中，保留已处理子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而防止大量重复计算最终得到多项式时间算法matrixChain已经统计了结构最优解所需全部信息。从s[1][n]可知，计算A[1:n]最优加括号方式为(A[1:s[1][n]])(A[s[1][n]+1:n])计算A[1:s[1][n]]最优加括号方式为(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,使和在约束下最大。