离散课后作业答案

1.1算法： 是对特定问题求解步骤的一种描述，是指令的有限序列。

程序：当一个算法用某种程序设计语言来描述时，得到的就是程序，也就是说,程序是用某种程序设计语言对算法的具体实现.

算法有输入、输出、确定性、能行性和有限性等特征，当不具备有穷性时，只能叫做计算过程，而不能称之为算法，算法可以终止，而程序没有此限制。 1.2程序证明和程序测试的目的各是什么？

程序证明是确认一个算法能正确无误的工作. 程序测试的目的是发现错误

1n!?{1-9 解: n!的递归定义： n*(n?1)!n?0n?1

求解n!的递归函数 long Factorial (long n)

{

if(n<0)

{

cout<<”error!”; exit(0); }

if(n==0)

return 1;

else return n *Factorial (n-1);

}

1-10 使用归纳法，证明上题所设计的计算n！的递归函数的正确性 证明(归纳法证明)：

(1)首先，如果n=0，那么程序执行

if(n==0) return 1;

返回1,算法显然正确;

(2)假定函数Factorial对n1)能正确运行，那么，当n=k时，算法必定执行:

else return k *Factorial (k-1);

因为Factorial (k-1)正确，所以，当n=k时，程序运行正确 综合以上两点，可得程序正确. 证毕.

2-1, 简述衡量一个算法的主要性能标准,说明算法的正确性与健壮性的关系 答: 衡量一个算法的主要性能指标有:

正确性，简单性，高效低存储，最优性

算法的正确性与健壮性的关系:

所谓算法的正确性:是指在合法的输入下，算法应实现预先规定的功能和计算精度

要求;所谓算法的健壮性，是指当输入不合法时，算法应该能按某种预定的方式做出适当的处理;

正确的算法不一定的是健壮的，健壮的算法也不一定是完全正确的.正确性和健壮

性是相互补充的.一个可靠的算法，要求能在正常情况下正确的工作，而在异常情况下，亦

能做出适当处理.

2-9(1)设计一个C/C++程序，实现一个n*m的矩阵转置，原矩阵与其转置矩阵保存在二维数组中.

Void reverse(int **a,int **b,int n,int m) {

For(int i=0;i

For(int j=0;j

(2)使用全局变量count,改写矩阵转置程序，并运行修改后的程序以确定此程序所需的程序步

Void reverse(int **a,int **b,int n,int m,int &count) {

int i=0; count++; int j=0; count++; For(;i

For(;j

{

count++;

b[j][i]=a[i][j];

count++; }

}

2-10 试用定义证明下列等式的正确性

22（1） 当 n?1 时，5n?8n?2?5n，所以，可选 c?5，n0?1。对于n?n0，

f(n)?5n2?8n?2?5n2，所以，5n2?8n?2??(n2)。

2222（2） 当 n?8 时，5n?8n?2?5n?n?2?4n，所以，可选 c?4，n0?8。对

于n?n0，f(n)?5n?8n?2?4n，所以，5n?8n?2??(n)。

（3） 由（1）、（2）可知，取c1?4，当n?n0时，有c1n2?5n2?8n?2?c2n2，c2?5，n0?8，所以5n?8n?2??(n)。

2-11. (1) 当n?3时，long?n?3222222?，long所以f(n)20n?lon?g，ng(n)?n?log3n?2n。可选 c?21，n0?3。对于n?n0，f(n)?cg(n)，即2f(n)??(g(n))。注意：是f(n)和g(n)的关系。

（2） 当 n?4 时，所以 f(n)?n2/logn?n2，logn?n?log2n，g(n)?nlog2n?n2。可选 c?1，n0?4。对于 n?n0，f(n)?n2?cg(n)，即 f(n)??(g(n))。 （3）因为 f(n)?(logn)logn?nlog(logn)，g(n)?n/logn?nlogn2。当 n?4 时，

ng)f(n)?nlog(lo?n，g(n)?nlogn2?n。所以，可选 c?1，n0?4，对于n?n0，

f(n)?cg(n)，即 f(n)??(g(n))

2-16 使用递推关系式计算求n!的递归函数的时间(即分析1-9题中的函数的时间复杂度),要求使用替换和迭代两种方法分别计算之.

解: 分析1-9题中的函数的时间复杂度:用基本运算乘法的运算次数作为衡量时间复杂度的量

当n=0时，程序执行if(n==0) return 1;,并没有做乘法，故T(0)=0;当n>=1时程序执行n *Factorial (n-1);此时T(n)= T(n-1)+1故:

0T(n)?{T(n?1)?1n?0n?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)=n 2-19 利用递归树计算递推方程T(n)?2T(n/2)?n T(1)?2

2

假设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. SolutionType DandC1(int left,int right) {

while(!Small(left,right)&&leftP[m]) left=m+1; else return S(P) } }

5-7. template

int SortableList::BSearch(const T&x,int left,int right) const { if (left<=right) { int m=left+(right-left+1)/3; if (xl[m]) return BSearch(x,m+1,right); else return m; } return -1; }

5-8三分搜索算法的做法是:它先将待查元素X与n/3处的元素比较，然后将X与2n/3处的元素比较,比较的结果或者找到X,或者将范围缩小到原来的n/3 int Search3(int a[],int left,int right,int x) /*递归算法*/ {

int l,u;

if(left<=right) {

l=left+(right-left+1)/3; u=left+(right-left+1)*2/3; if(x==a[u]) return u; else if(x==a[l]) return l; else if(x>a[u]) return Search3(a, u+1, right,x); else if(x>a[l]) return Search3(a, l+1, u-1,x);

else

return Search3(a, left, l-1,x); }

return -1; }

void main() {

int n,*a; int x,i;

cout<<\ cin>>n;

a=new int[n]; int location=-1; for(i=0;i

cout<<\ cin>>x;

cout<

void main() {

int a[15]; int x,i;

int location=-1; for(i=0;i<15;i++) { a[i]=i+1; }

cin>>x; i=0;

int j=14,l,u; while(i<=j) { l=i+(j-i)/3; u=i+(j-i)*2/3; if(x==a[u]) { location=u; break; } else if(x==a[l]) {

//动态数组 /*非递归算法*/

本文来源：https://www.bwwdw.com/article/ccd2.html