《计算机算法基础》第三版,课后习题答案.docx

文档介绍：该【《计算机算法基础》第三版,课后习题答案 】是由【kunpengchaoyue】上传分享，文档一共【10】页，该文档可以免费在线阅读，需要了解更多关于【《计算机算法基础》第三版,课后习题答案 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。
T(n)二Ig(n)n足够小
n=[2T(n/2)+f(n)否则
当①n=2kg(n)=0(1)和f(n)二0(n);
②n=2kg(n)=0(1)和f(n)二0(1)。
解:T(n)=T(2k)=2T(2k-i)+f(2k)=2(2T(2k-2)+f(2k-i))+f(2k)
=22T(2k-2)+21f(2k-1)+f(2k)=2kT(1)+2k-1f(2)+2k-2f(22)+・・・+2of(2k)
=2kg(n)+2k-1f(2)+2k-2f(22)+…+2of(2k)
当g(n)=0(1)和f(n)二O(n)时,
不妨设g(n)=a,f(n)=bn,a,b为正常数。贝V
T(n)=T(2k)=2ka+2k-1*2b+2k-2*22b+…+2o*2kb=2ka+kb2k=an+bnlogn=0(nlogn)
当g(n)=O(1)和f(n)二0(1)时,
不妨设g(n)=c,f(n)=d,c,d为正常数。则
T(n)=T(2k)=c2k+2k-1d+2k-2d+…+2od=c2k+d(2k-1)=(c+d)n-d=0(n)
,写一个二分检索的递归过程。
ProcedureBINSRCH(A,low,high,x,j)
integermid
iflowWhighthen
ow
ifx=A(mid)thenj~mid;endif
ifx>A(mid)thenBINSRCH(A,mid+1,high,x,j);endif
ifx<A(mid)thenBINSRCH(A,low,mid-1,x,j);endif
elsej~0;endif
endBINSRCH
“三分”检索算法。它首先检查n/3处的元素是否等于某个x的值,然后检查2n/3处的元素;这样,或者找到x,或者把集合缩小到原来的1/3。分析此算法在各种情况下的计算复杂度。
ProcedureThriSearch(A,x,n,j)integerlow,high,p1,p2low1;high~nwhilelowWhighdo
P1-L(2low+high)/3」;p2—L(low+2high)/3」
case
:x=A(p1):jjp1;return
:x=A(p2):jjp2;return
high~pl—llowp2+llowpl+1;
high~p2T
:x<A(p1):
:x>A(p2)::else:endcaserepeatjTendThriSearch
T(n)二Ig(n)n足够小
n=[T(n/3)+f(n)否则
g(n)=0(1)f(n)二0(1)
成功:
0(1),0(log3(n)),0(log3(n))
最好,平均,最坏
失败:
0(log3(n)),0(log3(n)),0(log3(n))
最好,平均,最坏
,证明E=I+2n,其中,E,I分别为外部和内部路径长度。
证明:数学归纳法
当n=1时,易知E=2,I=0,所以E=I+2n成立;
假设nWk(k>0)时,E=I+2n成立;
则当n二k+1时,不妨假定找到某个内结点x为叶结点(根据二元扩展树的定义,一定存在这样的结点x,且设该结点的层数为h),将结点x及其左右子结点(外结点)从原树中摘除,生成新二元扩展树。此时新二元扩展树内部结点为k个,则满足E=I+2k,考察原树的外部路径长度为E=E-(h-1)+2h,
kkk+1k
内部路径长度为I=I+(h-1),所以E=I+2k+h+1=I+2k+2=I+2(k+1),
k+1kk+1kk+1k+1
综合①②③知命题成立。
(nlogn),它的最好情况时间是什么?能说归并分类的时间是®(nlogn)吗?
最好情况:是对有序文件进行排序。
分析:在此情况下归并的次数不会发生变化log(n)次
归并中比较的次数会发生变化(两个长n/2序列归并)最坏情况
两个序列交错大小,需要比较n-1次最好情况
一个序列完全大于/小于另一个序列,比较n/2次差异都是线性的,不改变复杂性的阶
因此最好情况也是nlogn,平均复杂度nlogn。可以说归并分类的时间是®(nlogn)
“由底向上”的归并分类算法,从而取消对栈空间的利用。
答:见《数据结构》
算法MPass(R,n,)
MP1[初始化]
ill.
MP2[合并相邻的两个长度为length的子文件]
WHILEi<n-2*length+1DO
(Merge(R,i,i+length-l,i+2*length-).ili+2*length).
MP3[处理余留的长度小于2*length的子文件]
IFi+length-1<n
THENMerge(R,i,i+length-1,)
ELSEFORj=iTOnDOXj—Rj|
算法MSort(R,n)//直接两路合并排序算法,X是辅助文件,其记录结构与R相同
MS1[初始化]
lengthl1.
MS2[交替合并]
WHILElength<nDO
(MPass(R,n,).lengthl2*lengthiflength>n
thenFORj=1TOnDORj—Xj
elseMPass(X,n,).
lengthl2*length)
endif
()和()式确实能得到Cii,Ci2,C21和C22的正确值。
P=(A11+A22)(B11+B22)
Q=(A21+A22)B11
R=A11(B12-B22)
S=A22(B21-B11)
T=(A11+A12)B22
U=(A21-A11)(B11+B12)
V=(A12-A22)(B21+B22)
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
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)
1
=A11B11+A22B11+A11B22+A22B22+A11B12-A11B22-A21B11-A22B11+A21B11+A21B12-A11B11-A11B12
=A22B22+A21B12
①求以下情况背包问题的最优解,n=7,m=15,(p,.•…p)=(10,5,15,7,6,18,3)
17
和(w,••…w)=(2,3,5,7,1,4,1)。
17
将以上数据情况的背包问题记为I。设FG(I)是物品按p的非增次序输
i
入时由GREEDY-KNAPSACK所生成的解,FO(I)是一个最优解。问FO(I)/FG(I)是多少?
当物品按w的非降次序输入时,重复②的讨论。
i
解:①按照p/w的非增序可得
ii
(p/w,p/w,p/w,p/w,p/w,p/w,p/w)
551**********
=(6,5,9/2,3,3,5/3,1)
W的次序为(1,2,4,5,1,3,7),解为(1,1,1,1,1,2/3,0)所以最优解为:(1,2/3,1,0,1,1,1)
FO(I)=166/3
按照Pi的非增次序输入时得到
(p,p,p,p,p,p,p)=(18,15,10,7,6,5,3),
6314527
对应的(w,w,w,w,w,w,w)=(4,5,2,7,1,3,1)
6314527
解为(1,1,1,4/7,0,0,0)
所以FG(I)的解为(1,0,1,4/7,0,1,0)
FG(I)=47,所以FO(I)/FG(I)=166/141.
按照w的非降次序输入时得到
i
(w,w,w,w,w,w,w)=(1,1,2,3,4,5,7)
5712634
相应的(p,p,p,p,p,p,p)=(6,3,10,5,18,15,7)
5712634
解为(1,1,1,1,1,4/5,0)
则FW(I)的解为(1,1,4/5,0,1,1,1)
FW(I)=54,所以F0(I)/FW(I)=83/81.
.(0/1背包问题)
极大化工pixi
1
约束条件工wixi<Mxi=0或1lWiWn
1
这种背包问题称为0/1背包问题。它要求物品或者整件装入背包或者整件不装入。求解此问题的一种贪心策略是:按p/w的非增次序考虑这些物品,只要
ii正被考虑的物品能装进的就将其装入背包。证明这种策略不一定能得到最优解。
证明:当按照p/w的非增次序考虑物品存放背包时,如果所装入的物品恰
ii能装满背包时,易证为最优解,否则未必是最优解。
可举例如下:设n=3,M=6,(p,p,p)=(3,4,8),(w,w,w)
123123
=(1,2,5),按照p/w的非增序得到(p/w,p/w,p/w)=(3,2,),
ii112233
则其解为(1,1,0),而事实上最优解是(1,0,1),问题得证。
假定要将长为l,/,•••,/的n个程序存入一盘磁带,程序i被检索的频
12n
率是f。如果程序按i,i,…,i的次序存放,则期望检索时间(ERT)是
i12n
[工(f工l)]/工f
ijiki
j=1k=1i=1
证明按l的非降次序存放程序不一定得到最小的ERT。
i
证明按f的非增次序存放程序不一定得到最小的ERT。
i
③证明按f/1的非增次序来存放程序时ERT取最小值。
ii
证明:只需证明结论③是正确的即可,现证明如下:
假设l,l,…,l按照f/l的非增次序存放,即
i1i2inii
f/1三f/1三…三f/1,则得到
iiiiii
ERT=[/l+f(l+1)+•••+f
(l+l+…+
]/》f
ii=1
假设该问题的一个最优解是按照j
1
j,…,
j的顺序存放,并且其期望检
n
1
索式件是ERT',我们只需证明ERTWERT',即可证明按照f/1的非增次序存ii
放得到的是最优解。易知
ERT'=[fl+f
j1j1j2
(l+1)+•••+f
j1j2jn
(l+1+•••+l)]/工f
j1j2jni
i=1
1
1
从前向后考察最优解中的程序,不妨设程序j是第一个与其相邻的程序j
kk+i
1
则交换程序j和程序j,得到的期望检索时间kk+1
存在关系//1W//1,
jkjkjk+1jk+1
记为ERT"
ERT"-ERT"=fl-f1WO
jkjk+1jk+1jk
ERT""WERT"
显然ERT""也是最优解,将原来的最优解中所有这样类似于反序对的程序互换位置,得到的解不比原来的最优解差,所以最终变换后得到的解也是最优解,
而最终的解恰是程序按f/1的非增次序来存放得到的顺序。命题得证。
ii
假定要把长为l,l,…,l的n个程序分布到两盘磁带T和T上,并且希望
12n12
按照使最大检索时间取最小值的方式存放,即,如果存放在T和T上的程序集合12
分别是A和B,那么就希望所选择的A和B使得max{工l,工l}取最小值。iwAiiwBi
一种得到A和B的贪心方法如下:开始将A和B都初始化为空,然后一次考虑一个程序,如果工l=min{工l,工l},贝V将当前正在考虑的那个程序分配iwAiiwAiiwBi
给A,否则分配给B。证明无论是按lWl£•••£l或是按l三l三…三l的次序12n12n
来考虑程序,这种方法都不能产生最优解。
证明:按照lWlW-Wl存放不会得到最优解,举例如下:
12n
3个程序(a,b,c)长度分别为(1,2,3),根据题中的贪心算法,产生的解是A={a,c}B={b},则max{工l,工l}=4,而事实上,最优解应为3,所以iwAiiwBi
得证.
按照l三l三…三l的次序存放也不会得到最优解,举例如下:
12n
5个程序(a,b,c,d,e)长度分别为(10,9,8,6,4)根据题中的贪心算法,产生的解是A={a,d,e}B={b,c},则max{工l,工l}=20,而事实上,最优解iwAiiwBi
应为19,所以得证。
①当n=7,(p,••…p)=(3,5,20,1&1,6,30)和(d,••…d)=(1,3,4,3,2,1,2)
1717
时,?
②。这里,假定作业I的效益
p>0,要用的处理时间t>0,限期d三t.
iiii
解:①根据p的非增排序得到
i
(p,p,p,p,p,p,p)=(30,20,18,6,5,3,1),对应的期限为7346215
1
(2,4,3,1,3,1,2),:
J(1)=7
J(1)=7,J(2)=3
J(1)=7,J(2)=4,J(3)=3
J(1)=6,J(2)=7,J(3)=4,J(4)=3;
②证明:显然即使t>0(d三t),如果J中的作业可以按照G的次序而又不
iii
违反任何一个期限来处理,即对o次序中的任一个作业k,应满足d三工t,kjj=1
则J就是一个可行解。
下面证明如果J是可行解,则使得J中的作业可以按照d,〃,…,d排列i1i2in
的序列O处理而又不违反任何一个期限。
因为J是可行解,则必存在o'=rr…r,使得对任意的r,都有d三工t,
12nkkj
j=1
我们设o是按照dWdd排列的作业序列。假设oTo,那么令a是使
iii
r丰i的最小下标,设r=i,
aaba
显然b>a,在o,中将r与r相交换,因为dWd
ab
1
1
显然r和r可以按期完成作业。
ab
还要证明r和r之间的作业也能按期完成。因为dWd,而显然二者之间
abrr
ba
的所有作业r,都有d>d,又由于o是可行解,所以tWdWd。所以作
trrkrr
tbbt
k=1
业r和r交换后,所有作业可依新产生的排列o"==ss…s的次序处理而不违ab12n
反任何一个期限,连续使用这种方法,o"就可转换成o且不违反任何一个期限,定理得证。
①已知n-1个元素已按min-堆的结构形式存放在A(l),…,A(nT)。现要将另一存放在A(n)的元素和A(1:n-1)中元素一起构成一个具有n个元素的min-堆。对此写一个计算时间为O(logn)的算法。
在A(1:n)中存放着一个min-堆,写一个从堆顶A⑴删去最小元素后将其余元素调整成min-堆的算法,要求这新的堆存放在A(1:n-1)中,且算法时间为O(logn).
利用②所写出的算法,写一个对n个元素按非增次序分类的堆分类算法。分析这个算法的计算复杂度。
解:①procedureINSERT(A,n)
integeri,j,k
j~n;i
n/2
1
whilei±landA[i]>A[j]dok~A[j];
A[j]-A[i];A[i]-kjT;
i—Li/2_
repeat
endINSERT
②procedureRESTORE(A,l,n)
integeri,j,kx—A[n];
A[n]—A[l]
i—1j—2*iwhilejWn-1doif(j<n-1)and(A[j]>A[j+1])thenj—j+1
endifif(x>A[j])
thenA[i]—A[j];i—j;j—2*i
elsei—n
endifrepeat
endRESTORE
procedureHEAPSORT(A,n)
integeri,k
fori=_n/2_to1step-1do
RESTORE(A,i,n)
repeat
fori=nto2step-1dok—A[1];A[1]—A[i];A[i]—k
RESTORE(A,1,i-1)
repeatendHEAPSORT
.①证明如果一棵树的所有内部节点的度都为k,则外部节点数n满足nmod(k-1)=1.
②证明对于满足nmod(k-1)=1的正整数n,存在一棵具有n个外部节点的k元树T(在一棵k元树中,每个节点的度至多为k)。进而证明T中所有内部节点的度为k.
证明:①设某棵树内部节点的个数是m,外部结点的个数是n,边的条数是e,则有
e=m+n-1和e=mk
mk二m+n—1n(k—l)m二n—1nnmod(k—l)=l
②利用数学归纳法。
当n=1时,存在外部结点数目为1的k元树T,并且T中内部结点的度为k;
假设当nWm,且满足nmod(k-1)=1时,存在一棵具有n个外部结点的k元树T,且所有内部结点的度为k;
我们将外部结点数为n(n为满足nWm,且nmod(k-1)=1的最大值)的符合上述性质的树T中某个外部结点用内部结点a替代,且结点a生出k个外部结点,易知新生成的树T'中外部结点的数目为n+(k-1),显然n为满足nmod(k-1)=1,且比m大的最小整数,而树T'每个内结点的度为k,即存在符合性质的树。
综合上述结果可知,命题成立。
1
.①证明如果nmod(k—1)=1,(q,q,…,q)生成一棵最优的k元归并树。
12n
②当(q,q,…,q)=(3,7,8,9,15,16,18,20,23,25,28)时,画出使
1211
用这一规则所得到的最优3元归并树。
解:①通过数学归纳法证明:
对于n=1,返回一棵没有内部结点的树且这棵树显然是最优的。
假定该算法对于(q,q,…,q),其中m=(k-1)s+1(0<s),都生
12m
成一棵最优树.
则只需证明对于(q,q,…,q),其中n=(k-1)(s+1)+1,也能生成最优
12n
树即可。
不失一般性,假定qWq£•••£q,且q,q,…,q是算法所找到的k
12n12k
棵树的WEIGHT信息段的值。于是q,q,…,q棵生成子树T,设T是一棵对于
12k
(q,q,…,q)的最优k元归并树。设P是距离根最远的一个内部结点。如
12n
果P的k个儿子不是q,q,…,q,则可以用q,q,…,q和P现在的儿子进
12k12k
行交换,这样不增加厂的带权外部路径长度。因此T也是一棵最优归并树中的子树。于是在T'中如果用其权为q1+q2+・・・+qk的一个外部结点来代换T,则所生成的树T"是关于(q+q+•••+q,q,…,q)的一棵最优归并树。由归纳假设,在
12kk+1n
使用其权为q+q+•••+q的那个外部结点代换了T以后,过程TREE转化成去求
12k
取一棵关于(q+q+•••+q,q,…,q)的最优归并树。因此TREE生成一棵关于
12kk+1n
(q,q,…,q)的最优归并树。
12n
1
m=2
,使其输出每对结点(i,j)间的最短路径,这个新算法的时间和空间复杂度是多少?
ProcedureShortestPath(COST,n,A,Max)integeri,j,krealCOST(n,n),A(n,n),Path(n,n),Max
fori~ltondo
forj~ltondo
A(i,j)-COST(i,j)
ifiMjandA(i,j)工MaxthenPath(i,j)~j
elsePath(i,j)~0
endif
repeat
1
m=2
repeat
fork~ltondo
fori~ltondo
forj~ltondo
ifA(i,j)>A(i,k)+A(k,j)
thenA(i,j)~A(i,k)+A(k,j)Path(i,j)~Path(i,k)
endifrepeatrepeatrepeat
fori~ltondo
forj~ltondoprint(“thepathofitojis”i)k~path(i,j)whilekMOdo
print(,k)k—path(k,j)
repeat
repeat
repeat
endShortestPath
时间复杂度O(nQ,空间复杂度O(n2)
.①证明算法OBST的计算时间是O(n2)。
②在已知根R(i,j),OWi<jW4的情况下写一个构造最优二分检索树T的算法。证明这样的树能在O(n)时间内构造出来。
解:①将C中元素的加法看做基本运算,则算法OBST的时间复杂性为:
工刃(R(i+1,j)-R(i,j-1)+1)二
工辺(R(i+1,i+m)-R(i,i+m-1)+1)=
m=2i=0
乞(R(n-m+1,n)-R(0,m-1)+n-m+1)=O(n2)
②ProcedureBuildTree(m,n,R,Root)integerR(n,n),kTreeNodeRoot,LR,RRk~R(m,n)
ifkHOthendata(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,endifendBuildTree
时间复杂性分析:T(n)二c+T(k)+T(n-k-1),此递推式保证算法的时间复杂性为O(n),也可从递归的角度出发,递归的次数正是结点的个数,而每次递归时间复杂性为常数,所以算法的时间复杂度也为O(n)。
()出现最坏情况的例子,它使得S|=2i,0Wi<n。还要求对n的任意取值都适用。
解:取(P1,P2,…,Pi,・・・)=(W1,W2,…,Wi,・・・)=(2o,2i,・:2i-i,…)
P和W取值相同,使支配原则成立,也就是说不会因为支配原则而删除元素;只要说明不会出现相同元素被删除一个的情形,即可知是最坏的情况。可用归纳法证明此结论。
1