离散课后作业答案.doc

《离散课后作业答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.1算法：是对特定问题求解步骤的一种描述，是指令的有限序列。程序：当一个算法用某种程序设计语言来描述时，得到的就是程序，也就是说,程序是用某种程序设计语言对算法的具体实现.算法有输入、输出、确定性、能行性和有限性等特征，当不具备有穷性时，只能叫做计算过程，而不能称之为算法，算法可以终止，而程序没有此限制。1.2程序证明和程序测试的目的各是什么？程序证明是确认一个算法能正确无误的工作.程序测试的目的是发现错误1-9解:n!的递归定义：求解n!的递归函数longFactorial(longn){if(n<0){cout<<”error!”;exit(0);}if(n==0)r

2、eturn1;elsereturnn*Factorial(n-1);}1-10使用归纳法，证明上题所设计的计算n！的递归函数的正确性证明(归纳法证明)：(1)首先，如果n=0，那么程序执行if(n==0)return1;返回1,算法显然正确;(2)假定函数Factorial对n1)能正确运行，那么，当n=k时，算法必定执行:elsereturnk*Factorial(k-1);因为Factorial(k-1)正确，所以，当n=k时，程序运行正确综合以上两点，可得程序正确.证毕.2-1,简述衡量一个算法的主要性能标准,说明算法的正确性与健壮性的关系答:衡量一个算法的主

3、要性能指标有:正确性，简单性，高效低存储，最优性算法的正确性与健壮性的关系:所谓算法的正确性:是指在合法的输入下，算法应实现预先规定的功能和计算精度要求;所谓算法的健壮性，是指当输入不合法时，算法应该能按某种预定的方式做出适当的处理;正确的算法不一定的是健壮的，健壮的算法也不一定是完全正确的.正确性和健壮性是相互补充的.一个可靠的算法，要求能在正常情况下正确的工作，而在异常情况下，亦能做出适当处理.2-9(1)设计一个C/C++程序，实现一个n*m的矩阵转置，原矩阵与其转置矩阵保存在二维数组中.Voidreverse(int**a,int**b,intn,intm){For

4、(inti=0;i

5、于，，所以，。（3）由（1）、（2）可知，取，，，当时，有，所以。2-11.(1)当时，，所以，。可选，。对于，，即。注意：是f(n)和g(n)的关系。（2）当时，，所以，。可选，。对于，，即。（3）因为，。当时，，。所以，可选，，对于，，即2-16使用递推关系式计算求n!的递归函数的时间(即分析1-9题中的函数的时间复杂度),要求使用替换和迭代两种方法分别计算之.解:分析1-9题中的函数的时间复杂度:用基本运算乘法的运算次数作为衡量时间复杂度的量当n=0时，程序执行if(n==0)return1;,并没有做乘法，故T(0)=0;当n>=1时程序执行n*Factorial(

6、n-1);此时T(n)=T(n-1)+1故:替换法:T(0)=0,T(1)=1,T(2)=2-----总结得到:T(n)=n;归纳法证明:(1),当n=0时,T(0)=0,结论成立;(2)假设当k=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利用递归树计算递推方程假设n=2k,那么,总共有logn+1(即k+1)层,非递归部分之和为

7、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)&&leftP[m])left=m+1;elsereturnS(P)}}5-7.templateintSortableList