算法与分析平时作业---答案

平时作业1、给定下述二分搜索算法，请判断算法的正确性，指出错误算法的产生原因。a)intBinarySearch(Typea[],constType&x,intl,intr){while(r=l){intm=(l+r)/2;if(x==a[m])returnm;if(xa[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(xa[m])r=m+1;elsel=m-1;}return-1;}答：错误if(xa[m])r=m+1;当查找的元素在中间元素的左边时，右指针应该为m-1位置，修改成if(xa[m])r=m+1;elsel=m+lc)intBinarySearch(Typea[],constType&x,intl,intr){while(rl){intm=(l+r)/2;if(x==a[m])returnm;if(xa[m])r=m-1;elsel=m+1;}return-1;}答：错误。while(rl)要考虑到数组只有一个元素的情况所以应该是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）()nsetn；2）在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；3）按此规则进行处理，直至不能再添加新的自然数为止。例如(){6,16,26,126,36,136}setn。其中共有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语言代码如下：#includestdio.h#includestdlib.hintmain(){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个数组成的序列的最长单调递增子序列的长度。答：#includeiostream.h#definem10//快速排序voidQuickSort(intR[],ints,intt){inti=s,j=t;inttmp;if(st){tmp=R[s];while(i!=j){while(ji&&R[j]=tmp)j--;R[i]=R[j];while(ij&&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;in;i++){c[0][i]=0;c[i][0]=0;}for(i=0;in;i++)for(j=0;jn;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(i0||j0)return;if(b[i][j]==1){LCS(i-1,j-1,x,b);coutx[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;cind;cout请输入元素endl;for(inti=0;id;i++){cinx[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)。答：#includeiostreamusingnamespacestd;#defineM50//最大活动数structActive{intb;//开始时间intf;//结束时间intno;//预安排会场号}a[M];//两元素交换位置voidswap(Active&a,Active&b){Activet=a;a=b;b=t;}voidmain(){intk,i,j;cout输入待安排活动数:endl;cink;cout输入待安排活动的开始时间和结束时间:endl;//输入活动时间//活动时间排序for(i=1;i=k;i++){{for(j=i;j=k;j++){if(a[i].ba[j].b)swap(a[i],a[j]);if(a[i].b==a[j].b){if(a[i].fa[j].f)swap(a[i],a[j]);}}}intintsum=1;//使用的会场数初始化intn;a[1].no=sum;for(i=2;i=k;i++){for(n=1;ni;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输出最少会场数:\nsumendl;system(pause);}6、最优分解问题：设n是一个正整数。现要求将n分解为若干个互不相同的自然数的和，使得这些自然数的乘积最大。设计一个算法，得到最优分解方案。分析：我们知道如果a+b=常数，则|a-b|越小，a*b越大。贪心策略：将n分成从2开始的连续自然数的和。如果最后剩下一个数，将此数在后项优先的方式下均匀地分给前面各项。答：voiddicomp(intn,int[]a){intk=1;if(n3){a[1]=0;return;}if(n5){a[k]=1;a[++k]=n-1;return;}a[1]=2;n-=2;while(na[k]){k++;a[k]=a[k-1]+1;n-=a[k];}if(n==a[k]){a[k]++;n--;}for(inti=0;in;i++)a[k-i]++;}7、子集和问题：设12{,,,}nSxxx是n个正整数的集合，c是一个正整数。那么是否存在S的一个子集S1，使得子集中元素之和等于c，即1xSxc。答：#includestdio.hintn,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;in;i++){scanf(%d,&a[i]);current[i]=best[i]=0;}Back(0,0);if(d)printf(nosolution\n);for(j=0;jn;j++)//输出满足情况的子集和{if(best[j]==1)printf(%d\t\t,a[j]);}}voidBack(intm,intcount){intk;if(mn)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、设序列12{,,,}kZzzz是序列12{,,,}mXxxx和12{,,,}nYyyy的最长公共子序列。a)请说明最长公共子序列具有最优子结构性质。b)设c[i][j]记录序列12{,,,}iiXxxxi和12{,,,}jjYyyy的最长公共子序列的长度。由最长公共子序列问题的最优子结构性质建立子问题最优值c[i][j]的递归关系。c)写出寻找最长公共子序列的算法。答：最长公共子序列问题具有最优子结构性质：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,j0xi=yi时,c[i][j]=c[i-1][j-1]+1当i,j0xi!=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;in+1;i++){c[0][i]=0;}for(intj=0;jm+1;j++){c[j][0]=0;}}publicLSC(){}publicintLSCL