计算机算法基础课后答案整理版Word格式文档下载.docx

计算机算法基础课后答案整理版Word格式文档下载.docx

《计算机算法基础课后答案整理版Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《计算机算法基础课后答案整理版Word格式文档下载.docx（30页珍藏版）》请在冰点文库上搜索。

j←mid;

endif

ifx>

A（mid）then

BINSRCH（A,mid+1,high,x,j）;

ifx<

BINSRCH（A,low,mid-1,x,j）;

else

j←0;

endBINSRCH

P99-5

作一个“三分”检索算法，它首先检查n/3处的元素是否等于某个x的值，然后检查2n/3处的元素。

这样，或者找到x，或者把集合缩小到原来的1/3。

分析此算法在各种情况下的计算复杂度。

ProcedureThriSearch（A,x,n,j）

integerlow,high,p1,p2

low←1;

high←n

whilelow≤highdo

p1←⎣（high+2low）/3⎦

p2←⎣（2high+low）/3⎦

case

:

x=A（p1）:

j←p1;

return

x=A（p2）:

j←p2;

x<

A（p1）:

high←p1-1

x>

A（p2）:

low←p2+1

else:

low←p1+1;

high←p2-1

endcase

repeat

j←0

endThriSearch

实例运行

{1,2,3,4,5,6,7,8,9}

361

时间复杂度

成功:

􀂉

O

（1）,O（log3（n））,O（log3（n））

最好，平均，最坏

失败:

O（log3（n））,O（log3（n））,O（log3（n））

P99-6

对于含有n个内部结点的二元树，证明

E=I+2n

其中，E，I分别为外部和内部路径长度。

证明：

数学归纳法

当n=1时，易知E=2，I=0，所以E=I+2n成立；

假设n≤k（k>

0）时，E=I+2n成立；

此时新树内部结点为k个，则满足：

Ek=Ik+2k

（1）

考察原树的外部路径长度和内部路径长度：

Ek+1=Ek-h+2（h+1）

（2）

Ik+1=Ik+h（3）

综合

（1）

（2）（3）式：

Ek+1=Ik+2k+h+2

=Ik+1-h+2k+h+2

=Ik+1+2（k+1）

故命题成立。

P99-10

过程MERGESORT的最坏情况时间是O（nlogn），它的最好情况时间是什么？

能说归并分类的时间是Θ（nlogn）吗？

最好情况：

对有序文件进行排序

分析

归并的次数不会发生变化----log（n）次

归并中比较的次数会发生变化（两个长n/2序列归并）

最坏情况

两个序列交错大小

需要比较n-1次

最好情况

一个序列完全大于/小于另一个序列

比较n/2次

差异都是线性的，不改变复杂性的阶

最好情况也是nlog（n）,平均复杂度nlog（n）。

P99-11

写一个“由底向上”的归并分类算法，从而取消对栈空间的利用。

见《数据结构》---第九章P238

算法MPass（R，n，1ength．X）

MP1[初始化]

i←1．

MP2[合并相邻的两个长度为length的子文件]

WHILEi≤n–2*length+1DO

（Merge（R，i，i＋length–l，i＋2*length–1．X）.

i←i＋2*length）．

MP3[处理余留的长度小于2*length的子文件]

IFi+length–1<

nTHEN

Merge（R，i，i+length–1，n.X）

ELSE

FORj=iTOnDOXj←Rj▌

P99-23

通过手算证明（4.9）和（4.10）式确实能得到C11,C12,C21和C22的正确值。

C11=P+S-T+V

=（A11+A22）（B11+B22）+A22（B21-B11）-（A11+A12）B22+（A12-A22）（B21+B22）

=A11B11+A22B11+A11B22+A22B22+A22B21-A22B11-A11B22-A12B22+A12B21+A12B22-A22B21-A22B22

=A11B11+A12B21

P=（A11+A22）（B11+B22）T

=（A11+A12）B22

Q=（A21+A22）B11

U=（A21-A11）（B11+B12）

R=A11（B12-B22）V

=（A12-A22）（B21+B22）

S=A22（B21-B11）

C12=R+T

=A11B12-A11B22+A11B22+A12B22

=A11B12+A12B22

C21=Q+S

=A21B11+A22B11+A22B21-A22B11

=A21B11+A22B21

C22=P+R-Q+U

=（A11+A22）（B11+B22）+A11（B12+B22）-（A21+A22）B11+（A21-A11）（B11+B12）

=A11B11+A22B11+A11B22+A22B22+A11B12-A11B22-A21B11-A22B11+A21B11+A21B12-A11B11-A11B12

=A22B22+A21B12

第五章：

2、3、6、8、9、10、11、12

P121-2．

求以下情况背包问题的最优解，n=7，m=15，（p1,…,p7）=（10,5,15,7,6,18,3）和（w1,…,w7）=（2,3,5,7,1,4,1）。

将以上数据情况的背包问题记为I。

设FG（I）是物品按pi的非增次序输入时由GREEDY-KNAPSACK所生成的解，FO（I）是一个最优解。

问FO（I）/FG（I）是多少?

当物品按wi的非降次序输入时，重复②的讨论。

①按照pi/mi的非增序可得（p5/w5,p1/w1,p6/w6,p3/w3,p7/w7,p2/w2,p4/w4）=（6,5,9/2,3,3,5/3,1）

所以最优解为：

（1,2/3,1,0,1,1,1），并且FO（I）=166/3

②按照pi的非增次序输入时，得到（p6,p3,p1,p4,p5,p2,p7）=（18,15,10,7,6,5,3），对应的（w6,w3,w1,w4,w5,w2,w7）=（4,5,2,7,1,3,1），则FG（I）的解为（1,0,1,4/7,0,1,0），并且FG（I）=47，所以FO（I）/FG（I）=166/141.

③按照wi的非降次序输入时，得（w5,w7,w1,w2,w6,w3,w4）=（1,1,2,3,4,5,7），相应的（p5,p7,p1,p2,p6,p3,p4）=（6,3,10,5,18,15,7），则FW（I）的解为（1,1,4/5,0,1,1,1），并且FW（I）=54，所以FO（I）/FW（I）=83/81.

P122-3

3．（0/1背包问题）如果将5.3节讨论的背包问题修改成􀂄

极大化􀂄

约束条件􀂄

xi=0或11≤i≤n􀂄

这种背包问题称为0/1背包问题。

它要求物品或者整件装入背包或者整件不装入。

求解此问题的一种贪心策略是：

按pi/wi的非增次序考虑这些物品，只要正被考虑的物品能装的进就将其装入背包。

证明这种策略不一定能得到最优解。

1niipxΣ1niiwxM≤Σ

当按照pi/wi的非增次序考虑物品存放背包时，如果所装入的物品恰能装满背包时，显然为最优解，否则未必是最优解.

可举例如下：

设n=3，M=6，

（p1,p2,p3）=（3,4,8），（w1,w2,w3）=（1,2,5）

按照pi/wi的非增序得到

（p1/w1,p2/w2,p3/w3）=（3,2,1.6），

则其解为（1,1,0），而事实上最优解是（1,0,1）。

问题得证。

P122-6．

假定要将长为l1,l2,…,ln的n个程序存入一盘磁带，程序i被检索的频率是fi。

如果程序按i1,i2,…,in的次序存放，则期望检索时间（ERT）是:

①证明按li的非降次序存放程序不一定得到最小的ERT。

②证明按fi的非增次序存放程序不一定得到最小的ERT。

③证明按fi/li的非增次序来存放程序时ERT取最小值。

①l:

（4,1,2）f:

（0.8,0.1,0.1）

按li的非降序存放程序

ERT=0.1*1+0.1*3+0.8*7=6

而最优解为0.8*4+0.1*5+0.1*7=4.4

②l:

（16,1,2）f:

按fi的非增序存放程序

ERT=0.8*16+0.1*17+0.1*19=16.4

而最优解为0.1*1+0.8*17+0.1*19=15.6

证明结论③是正确的,证明如下：

假设li1,li2,…,lin按照fi/li的非增次序存放，即fi1/li1≥fi2/li2≥…≥fin/lin，则得到ERT=[fi1li1+fi2（li1+li2）+…+fik（li1+li2+…+lik）+…+fin（li1+li2+…+lin）]/假设该问题的一个最优解是按照j1,j2,…,jn的顺序存放，并且其期望检索式是ERT’，我们只需证明ERT≤ERT’，即可证明按照fi/li的非增次序存放得到的是最优解。

易知ifΣ

ERT’=[fj1lj1+fj2（lj1+lj2）+…+fjk（lj1+lj2+…+ljk）+…+fjn（lj1+lj2+…+ljn）]/,从前向后考察最优解中的程序，不妨设程序jk是第一个与其相邻的程序jk+1存在关系，则交换程序jk和程序jk+1，得到的期望检索时间记为ERT’’，容易证明ERT’’≤ERT’，显然ERT’’也是最优解，将原来的最优解中所有这样类似于反序对的程序互换位置，得到的解不比原来的最优解差，所以最终变换后得到的解也是最优解，而最终的解恰是程序按fi/li的非增次序来存放得到的顺序。

命题得证。

P123-8

①当n=7，（p1,…,p7）=（3,5,20,18,1,6,30）和（d1,…,d7）=（1,3,4,3,2,1,2）时，算法5.5所生成的解是什么？

②证明即使作业有不同的处理时间定理5.3亦真。

这里，假定作业i的效益pi>

0，要用的处理时间ti>

0，限期di≥ti.

解：

①根据pi的非增排序得到（p7,p3,p4,p6,p2,p1,p5）=（30,20,18,6,5,3,1），对应的期限为（2,4,3,1,3,1,2），按照算法3.5生成的解为：

1.J

（1）=7

（2）,

2.J

（1）=7

（2）,J

（2）=3（4）；

3.J

（1）=7

（2）,J

（2）=4（3）,J（3）=3（4）；

4.J

（1）=6

（1）,J

（2）=7

（2）,J（3）=4（3）,J（4）=3（4）；

0，限期di≥ti.（P106）

定理5.3:

设J是K个作业的集合,σ=i1i2…ik是J中作业的一种排序,它使得di1≤di2≤…≤dik.J是一个可行解,当且仅当J中的作业可以按照σ的次序又不违反任何一个期限的情况下来处理.

显然即使ti>

0（di≥ti），如果J中的作业可以按照σ的次序而又不违反任何一个期限来处理，即对σ次序中的任一个作业k，应满足dk≥Σ=kjjt1，则J就是一个可行解。

下面证明如果J是可行解，σ=i1i2…ik使得J中的作业可以按照di1≤di2≤…≤din序列排列而又不违反任何一个期限。

J是可行解，则必存在σ’=r1r2…rn，使得对任意的rk，都有dk≥Σ=kjjt1，我们设σ是按照di1≤di2≤…≤din排列的作业序列。

假设σ’≠σ，那么令a是使ra≠ia的最小下标，设rb=ia，显然b>

a，在σ’中将ra与rb相交换，因为drb≤dra，显然ra和rb可以按期完成作业，我们还要证明ra和rb之间的作业也能按期完成。

因为drb≤dra，而显然二者之间的所有作业rt，都有drb≤drt，又由于σ’是可行解，所以1btbkrrktdd=≤≤Σ，所以作业ra和rb交换后，仍满足1ttkrktd=≤Σ，即所有作业可依新产生的排列σ’’==s1s2…sn的次序处理而不违反任何一个期限，连续使用这种方法，σ’就可转换成σ且不违反任何一个期限，定理得证。

P123-9

①对于5.3节的作业排序问题证明：

当且仅当子集合J中的作业可以按下述规则处理时它表示一个可行解；

如果J中的作业I还没分配处理时间，则将它分配在时间片[a-1，a]处理，其中a是使得1≤r≤di的最大整数r，且时间片[a-1，a]是空的。

②仿照例5.4的格式，在习题5.8的①所提供的数据集上执行算法5.5。

易证如果J中的作业能按上述规则处理，显然J是可行解；

如果J是可行解，根据定理5.3可知，J中的作业根据时间期限的非降次序排列，得到i1i2…ik…in，并且按照这个顺序，可以处理J中所有作业，而对这一序列中的任意作业ik，如果它的时间期限是dk，且时间片[dk-1,dk]是空的，则分配之；

若时间片[dk-1，dk]非空，则向前找最大的非空[r-1,r]时间片，1≤r≤dk因为J是可行解，所以一定可以找到如此时间片。

故命题得证。

n=7

（p1,…,p7）=（3,5,20,18,1,6,30）

（d1,…,d7）=（1,3,4,3,2,1,2）

（p7,p3,p4,p6,p2,p1,p5）

=（30,20,18,6,5,3,1），

对应的期限为（2,4,3,1,3,1,2）

b=min{n,max{d（i）}}

=min{7,4}

=4

P123-11

①证明如果一棵树的所有内部节点的度都为k，则外部节点数n满足nmod（k-1）=1.

②证明对于满足nmod（k-1）=1的正整数n，存在一棵具有n个外部节点的k元树T（在一棵k元树中，每个节点的度至多为k）。

进而证明T中所有内部节点的度为k.

①设某棵树内部节点的个数是i，外部结点的个数是n，边的条数是e，则有

e=i+n-1

ik=e

⇒ik=i+n-1

⇒（k-1）i=n-1

⇒nmod（k-1）=1

P123-12

①证明如果nmod（k-1）=1，则在定理5.4后面所描述的贪心规则对于所有的（q1,q2,…,qn）生成一棵最优的k元归并树。

（P111）

②当（q1,q2,…,q11）=（3,7,8,9,15,16,18,20,23,25,28）时，画出使用这一规则所得到的最优3元归并树。

通过数学归纳法证明：

对于n=1，返回一棵没有内部结点的树且这棵树显然是最优的。

假定该算法对于（q1,q2,…,qm），其中m=（k-1）s+1（s≥0），都生成一棵最优树，

则只需证明对于（q1,q2,…,qn），其中n=（k-1）（s+1）+1，也能生成最优树即可。

不失一般性，假定q1≤q2≤…≤qn，且q1,q2,…,qk是算法所找到的k棵树的WEIGHT信息段的值。

于是q1,q2,…,qk可生成子树T，设T’是一棵对于（q1,q2,…,qn）的最优k元归并树。

设P是距离根最远的一个内部结点。

如果P的k个儿子不是q1,q2,…,qk，则可以用q1,q2,…,qk和P现在的儿子进行交换，这样不增加T’的带权外部路径长度。

因此T也是一棵最优归并树中的子树。

于是在T’中如果用其权为q1+q2+…+qk的一个外部结点来代换T，则所生成的树T’’是关于（T,qk+1,…,qn）的一棵最优归并树。

由归纳假设，在使用其权为q1+q2+…+qk的那个外部结点代换了T以后，过程TREE转化成去求取一棵关于（T,qk+1,…,qn）的最优归并树。

因此TREE生成一棵关于（q1,q2,…,qn）的最优归并树。

第六章12345681317

动态规划

1.多阶段过程

2.满足最优性原理

3.建立递推关系式

P151-1

􀂃

①递推关系式（6.8）对右图成立吗？

为什么？

②递推关系式（6.8）为什么对于含有负长度环的图不能成立？

•解：

•①成立，不包含负长度环

•②可以使节点间的长度任意小。

P151-2

修改过程ALL_PATHS，使其输出每对结点（i,j）间的最短路径，这个新算法的时间和空间复杂度是多少？

回忆算法：

P127算法6.1

P131算法6.3

D（i,j）/D（j）:

从节点j到汇点t的最优路径中下一个节点，即最优路径中j的后继节点。

算法6.1在计算COST（j）的同时也计算了D（j）

3－7行

计算出D（j）之后，即可计算最短路径。

9－11行

对矩阵进行初始化，每个元素赋值为边的长

度（如果没边则赋值成MAX）

1－5行

迭代计算最短路径长度

6－12行

仿照6.1，在每次计算最短路径的时候计算出D（j）再通过D（j）就可以表示出最短路径

fork←1tondo//迭代计算

fori←1tondo

forj←1tondo

ifA（i,j）>

A（i,k）+A（k,j）then

A（i,j）←A（i,k）+A（k,j）

Path（i,j）←Path（i,k）

fori←1tondo//输出最优路径

print（“thepathofitojis”i）

k←path（i,j）

whilek≠0do

print（k）

k←path（k,j）

endShortestPath

第一个循环：

O（n2）

O（n3）

空间复杂度

Cost（n,n）A（n,n）Path（n,n）

P151-3

对于标识符集（a1,a2,a3,a4）=（end,goto,print,stop），已知成功检索概率为P

（1）=1/20,P

（2）=1/5,P（3）=1/10,P（4）=1/20，不成功检索概率为Q（0）=1/5,Q

（1）=1/10,Q

（2）=1/5,Q（3）=1/20,Q（4）=1/20，用算法OBST对其计算W（i,j），R（i,j）和C（i,j）（0≤i,j≤4）。

P136算法6.5

P（i）

P

（1）=1/20,P

（2）=1/5,P（3）=1/10,P（4）=1/20

Q（i）

Q（0）=1/5,Q

（1）=1/10,Q

（2）=1/5,Q（3）=1/20,

Q（4）=1/20

P

（1）=1,P

（2）=4,P（3）=2,P（4）=1

Q（0）=4,Q

（1）=2,Q

（2）=4,Q（3）=1,Q（4）=1

P151-4

①证明算法OBST的计算时间是O（n2）。

②在已知根R（i,j），0≤i<

j≤4的情况下写一个构造最优二分检索树T的算法。

证明这样的树能在O（n）时间内构造出来。

①将C中元素的加法看做基本运算，则算法OBST的时间复杂性为：

20（（1,）（,1）1）nnmmiRijRij−==+−−+ΣΣ=20（（1,）（,1）1）nnmmiRiimRiim−==++−+−+ΣΣ=2（（1,）（0,1）1）nmRnmnRmnm=−+−−+−+ΣO（n2）

②ProcedureBuildTree（m,n,R,Root）

integerR（n,n）,k

TreeNodeRoot,LR,RR

k←R（m,n）

ifk≠0thendata（Root）←k,

BuileTree（m,k-1,R,LR）,BuileTree（k,n,R,RR）

left（Root）←LR,right（Root）←RR

elsedata（Root）←m,left（Root）←null,right（Root）←null,endif

endBuildTree

时间复杂性分析：

T（n）=c+T（k）+T（n-k-1），此递推式保证算法的时间复杂性为O（n），也可从递归的角度出发，递归的次数正是结点的个数，而每次递归时间复杂性为常数，所以算法的时间复杂度也为O（n）。

P151-5

由于我们通常只知道成功检索和不成功检索概率的近似值，因此，若能在较短的时间内找出几乎是最优的二分检索树，也是一件很有意义的工作。

所谓几乎是最优的二分检索树，就是对