算法分析与设计重点课后习题答案

习题13．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和C++描述。//采用分治法//对数组先进行快速排序//在依次比较相邻的差#includeiostreamusingnamespacestd;intpartions(intb[],intlow,inthigh){intprvotkey=b[low];b[0]=b[low];while(lowhigh){while(lowhigh&&b[high]=prvotkey)--high;b[low]=b[high];while(lowhigh&&b[low]=prvotkey)++low;b[high]=b[low];}b[low]=b[0];returnlow;}voidqsort(intl[],intlow,inthigh){intprvotloc;if(lowhigh){prvotloc=partions(l,low,high);//将第一次排序的结果作为枢轴qsort(l,low,prvotloc-1);//递归调用排序由low到prvotloc-1qsort(l,prvotloc+1,high);//递归调用排序由prvotloc+1到high}}voidquicksort(intl[],intn){qsort(l,1,n);//第一个作为枢轴，从第一个排到第n个}intmain(){inta[11]={0,2,32,43,23,45,36,57,14,27,39};intvalue=0;//将最小差的值赋值给valuefor(intb=1;b11;b++)couta[b]'';coutendl;quicksort(a,11);for(inti=0;i!=9;++i){if((a[i+1]-a[i])=(a[i+2]-a[i+1]))value=a[i+1]-a[i];elsevalue=a[i+2]-a[i+1];}coutvalueendl;return0;}4．设数组a[n]中的元素均不相等，设计算法找出a[n]中一个既不是最大也不是最小的元素，并说明最坏情况下的比较次数。要求分别给出伪代码和C++描述。#includeiostreamusingnamespacestd;intmain(){inta[]={1,2,3,6,4,9,0};intmid_value=0;//将“既不是最大也不是最小的元素”的值赋值给它for(inti=0;i!=4;++i){if(a[i+1]a[i]&&a[i+1]a[i+2]){mid_value=a[i+1];coutmid_valueendl;break;}elseif(a[i+1]a[i]&&a[i+1]a[i+2]){mid_value=a[i+1];coutmid_valueendl;break;}}//forreturn0;}5.编写程序，求n至少为多大时，n个“1”组成的整数能被2013整除。#includeiostreamusingnamespacestd;intmain(){doublevalue=0;for(intn=1;n=10000;++n){value=value*10+1;if(value%2013==0){coutn至少为:nendl;break;}}//forreturn0;}习题22．考虑下面的算法，回答下列问题：算法完成什么功能？算法的基本语句是什么？基本语句执行了多少次？算法的时间复杂性是多少？（1）intStery(intn){intS=0;for(inti=1;i=n;i++)S=S+i*i;returnS;}（2）intQ(intn){if(n==1)return1;elsereturnQ(n-1)+2*n-1;}（1）完成的是1-n的平方和基本语句：s+=i*i，执行了n次时间复杂度O（n）（2）（2）完成的是n的平方基本语句：returnQ(n-1)+2*n–1，执行了n次时间复杂度O（n）3.分析以下程序段中基本语句的执行次数是多少，要求列出计算公式。（1）基本语句2*in执行了n/2次基本语句y=y+i*j执行了2/n次一共执行次数=n/2+n/2=O（n）（2）基本语句m+=1执行了(n/2)*n=O(n*n)4.使用扩展递归技术求解下列递推关系式：（1）1)1(314)(nnTnnT（2）1)3(211)(nnnTnnT(1)intT(intn){if(n==1)return4;elseif(n1)return3*T(n-1);}(2)intT(intn){if(n==1)return1;elseif(n1)return2*T(n/3)+n;}习题3（1）for(i=1;i=n;i++)if(2*i=n)for(j=2*i;j=n;j++)y=y+i*j；（2）m=0;for(i=1;i=n;i++)for(j=1;j=2*i;j++)m=m+1;6.设计算法，在数组r[n]中删除所有元素值为x的元素，要求时间复杂性为O(n)，空间复杂性为O(1)。#includeiostreamusingnamespacestd;voiddeletere(inta[],intN){intb[100]={0};inti,k;k=0;staticintj=0;for(i=0;iN;i++)b[a[i]]++;for(i=0;i100;i++){if(b[i]!=0){if(b[i]==2){k++;}a[j]=i;j++;}}for(i=0;iN-k;i++)couta[i]endl;}intmain(){inta[]={1,2,1,3,2,4};deletere(a,6);return0;}8.设表A={a1,a2,…,an}，将A拆成B和C两个表，使A中值大于等于0的元素存入表B，值小于0的元素存入表C，要求表B和C不另外设置存储空间而利用表A的空间。//先对A进行快排//将大于0的元素给B，小于0的元素给C#includeiostreamusingnamespacestd;intpartions(intl[],intlow,inthigh){intprvotkey=l[low];l[0]=l[low];while(lowhigh){while(lowhigh&&l[high]=prvotkey)--high;l[low]=l[high];while(lowhigh&&l[low]=prvotkey)++low;l[high]=l[low];}l[low]=l[0];returnlow;}voidqsort(intl[],intlow,inthigh){intprvotloc;if(lowhigh){prvotloc=partions(l,low,high);//将第一次排序的结果作为枢轴qsort(l,low,prvotloc-1);//递归调用排序由low到prvotloc-1qsort(l,prvotloc+1,high);//递归调用排序由prvotloc+1到high}}voidquicksort(intl[],intn){qsort(l,1,n);//第一个作为枢轴，从第一个排到第n个}intmain(){inta[11]={-2,2,32,43,-23,45,36,-57,14,27,-39};quicksort(a,11);for(inti=1;i11;i++){if(a[i]0)coutC:a[i]'';elsecoutB:a[i]'';}coutendl;return0;}习题44.对于待排序序列(5,3,1,9)，分别画出归并排序和快速排序的递归运行轨迹。归并排序：第一趟：（5,3）（1,9）；第二趟：（3,5,1,9）；第三趟：（1,3,5,9）；快速排序：第一趟：5（,3,1,9）；//5为哨兵，比较9和5第二趟：5（1,3,,9）；//比较1和5，将1挪到相应位置；第三趟：5（1,3,,9）;//比较3和5；第四趟：（1,3,5,9）;5.设计分治算法求一个数组中的最大元素，并分析时间性能。//简单的分治问题//将数组均衡的分为“前”，“后”两部分//分别求出这两部分最大值，然后再比较这两个最大值#includeiostreamusingnamespacestd;externconstintn=6;//声明intmain(){inta[n]={0,6,1,2,3,5};//初始化intmid=n;intnum_max1=0,num_max2=0;for(inti=0;i=n;++i)//前半部分{if(a[i]num_max1)num_max1=a[i];}for(intj=n+1;jn;++j)//后半部分{if(a[j]num_max2)num_max2=a[j];}if(num_max1=num_max2)cout数组中的最大元素：num_max1endl;elsecout数组中的最大元素：num_max2endl;return0;}时间复杂度：O（n）9.在有序序列(r1,r2,…,rn)中，存在序号i（1≤i≤n），使得ri=i。请设计一个分治算法找到这个元素，要求算法在最坏情况下的时间性能为O(log2n)。//在有序数组中//采用二分法查找符合条件的元素#includeiostreamusingnamespacestd;voidFindnum(int*a,intn){intlow=0;inthigh=n-1;while(low=high){intmid=(low+high)/2;if(a[mid]==mid){cout这个数是：a[mid]endl;break;}elseif(a[mid]mid)high=mid-1;elselow=mid+1;}}intmain(){inta[7]={1,0,2,5,6,7,9};Findnum(a,7);return0;}时间复杂度为O(log2n)。10.在一个序列中出现次数最多的元素称为众数。请设计算法寻找众数并分析算法的时间复杂性。//先对序列进行快速排序//再进行一次遍历//输出众数的重复次数#includeiostreamusingnamespacestd;intpartions(intb[],intlow,inthigh){intprvotkey=b[low];b[0]=b[low];while(lowhigh){while(lowhigh&&b[high]=prvotkey)--high;b[low]=b[high];while(lowhigh&&b[low]=prvotkey)++low;b[high]=b[low];}b[low]=b[0];returnlow;}voidqsort(intl[],intlow,inthigh){intprvotloc;if(lowhigh){prvotloc=partions(l,low,high);//将第一次排序的结果作为枢轴qsort(l,low,prvotloc-1);//递归调用排序由low到prvotloc-1qsort(l,prvotloc+1,high);//递归调用排序由prvotloc+1到high}}voidquicksort(intl[],intn){qsort(l,1,n);//第一个作为枢轴，从第一个排到第n个}intmain(){inta[10]={1,2,3,5,3,3,3,2,5,1};inti=0;intcount=0;intmax=0;//max表示出现的次数qsort(a,0,10);while(i10){intj;j=i+1;if(a[i]=a[j]&&i10){count++;i++;}if(count