离散课后作业答案

1.1算法：是对特定问题求解步骤的一种描述，是指令的有限序列。程序：当一个算法用某种程序设计语言来描述时，得到的就是程序，也就是说,程序是用某种程序设计语言对算法的具体实现.算法有输入、输出、确定性、能行性和有限性等特征，当不具备有穷性时，只能叫做计算过程，而不能称之为算法，算法可以终止，而程序没有此限制。1.2程序证明和程序测试的目的各是什么？程序证明是确认一个算法能正确无误的工作.程序测试的目的是发现错误1-9解:n!的递归定义：011)!1(*{!nnnnn求解n!的递归函数longFactorial(longn){if(n0){cout”error!”;exit(0);}if(n==0)return1;elsereturnn*Factorial(n-1);}1-10使用归纳法，证明上题所设计的计算n！的递归函数的正确性证明(归纳法证明)：(1)首先，如果n=0，那么程序执行if(n==0)return1;返回1,算法显然正确;(2)假定函数Factorial对nk(1)能正确运行，那么，当n=k时，算法必定执行:elsereturnk*Factorial(k-1);因为Factorial(k-1)正确，所以，当n=k时，程序运行正确综合以上两点，可得程序正确.证毕.2-1,简述衡量一个算法的主要性能标准,说明算法的正确性与健壮性的关系答:衡量一个算法的主要性能指标有:正确性，简单性，高效低存储，最优性算法的正确性与健壮性的关系:所谓算法的正确性:是指在合法的输入下，算法应实现预先规定的功能和计算精度要求;所谓算法的健壮性，是指当输入不合法时，算法应该能按某种预定的方式做出适当的处理;正确的算法不一定的是健壮的，健壮的算法也不一定是完全正确的.正确性和健壮性是相互补充的.一个可靠的算法，要求能在正常情况下正确的工作，而在异常情况下，亦能做出适当处理.2-9(1)设计一个C/C++程序，实现一个n*m的矩阵转置，原矩阵与其转置矩阵保存在二维数组中.Voidreverse(int**a,int**b,intn,intm){For(inti=0;in;i++)For(intj=0;jm;j++)b[j][i]=a[i][j];}(2)使用全局变量count,改写矩阵转置程序，并运行修改后的程序以确定此程序所需的程序步Voidreverse(int**a,int**b,intn,intm,int&count){inti=0;count++;intj=0;count++;For(;in;i++)For(;jm;j++){count++;b[j][i]=a[i][j];count++;}}2-10试用定义证明下列等式的正确性（1）当1n时，225825nnn，所以，可选5c，01n。对于0nn，22()5825fnnnn，所以，22582()nnn。（2）当8n时，2222582524nnnnn，所以，可选4c，08n。对于0nn，22()5824fnnnn，所以，22582()nnn。（3）由（1）、（2）可知，取14c，25c，08n，当0nn时，有22212582cnnncn，所以22582()nnn。2-11.(1)当3n时，3loglognnn，所以()20log21fnnnn，3()log2gnnnn。可选212c，03n。对于0nn，()()fncgn，即()(())fngn。注意：是f(n)和g(n)的关系。（2）当4n时，2loglognnn，所以22()/logfnnnn，22()loggnnnn。可选1c，04n。对于0nn，2()()fnncgn，即()(())fngn。（3）因为loglog(log)()(log)nnfnnn，()/loglog2ngnnnn。当4n时，log(log)()nfnnn，()log2ngnnn。所以，可选1c，04n，对于0nn，()()fncgn，即()(())fngn2-16使用递推关系式计算求n!的递归函数的时间(即分析1-9题中的函数的时间复杂度),要求使用替换和迭代两种方法分别计算之.解:分析1-9题中的函数的时间复杂度:用基本运算乘法的运算次数作为衡量时间复杂度的量当n=0时，程序执行if(n==0)return1;,并没有做乘法，故T(0)=0;当n=1时程序执行n*Factorial(n-1);此时T(n)=T(n-1)+1故:0011)1({)(nnnTnT替换法:T(0)=0,T(1)=1,T(2)=2-----总结得到:T(n)=n;归纳法证明:(1),当n=0时,T(0)=0,结论成立;(2)假设当kn时，有T(k)=k,那么，当k=n时，有T(n)=T(n-1)+1=(n-1)+1=n所以，对所有n=0有T(n)=n;成立.迭代法:T(n)=T(n-1)+1=(T(n-2)+1)+1=((T(n-3)+1)+1)+1=....=T(0)+1+1......+1(n个1)=n2-19利用递归树计算递推方程2)2/(2)(nnTnT2)1(T假设n=2k,那么,总共有logn+1(即k+1)层,非递归部分之和为n2+n2/21+n2/22+…+n2/2k=(1+1/2+1/22+1/23+…+1/2logn)n2=2n2=O(n2)5-4.SolutionTypeDandC1(intleft,intright){while(!Small(left,right)&&leftright){intm=Divide(left,right);if(xP(m)right=m-1;elseif(xP[m])left=m+1;elsereturnS(P)}}5-7.templateclassTintSortableListT::BSearch(constT&x,intleft,intright)const{if(left=right){intm=left+(right-left+1)/3;if(xl[m])returnBSearch(x,left,m-1);elseif(xl[m])returnBSearch(x,m+1,right);elsereturnm;}return-1;}5-8三分搜索算法的做法是:它先将待查元素X与n/3处的元素比较，然后将X与2n/3处的元素比较,比较的结果或者找到X,或者将范围缩小到原来的n/3intSearch3(inta[],intleft,intright,intx)/*递归算法*/{intl,u;if(left=right){l=left+(right-left+1)/3;u=left+(right-left+1)*2/3;if(x==a[u])returnu;elseif(x==a[l])returnl;elseif(xa[u])returnSearch3(a,u+1,right,x);elseif(xa[l])returnSearch3(a,l+1,u-1,x);elsereturnSearch3(a,left,l-1,x);}return-1;}voidmain(){intn,*a;intx,i;coutPleaseinputn:;cinn;a=newint[n];//动态数组intlocation=-1;for(i=0;in;i++){a[i]=i+1;}coutPleaseinputthesearchx:;cinx;coutendlSearch3(a,0,n-1,x)endl;}voidmain()/*非递归算法*/{inta[15];intx,i;intlocation=-1;for(i=0;i15;i++){a[i]=i+1;}cinx;i=0;intj=14,l,u;while(i=j){l=i+(j-i)/3;u=i+(j-i)*2/3;if(x==a[u]){location=u;break;}elseif(x==a[l]){location=l;break;}elseif(xa[u])i=u+1;elseif(xa[l])j=l-1;else{i=l+1;j=u-1;}}coutlocationendl;//x的位置}5-12Voidstoogesort(nta[],intleft,intright){if(a[left]a[right])swap(a,left,right);if(left+1=right)return;intk=(right-left+1)/3;stoogesort(a,left,right-k);stoogesort(a,left+k,right);stoogesort(a,left,right-k);}证明:元素个数n=right-left+1;(1)若为空表或只有一个元素(n=1时,即left+1==right)时，程序执行if(a[left]a[right])swap(a,left,right);之后，执行if(left+1=right)return;即此时程序做了一次元素之间的比较之后，不做任何操作，显然正确.(2)假设当nright-left+1(n=2)时，算法正确，即对于所有元素个数小于n的元素集,算法能正确排序.那么,当n=right-left+1时，算法执行程序段:intk=(right-left+1)/3;stoogesort(a,left,right-k);//序列的前2/3的子序列有序stoogesort(a,left+k,right);//使序列的后2/3的子序列有序，经过这两次递归排序，使原序列的后1/3的位置上是整个序列中较大的数，即序列后1/3的位置上数均大于前2/3的数，但此时，前2/3的序列并不一定是有序的。stoogesort(a,left,right-k);//使序列的前2/3有序经过三次递归，最终使序列有序，所以，当n=right-left+1时,算法正确.由以上两点可知，算法正确.分析算法的时间复杂度:排序算法，基本运算仍然是元素之间的比较,最坏情况发生在序列按递减次序排列所以，算法时间复杂度为:010，21，2313nn。设322in，则log1log31ni。2431331139nnn49319n122333313iiiin31322ii31322ilog1log31312222nnlog3log313nlog3log31n冒泡排序最坏时间复杂度为2n，队排序最坏时间复杂度为lognn，快速排序最坏时间复杂度为lognn。所以，该算法不如冒泡排序，堆排序，快速排序。5-13.templateclassTselect(T&x,intk){if(mn)swap(m,n);if(m+nk||k=0){coutOutOfBounds;returnfalse;}int*p=newtemp[k];intmid,left=0,right=n-1,cnt=0,j=0,r=0;for(inti=0;im;i++){while(k0){do{mid=(left+right)/2;if(a[mid]b[i])left=mid;elseif(a[mid]b[i])right=mid;else{cnt=mid;break;}}while(leftright-1)if(a[left]b[i])cnt=left;elsecnt=left-1;if(kc