算法设计技巧与分析习题参考答案.doc

《算法设计技巧与分析习题参考答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、习题4.13A1A2A3A6A7A4A5A8A910111213141516171819(b)元素最大交换次数：A9~A5各1次；A4~A3各2次；A2最多3次；A1最多4次Þ最多共需16次元素交换4.13另解：考虑第i个节点，其子节点为2i，则最多可交换1次；若子节点有子节点22i,则最多可交换2次；若…..有子节点i×2k,则最多可交换k次；因此有i×2k≤19求出满足上述不等式的最大的k值即可。i=1时,k=4;i=2时,k=3;i=3或4时,k=2;i=5~9时,k=1;因此最多交换4+3+2×2+1×5=16次6.5用分治法求数组A[1…n]元素和，算法的工作空间是

2、多少？输入：数组A[1…n]输出：数组的所有元素之和∑A[i]{i=1…n}SUM(low,high)1.ifhigh=lowthen2.returnA[low]3.else4.mid←ë(low+high)/2û5.s1←SUM(low,mid)6.s2←SUM(mid+1,high)7.returns1+s28.endif工作空间：mid~Q(logn),s1&s2~Q(1)（后序遍历树，不断释放空间，故为常数Q(1)），总的工作空间为Q(logn).6.6用分治法求元素x在数组A中出现的频次。freq(A[low,high],x)1.ifhigh=lowthen2.if

3、A[low]=xthen3.return14.else5.return06.endif7.else8.mid←ë(low+high)/2û9.f1←freq(A[low,mid])10.f2←freq(A[mid+1,high])11.returnf1+f212.endif复杂度:T(n)=T(ën/2û)+T(én/2ù)≈2T(n/2)(设2k≤n<2k+1)=…=2kT(n/2k)=2kT(1)=n6.16修改后的MERGESORT算法最大比较次数最小比较次数令n/2k=m≥2，展开可知：T(n)=2kT(n/2k)+kn-(2k-1)=n/m×m(m-1)/2+nlo

4、g(n/m)-n/m+1=n(m-1)/2+nlog(n/m)-n/m+1若T(n)=Q(nlogn),其中表达式有nm,nlogn,nlogm,n/m等.有n/m0

5、)--high;4.A[low]←A[high]5.while(low

6、.,2k,要兑换的值n<2k+1，用贪心算法解这个问题，要求算法复杂度为O(logn)输入：k+1个不同硬币的面值，其中包括单位币（面值为1）输出：若要兑换的值n，给出各个面值硬币的数目num[0…k]1.将k+1个不同的面值按递增顺序排列，记为Value[0...k]2.num[0…k]←03.forj←kdownto04.num[j]←ën/Value[j]û5.n←n-num[j]×Value[j]6.endfor7.returnnum[0…k]8.16修改Dijkstra算法，使它找出最短路径和它的长度。1.X={1};Y←V-{1};λ[1]←0;pre[1]←0;

7、2.fory←2ton3.ify相邻于1thenλ[y]←length[1,y]4.elseλ[y]←∞5.endif6.endfor7.forj←1ton-18.令y∈Y,使得λ[y]为最小的9.X←X∪{y}10.Y←Y-{y}11.for每条边(y,w)12.ifw∈Yandλ[y]+length[y,w]<λ[w]then13.λ[w]←λ[y]+length[y,w]14.pre[w]←y14.endif15.endfor16.endfor输出最短路径voidPrintPath(intnode