算法设计与分析习题与实验题(12.18)

《算法设计与分析》习题第一章引论习题1-1写一个通用方法用于判定给定数组是否已排好序。解答：Algorithmcompare(a,n)BeginJ=1;While(jnanda[j]=a[j+1])doj=j+1;Ifj=nthenreturntrueElseWhile(jnanda[j]=a[j+1])doj=j+1;Ifj=nthenreturntrueelsereturnfalseendifEndifend习题1-2写一个算法交换两个变量的值不使用第三个变量。解答：x=x+y;y=x-y;x=x-y;习题1-3已知m,n为自然数，其上限为k（由键盘输入，1=k=109）,找出满足条件(n2-mn-m2)2=1且使n2+m2达到最大的m、n。解答：m:=k;flag:=0;repeatn:=m;repeatl:=n*n-m*n-m*n;if(l*l=1)thenflag:=1elsen:=n-1;until(flag=1)or(n=0)ifn=0thenm:=m-1until(flag=1)or(m=0);第二章基础知识习题2-1求下列函数的渐进表达式：3n2+10n;n2/10+2n;21+1/n;logn3;10log3n。解答：3n2+10n=O（n2），n2/10+2n=O（2n），21+1/n=O（1），logn3=O（logn），10log3n=O（n）。习题2-2说明O(1)和O(2)的区别。习题2-3照渐进阶从低到高的顺序排列以下表达式：!n，3/22,2,20,3,log,4nnnnn。解答：照渐进阶从低到高的顺序为：!n、3n、24n、23n、20n、logn、2习题2-4（1）假设某算法在输入规模为n时的计算时间为nnT23)(。在某台计算机上实现并完成该算法的时间为t秒。现有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？（2）若上述算法的计算时间改进为2)(nnT，其余条件不变，则在新机器上用t秒时间能解输入规模多大的问题？（3）若上述算法的计算时间进一步改进为8)(nT,其余条件不变，那么在新机器上用t秒时间能解输入规模多大的问题？解答：（1）设新机器用同一算法在t秒内能解输入规模为1n的问题。因此有64/23231nnt，解得61nn。（2）nnnn8641221。（3）由于)(nT常数，因此算法可解任意规模的问题。习题2-5XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC公司同类产品的100倍。对于计算复杂性分别为n，2n，3n和!n的各算法，若用ABC公司的计算机能在1小时内能解输入规模为n的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题？解答：nn100。nnnn1010022。nnnn64.4100100333。64.6100log!100!nnnnn。习题2-6对于下列各组函数)(nf和)(ng，确定))(()(ngOnf或))(()(ngnf或))(()(ngnf，并简述理由。（1）5log)(;log)(2nngnnf。（2）nngnnf)(;log)(2。（3）nngnnf2log)(;)(。（4）nngnnnnflog)(;log)(。（5）10log)(;10)(ngnf。（6）nngnnflog)(;log)(2。（7）2100)(;2)(nngnfn。（8）nnngnf3)(;2)(。解答：（1）)5(loglog2nn。（2）)(log2nOn。（3）)(log2nn。（4）)(loglognnnn。（5）)10(log10。（6）)(loglog2nn。（7）)100(22nn。（8）)3(2nnO。习题2-7证明：如果一个算法在平均情况下的计算时间复杂性为))((nf，则该算法在最坏情况下所需的计算时间为))((nf。证明：)(),()(),(),(max)(),()()(max**NTINTIPINTINTIPINTIPNTNNNNDIDIDIDIavg因此，))(()))((())(()(maxnfnfNTNTavg。习题2-7求解下列递归方程:s0=0sn=2sn-1+2n-1解答：步骤:1应用零化子化为齐次方程，2解此齐次方程的特征方程，3由特征根构造一般解，4再由初始条件确定待定系数，得到解为：习题2-8求解下列递归方程:01122844nnnhhhhh解hn=2n+1(n+1)第三章递归与分治策略习题3-1下面的7个算法都是解决二分搜索问题的算法。请判断这7个算法的正确性。如果算法不正确，请说明产生错误的原因。如果算法正确，请给出算(1)21nnsn法的正确性证明。publicstaticintbinarySearch1(int[]a,intx,intn){intleft=0;intright=n-1;while(left=right){intmiddle=(left+right)/2;if(x==a[middle])returnmiddle;if(xa[middle])left=middle;elseright=middle;return-1;}publicstaticintbinarySearch2(int[]a,intx,intn){intleft=0;intright=n-1;while(leftright-1){intmiddle=(left+right)/2;if(xa[middle])right=middle;elseleft=middle;}if(x==a[left])returnleft;elsereturn-1}publicstaticintbinarySearch3(int[]a,intx,intn){intleft=0;intright=n-1;while(left+1!=right){intmiddle=(left+right)/2;if(x=a[middle])left=middle;elseright=middle;}if(x==a[left])returnleft;elsereturn-1;}publicstaticintbinarySearch4(int[]a,intx,intn){if(n0&&x=a[0]){intleft=0;intright=n-1;while(leftright){intmiddle=(left+right)/2;if(xa[middle])right=middle-1;elseleft=middle;}if(x==a[left])returnleft;}return-1;}publicstaticintbinarySearch5(int[]a,intx,intn){if(n0&&x=a[0]){intleft=0;intright=n-1;while(leftright){intmiddle=(left+right+1)/2;if(xa[middle])right=middle-1;elseleft=middle;}if(x==a[left])returnleft;}return-1;}publicstaticintbinarySearch6(int[]a,intx,intn){if(n0&&x=a[0]){intleft=0;intright=n-1;while(leftright){intmiddle=(left+right+1)/2;if(xa[middle])right=middle–1;elseleft=middle+1;}if(x==a[left])returnleft;}return-1;}publicstaticintbinarySearch7(int[]a,intx,intn){if(n0&&x=a[0]){intleft=0;intright=n-1;while(leftright){intmiddle=(left+right+1)/2;if(xa[middle])right=middle;elseleft=middle;}if(x==a[left])returnleft;}return-1;}分析与解答：算法binarySearch1数组段左右游标left和right的调整不正确，导致陷入死循环。算法binarySearch2数组段左右游标left和right的调整不正确，导致当x=a[n-1]时返回错误。算法binarySearch3数组段左右游标left和right的调整不正确，导致当x=a[n-1]时返回错误。算法binarySearch4数组段左右游标left和right的调整不正确，导致陷入死循环。算法binarySearch5正确，且当数组中有重复元素时，返回满足条件的最右元素。算法binarySearch6数组段左右游标left和right的调整不正确，导致当x=a[n-1]时返回错误。算法binarySearch7数组段左右游标left和right的调整不正确，导致当x=a[n-1]时陷入死循环。习题3-2设]1:0[na是已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。分析与解答：改写二分搜索算法如下：publicstaticbooleanbinarySearch(int[]a,intx,intleft,intright,int[]ind){intmiddle;while(left=right){middle=(left+right)/2;if(x==a[middle]){ind[0]=ind[1]=middle;returntrue;}if(xa[middle])left=middle+1;elseright=middle-1;}ind[0]=right;ind[1]=left;returnfalse;}返回的ind[1]是小于x的最大元素位置，ind[0]是大于x的最小元素的位置。习题3-3设]1:0[na是有n个元素的数组，)11(nkk是非负整数。试设计一个算法讲子数组]1:0[ka与]1:[nka换位。要求算法在最坏情况下耗时为)(nO，且只用到)1(O的辅助空间。分析与解答：算法：三次求反法Algorithmexchange(a,k,n);BeginInverse(n,0,k-1);inverse(n,k,n-1)；inverse（n,0,n-1）End.Algorithminverse(a,i,j);Beginh=12ji;Fork=0toh-1doBeginx=a[i+k];a[i+k]=a[j-k];a[j-k]=xend;end习题3-4如果在合并排序算法的分割步中，讲数组]1:0[na划分为n个子数组，每个子数组中有)(nO个元素。然后递归地对分割后的子数组进行排序，最后将所得到的n个排好序的子数组合并成所要求的排好序的数组]1:0[na。设计一个实现上述策略的合并排序算法，并分析算法的计算复杂性。分析与解答：实现上述策略的合并排序算法如下：publicstaticvoidmergesort(int[]a,intleft,intright){if(leftright){intj=(int)Math.sqrt(right–left+1);if(j1){for(inti=0;ij;i++)mergesort(a,left+i*j,left+(i+1)*j-1);mergesort(a,left+i*j,right);}mergeall(a,left,right);}}其