离散课后作业答案

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]) {

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

location=l; break; } else if(x>a[u]) i=u+1; else if(x

cout<

Void stoogesort(nt a[],int left,int right) {

if(a[left]>a[right]) swap(a,left,right); if(left+1>=right) return; int k=(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) 假设当n< right-left+1(n>=2)时，算法正确，即对于所有元素个数小于n的元素集,

算法能正确排序.

那么,当n= right-left+1时，算法执行程序段:

int k=(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时,算法正确.

由以上两点可知，算法正确.

分析算法的时间复杂度:

排序算法，基本运算仍然是元素之间的比较, 最坏情况发生在序列按递减次序排列 所以，算法时间复杂度为:

??0????1??0，??2??1，??n??3???2n???1。 3??logn?1?3?设n?2??，则i?。

log3?1?2?i??4???4??2???n??3??n??1?3?3??n??1??1?9??n??3?1???

?9??3???9????2?i?i?1i?2?3????n??3?3???3?1

???3???i3i?1?3??2??

2i?3i1?3??2 2logn?13n1???2log3?1? 222?3?nlog3log3?1

log3?log3??1???n ?????2冒泡排序最坏时间复杂度为?n，队排序最坏时间复杂度为??nlogn?，快速排序最坏

??时间复杂度为??nlogn?。所以，该算法不如冒泡排序，堆排序，快速排序。 5-13. template select (T&x,int k) { if(m>n) swap(m,n); if(m+n0) {

do { mid=(left+right)/2; if(a[mid]b[i]) right=mid; else {cnt=mid; break;} }while(leftcnt) { if(cnt>0) { for(j=0;j

}

}

} 6-1

设有背包问题实例，n=7，(w0,w1,w2,w3,w4,w5,w6)=(2,3,5,7,1,4,1)，

(p0,p1,p2,p3,p4,p5,p6)=( 10,5,15,7,6,18,3)，M=15。求这一实例的最优解及最大收益. 解:

首先，选择最优量度标准为收益重量比;

其次, 依据收益重量比的非增次序对输入(物品)进行排序

(p0/w0,p1/w1,p2/w2,p3/w3,p4/w4,p5/w5,p6/w6)=(5,5/3,3,1,6,4.5,3) 对物品排序结果为:4,0,5,2,6,1,3 最后，进行贪心选择:

X=(4) X=(4,0) X=(4,0,5) (剩余载重)U=14 U=12 U=8

(收益) P=6 P=6+10=16 P=16+18=34

X=(4,0,5,2) X=(4,0,5,2,6) X=(4,0,5,2,6,1(2/3))

(剩余载重)U=3 U=2 U=0

(收益) P=34+15=49 P=49+3=52 P=52+2/3*5=55.33 所以,最优解为x=(1,2/3,1,0,1,1,1); 即装入第0,2,4,5,6物品和第1个物品的2/3 最大收益: P=55.33

6-2,0/1背包问题是一种特殊的背包问题，装入背包的物品不能分割,只允许或者整个物品装入背包，或者不装入，即xi=0,或1,(0<=i

首先，选择最优量度标准为收益重量比;

其次, 依据收益重量比的非增次序对输入(物品)进行排序

(p0/w0,p1/w1,p2/w2,p3/w3,p4/w4,p5/w5,p6/w6)=(5,5/3,3,1,6,4.5,3) 对物品排序结果为:4,0,5,2,6,1,3 最后，进行贪心选择:

X=(4) X=(4,0) X=(4,0,5) (剩余载重)U=14 U=12 U=8

(收益) P=6 P=6+10=16 P=16+18=34

X=(4,0,5,2) X=(4,0,5,2,6) X=(4,0,5,2,6)

(剩余载重)U=3 U=2 继续考察第1和第3个 (收益) P=34+15=49 P=49+3=52 物品,都不能装入.

所以,贪心法求得的0/1背包问题的最优解为x=(1,0,1,0,1,1,1);即装入第0,2,4,5,6物品

最大收益: P=52 但实际上，当y=(1,1,1,0,1,1,0) 即装入第0,1,2,4,5物品,可获收益为P=54,所以，贪心法求得的0/1背包问题的解x一定不是最优解.

原因是: 对于0/1背包问题，贪心法并不能保证使其单位载重下的收益最大，因为通常在背包没还装满时，却再也装不下任何物品，这样，就使得单位载重下的物品收益减少,所以， 0/1背包问题通常不能用贪心法求解.

6-3 设有带时限的作业排序实例n=7，收益(p0, p1, p2, p3, p4, p5, p6)=(3,5,20,18,1,6,30)，作业的时限(d0, d1, d2, d3, d4, d5, d6)=(1,3,4,3,2,1,2),给出以此实例为输入，执行函数JS得到的用最优解和最大收益。

解:X={5,6,3,2} 最大收益为74

函数JS如下:

int JS(int *d, int *x, int n) { //设p0≥p1≥?≥pn?1 }

int k=0; x[0]=0;

for (int j=1; j

int r=k;

while (r>=0 && d[x[r]]>d[j] && d[x[r]]>r+1)r--; if((r<0 || d[x[r]]<=d[j]) && d[j]>r+1){ }

for (int i=k; i>=r+1; i--) x[i+1]=x[i]; x[r+1]=j; k++;

//搜索作业j的插入位置 //若条件不满足，选下一个作业 //将x[r]以后的作业后移 //将作业j插入r+1处

在执行JS函数之前，必须先对输入(即作业)按作业的收益非增次序排序，结果为: 6,2,3,5,1,0,4 接着执行JS函数:

最初, 解集合X为空. X:

X: 6 首先, 考虑作业6, 假设将其加入集合X, 即x[0]=6; 0 1 2 3 4 5 6

考虑X中的作业能否均如期完成,因为此时X中只有作业6,其截止时限为2,故,能如

期完成,此时,将作业6加入作业子集X中,此时，子集X中的最大可用下标k=0;

X: 6

0 1 2 3 4 5 6 k

接着，考虑作业2.

首先搜索作业2在X集合中的插入位置，使得X集合中的元素按作业的截止时限的非减次序排序,因为d6=2,而d2=4,所以，可将作业2插在作业6的后面，即x[1]=2,得到X=(6,2),

X: 6 2

0 1 2 3 4 5 6

k

考虑X中的作业能否均如期完成?因为d6=2>=1, d2=4>=2,所以，X中作业均能如期完成，将作业2加入子集X中. 子集X中的最大可用下标k=k+1=1

依矩阵C可求得两个最长公共子序列分别为xyzz 和 zyyx （求一个即可）

7-17设流水作业调度的实例为n=7，(a0, a1, a2, a3, a4, a5, a6)=(6,2,4,1,7,4,7), (b0, b1, b2, b3, b4, b5, b6)=(3,9,3,8,1,5,6).请使用流水作业调度的Johnson算法求使完成时间最小的最优调度,并求该最小完成时间。

提示：依据调度规则，求得最优调度次序 解:；令mi=min{ai，bi} 0<=i<7

即得: m0=b0=3, m1=a1=2, m2=b2=3, m3=a3=1, m4=b4=1, m5=a5=4 m6=b6=6 考虑mi,对其从小到大排序得(m3,m4,m1,m0,m2,m5,m6)

考虑mi序列(如果序列中下一个数mi是ai,则作业i放在最左的空位，否则，作业i放在最右的空位)得:

最优调度顺序(3,1,5,6,2,0,4)

依据最优调度在两台处理机上处理作业，最小完成时间:36(画出如教材P170的图7-17的形式即可求得最小完成时间36) 8-1．

状态空间：描述问题的各种可能的情况，一种情况对呀状态空间的一个状态。 显示约束：用于规定每个xi取值的约束条件称为显示约束 隐式约束：用于判定一个候选解是否为可行解的条件 问题状态：在状态空间树中的每个节点称为一个问题状态

解状态：如果从根到树中某个状态的路径代表一个作为候选解的元组，则该状态为解状态 答案状态：如果从根到树中某个状态的路径代表一个作为可行解的元组，则该状态为解状态。 活结点：回溯法从开始结点出发，以深度优先的方式搜索整个解空间，这个开始结点就成为一个活结点。未检测的结点称为活结点

扩展结点：算法从x出发，访问x的摸个后继结点y，则x被称为扩展结点

约束函数：一个约束函数是关于部分向量的函数Bk(x0,x1.....xk),它被定义为：如果可以判定Y的子树上不含任何答案状态，则Bk(x0,x1.....xk)为false,否则为true.

剪枝函数：约束函数和限界函数的目的相同，都是为了剪去不必要搜索的子树，减少问题求解所需实际生成的状态节点数，他们统称为剪枝函数 8-2 #include #include

int count=0;//记录可行解的个数

//先将书中的递归变为如下非递归函数，再在输出一个可行解之后，加上break; int place(int k,int xk,int *x) {

for(int j=0;j

return 1;//互不冲突,return 1 }

void NQueens(int n,int *x) {

int k=0; x[k]=-1; while(k>=0) {

x[k]=x[k]+1; while (x[k]

void main() {

int n;

cout<<\ cin>>n;

int *x=new int[n];

/* for(int i=0;i

NQueens(n,x);

cout<<\}

8-3

#include #include

int place(int k,int n,int xk,int *x) {

for(int i=xk;i

if(j==k)//互不冲突 return i; }

return -1; }

void NQueens(int n,int *x) {

int k=0; while(k>=0) { int f=place(k,n,x[k],x); if(f!=-1) { x[k]=f; if(k==n-1) { cout<<\ for(int i=0;i

\ void main() {

int n;

cout<<\ cin>>n;

int *x=new int[n]; for(int i=0;i

NQueens(n,x); }

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