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

1、习题4.13A1A2A3A6A7A4A5A8A910111213141516171819(b)元素最大交换次数：A9A5 各1次；A4A3 各2次；A2最多3次；A1最多4次最多共需16次元素交换4.13另解：考虑第i个节点，其子节点为2i，则最多可交换1次；若子节点有子节点22i, 则最多可交换2次；若.有子节点i2k, 则最多可交换k次；因此有i2k 19求出满足上述不等式的最大的k值即可。i=1时, k=4; i=2时, k=3; i=3或4时, k=2;i=59时, k=1; 因此最多交换4+3+22+15=16次6.5 用分治法求数组A1n元素和，算法的工作空间是多少？输入：数组A1n输出：数组的所有元素之和Ai i=1nSUM(low, high)1. if high = low then2. return Alow3. else4. mid(low+high)/25. s1SUM(low,mid)6. s2SUM(mid+1, high)7. return s1+s28. end if工作空间：midQ(logn), s1&s2Q(1)（后序遍历树，不断释放空间，故为常数

2、Q(1)），总的工作空间为Q(logn).6.6 用分治法求元素x在数组A中出现的频次。freq(Alow, high, x)1. if high=low then2. if Alow=x then3. return 14. else5. return 06. end if7. else8. mid (low+high)/29. f1 freq(Alow, mid)10. f2 freq(Amid+1, high)11. return f1+f212. end if复杂度:T(n)=T(n/2)+ T(n/2)2T(n/2) (设2kn2k+1)=2kT(n/2k) =2kT(1) = n6.16修改后的MERGESORT算法最大比较次数最小比较次数令n/2k=m2，展开可知：T(n)= 2kT(n/2k) + kn - (2k-1)= n/mm(m-1)/2 + nlog(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/m nlogm nm 且须有nm=O

3、(nlogn), i.e., nm cnlogn,则须有mclogn. 可令c=1,则mlogn. 另一方面，C(n) = 2kC(n/2k)+kn/2 = n/m(m-1) + (n/2)log(n/m)= Q(nlogn)6.35 split(Alow,.high)1. xAlow /备份为x2. while (lowhigh)3. while (low0) -high;4. Alow Ahigh5. while (lowhigh & Alow0) +low;6. Ahigh Alow7. 8. Alow x /这时, low=high7.3 动态规划法计算二项式系数，并分析其时间复杂度。1. for i1 to n2. Ci,0 1; Ci, i 13. end for4. for i2 to n5. for j1 to i-1 / min(k, i-1) /例如计算C6,26. Ci,j Ci-1,j-1 + Ci-1,j7. end8. end for9. return Cn.k复杂度分析： 或8.5 硬币的面值为1, 2, 4, 8, ., 2k, 要兑换的值n2k+1，用

4、贪心算法解这个问题，要求算法复杂度为O(logn)输入：k+1个不同硬币的面值，其中包括单位币（面值为1）输出：若要兑换的值n，给出各个面值硬币的数目num0k1. 将k+1个不同的面值按递增顺序排列，记为Value0.k2. num0k03. for j k downto 04. numj n/Valuej5. nn - numjValuej6. end for7. return num0k8.16 修改Dijkstra算法，使它找出最短路径和它的长度。1. X=1; YV-1; 10; pre10;2. for y2 to n3. if y 相邻于1 then ylength1,y 4. else y 5. end if6. end for7. for j1 to n-18. 令yY, 使得y为最小的 9. XXy 10. YY - y 11. for 每条边(y,w) 12. if wY and y+lengthy,w w then13. w y+lengthy,w 14. prew y14. end if15. end for16.end for输出最短路径void Print

5、Path(int node) /输出格式为1node if (node=1) print(“1”); else PrintPath( prenode ); /先递归再输出 print(“”, node); 13.2 考虑3着色问题，给出一个算法判断一图G=(V,E)的3着色向量c1n是否是合法的。输入：图G=(V,E)，向量c1n输出：flag=true 若合法着色；否则flag=false2. for i1 to n3. if ci04. for (i,j)E5. if cj0 and cj=ci6. return false;7. end if8. end for9. end if10. end for11. return true13.3 考虑3着色问题，给出一个算法判断一图G=(V,E)的3着色向量c1k是否是部分的。输入：图G=(V,E)，向量c1k输出：true 若着色是部分的；否则输出false2. for i1 to k3. if ci04. for (i,j)E5. if jk and cj0 and cj=ci6. return false;7. end if8.

6、end for9. end if10. end for11. return true13.10 设计一个回溯算法来生成数字1,2,n的所有排列。输入：数字1,2,n输出：数字1,2,n的所有排列c1,n向量1. for k 1 to n2. ck 03. end for5. k 1 6.while k17. while ckn-1 8. ck ck+19. if c为合法的then output c (and goto 12)10. else if c为部分解 then k k+111. end while 12. ck 0 13. k k-1 14. end while 14.7 对二分查找算法进行随机化，即每次迭代时，随机选择剩下的位置代替搜索空间减半，假设在low与high之间每个位置被选中的概率都是相同的。比较这种随机化算法与二分查找的表现。输入：n个元素的升序数组A1n和元素x输出：若x=Aj, 1jn, 则输出j, 否则输出01. low1; high n; j02. while(low high) and (j=0)3. mid ( low+high)/2 / midra

7、ndom(low,high)4. if x=Amid then j mid 5. else if xAmid then high mid-16. else low mid+17. end while8. return j时间复杂度分析将每次迭代时随机选择的位置记为k，且在low与high之间每个位置被选中的概率都是1/n，期望比较次数C(n)满足nC(n) = n + 2C(1)+C(2)+C(n-2) +C(n-1) (1)(n-1)C(n-1)= n-1 + 2C(1)+C(2)+C(n-2) (2)(2)-(1) nC(n) - (n-1)C(n) = 1 + 2C(n-1) nC(n) = 1 + (n+1)C(n-1)nC(n) = 1 + (n+1)C(n-1) (可将C(n)=n代入推导过程，以验证其正确性) 因此，随机化拟二分查找的时间复杂度为O(n)，二分查找的时间复杂度为O(logn)。随机化方法的效率反而比二分查找低，其原因在于14.10 设L=x1,x2,xn是一个元素序列，其中元素x恰好出现k次（1kn），我们要找到一个j，使得xj=x。考虑重复执行下面的过程直到找到x 为止。生成一个1到n之间色随机数i，并检查是否xi=x。在平均情况下，这种方法和线性方法查找哪一种方法快？请说明。解：(1) 随机查找的情况 不妨设第i1,i2,ik个元素等于x，记I=i1,i2,ik, |I|=k, 则PiI=k/n，记p=k/n, q=1-p，则查找长度的数学期望E(ASL)=p1+qp2+qi-1pi+=1/p=n/k(2) 线性查找的情况其中，分母=n(n-1)(n-2)(n-i+1)=n!/(n-i)!分子=(n-k)( n-k-1)(n-k-i+2)ki=(n-k)!ki /(n-k-i+1)!则通项可写为于是，可以证明上式的

《算法设计技巧与分析习题参考答案》由会员l****分享，可在线阅读，更多相关《算法设计技巧与分析习题参考答案》请在金锄头文库上搜索。