算法2010-2011考题 答案.doc

1、使用分治法写一个算法完成一个无序的整数数组的归并排序，并分析算法的时间复杂度。要求：算法的函数表示是MergeSort（1，n）算法对于A1:n进行排序，A是一个全局数组，含有n个元素。算法的实现可利用Merge（low,mid,high）计数，其功能是将全程数组Alow:high进行合并排序，函数调用前，Alow,high由两部分已经排序的子数组构成：Alow:mid和Alow+1:high，函数的任务是将这两部分子数组合并成一个整体排好序的数组，再存于数组Alow:high。（实现时，可认为Merge是已知的，不需要编写）（20分）解：（1）递归实现的归并排序：1. /2d7-1递归实现二路归并排序2. #includestdafx.h3. #include4. usingnamespacestd;5. 6. inta=10,5,9,4,3,7,8;7. intb7;8. 9. template10. voidMerge(Typec,Typed,intl,intm,intr);11. 12. template13. voidMergeSort(Typea,intleft,intright);14. 15. intmain()16. 17. for(inti=0;i7;i+)18. 19. coutai;20. 21. coutendl;22. MergeSort(a,0,6);23. for(inti=0;i7;i+)24. 25. coutai;26. 27. coutendl;28. 29. 30. template31. voidMerge(Typec,Typed,intl,intm,intr)32. 33. inti=l,j=m+1,k=l;34. while(i=m)&(j=r)35. 36. if(cim)47. 48. for(intq=j;q=r;q+)49. 50. dk+=cq;51. 52. 53. else54. 55. for(intq=i;q=m;q+)56. 57. dk+=cq;58. 59. 60. 61. 62. template63. voidMergeSort(Typea,intleft,intright)64. 65. if(leftright)66. 67. inti=(left+right)/2;68. MergeSort(a,left,i);69. MergeSort(a,i+1,right);70. Merge(a,b,left,i,right);/合并到数组b71. 72. /复制回数组a73. for(intg=left;g=right;g+)74. 75. ag=bg;76. 77. 78. （2）非递归实现的归并排序：1. /2d7-1自然二路归并排序2. #includestdafx.h3. #include4. usingnamespacestd;5. 6. inta=10,5,9,4,3,7,8;7. intb7;8. 9. template10. voidMerge(Typec,Typed,intl,intm,intr);11. 12. template13. voidMergePass(Typex,Typey,ints,intn);14. 15. template16. voidMergeSort(Typea,intn);17. 18. intmain()19. 20. for(inti=0;i7;i+)21. 22. coutai;23. 24. coutendl;25. MergeSort(a,7);26. for(inti=0;i7;i+)27. 28. coutai;29. 30. coutendl;31. 32. 33. template34. voidMerge(Typec,Typed,intl,intm,intr)35. 36. inti=l,j=m+1,k=l;37. while(i=m)&(j=r)38. 39. if(cim)50. 51. for(intq=j;q=r;q+)52. 53. dk+=cq;54. 55. 56. else57. 58. for(intq=i;q=m;q+)59. 60. dk+=cq;61. 62. 63. 64. 65. template66. /合并大小为s的相邻子数组67. voidMergePass(Typex,Typey,ints,intn)68. 69. inti=0;70. while(i=n-2*s)71. 72. /合并大小为s的相邻两段子数组73. Merge(x,y,i,i+s-1,i+2*s-1);74. i=i+2*s;75. 76. /剩下的元素个数少于2s77. if(i+sn)78. 79. Merge(x,y,i,i+s-1,n-1);80. 81. else82. 83. for(intj=i;j=n-1;j+)84. 85. yj=xj;86. 87. 88. 89. 90. template91. voidMergeSort(Typea,intn)92. 93. Type*b=newTypen;94. ints=1;95. while(sn)96. 97. MergePass(a,b,s,n);/合并到数组b98. s+=s;99. MergePass(b,a,s,n);/合并到数组a100. s+=s;101. 102. 2、使用贪心算法解优化问题，关键是选取合适的贪心准则。试说明解装载问题时采用的贪心准则。（最优有装载问题：一批集装箱要装上一艘载重量为c的轮船，其中集装箱i的重量为wi。最优装载问题要求确定在装在体积不受限制的情况下，将尽可能多的集装箱装上轮船。）（10分）解：算法分析：采用重量轻者先装的贪心选择策略，可产生最优装载问题的最优解。具体描述如下：2、贪心选择性质变换目标后可以证明最优装载问题具有贪心选择性质(归纳法)3、最优子结构性质最优装载问题具有最优子结构性质(反证法)由最优装载问题的贪心选择性质和最优子结构性质，容易证明算法loading的正确性。算法loading的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为O(nlogn)3、设使用动态规划算法求解最长公共子序列，写出子序列长度cij的递归表达式，写出求解序列（A，B，F，G）和序列（D，C，B，F）的最长公共子序列时cij 的值。（20分）解：Ci,j: 保存Xi与Yj的LCS（最长公共系序列）的长度递归法递推表达式：动态规划法递推表达式：算法：void LCSLength(int m，int n，char *x，char *y，int*c，int*b) inti，j;for (i= 1; i= m; i+) ci0 = 0;for (i= 1; i= n; i+) c0i = 0;for (i= 1; i= m; i+)for (j = 1; j =cij-1) cij=ci-1j; bij=2;else cij=cij-1; bij=3; 构造最长公共子序列void LCS(inti，intj，char *x，int*b)if (i=0 | j=0) return;if (bij= 1) LCS(i-1，j-1，x，b); coutxi; else if (bij= 2) LCS(i-1，j，x，b);else LCS(i，j-1，x，b);4、用回溯法解0-1背包问题，针对实例画出问题的搜索和剪枝过程。（20分）解：一个例子（老师PDF）：n=5，c=10，w=2，2，6，5，4，v=6，3，5，4，6 初始时p6=(0,0)，(w5,v5)=(4,6)。因此，q6=p6(w5,v5)=(4,6)； p5=(0,0),(4,6)； q5=p5(w4,v4)=(5,4),(9,10)。从跳跃点集p5与q5的并集p5q5=(0,0),(4,6),(5,4),(9,10)中看到跳跃点(5,4)受控于跳跃点(4,6)。将受控跳跃点(5,4)清除后，得到p4=(0,0),(4,6),(9,10) q4=p4(6，5)=(6，5)，(10，11) p3=(0，0)，(4，6)，(9，10)，(10，11) q3=p3(2，3)=(2，3)，(6，9) p2=(0，0)，(2，3)，(4，6)，(6，9)，(9，10)，(10，11) q2=p2(2，6)=(2，6)，(4，9)，(6，12)，(8，15) p1=(0，0)，(2，6)，(4，9)，(6，12)，(8，15) p1的最后的那个跳跃点(8,15)给出所求的最优值为m(1, c)=155、试用优先队列式分支限界算法解旅行商问题，给出针对下图实例的解空间树的扩展过程与队列变化状态。（15分）解：一个例题：6、设f(x)是0,2上的连续函数，且，试利用概率算法计算定积分的近似值（设生成随机数的函数是已知的）。（15）解：（1）随机投点法计算定积分：基本思想是在矩形区域上随机均匀的投点实现。本算法的基本思想是在积分区间上随机均匀的产生点, 即在a,b上随机均匀的取点, 求出由这些点产生的函数值的算术平均值, 再乘以区间宽度, 即可解出定积分得近似解。随机化算法：用随机投点法计算定积分：#includestdafx.h#includeRandomNumber.h#includeusingnamespacestd;doubleDarts(intn,doublea,doubleb);doublef(doublex);intmain()intn1=100,n2=1000,n3=1000,n4=10000,n5=10000000;doublea=2.0,b=3.0;coutn1=n1,r1=Darts(n1,a,b)endl;coutn2=n2,r2=Darts(n2,a,b)endl;coutn3=n3,r3=Darts(n3,a,b)endl;coutn4=n4,r4=Darts(n4,a,b)endl;coutn5=n5,r5=Darts(n5,a,b)endl;return0;/*基本思想是在矩形区域内随机均匀投点，求出由这些点*产生的函数值的算术平均值，再乘以区间宽度，即可得*出定积分的近似解*/doubleDarts(intn,doublea,doubleb)staticRandomNumberdart;doublesum=0.0;for(inti=0;in;i+)doublex=(b-a)*dart.fRandom()+a;/产生a,b)之间的随机数sum=sum+f(x);return(b-a)*sum/n;doublef(doublex)returnx*x;（2）概率法计算定积分：设f:a,bc,d连续函数(如图2 所示), 则由曲线y=f(x)以及x 轴和直线x=a,x=b 围成的面积由定积分给出。根据几何概型可知。假设向矩形区域随机均匀的投镖n 次, 落入阴影为K次, 又设M为x=a、x=b、y=c、y=d 所围成的矩形面积, s 为定积分面积,则, 所以s= k/nM。具体实现：1. /随机化算法用概率法计算定积分2. #includestdafx.h3. #includeRandomNumber.h4. #include5. usingnamespacestd;6. 7. doubleDarts(intn,doublea,doubleb,doubled);8. doublef(doublex);9. 10. intmain()11. 12. intn1=100,n2=1000,n3=1000,n4=10000,n5=10000000;13. doublea=2.0,b=3.0;14. doubled=f(b);15. coutn1=n1,r1=Darts(n1,a,b,d)endl;16. coutn2=n2,r2=Darts(n2,a,b,d)endl;17. coutn3=n3,r3=Darts(n3,a,b,d)endl;18. coutn4=n4,r4=Darts(n4,a,b,d)endl;19. coutn5=n5,r5=Darts(n5,a,b,d)endl;20. return0;21. 22. 23. /*24. *f为积分函数,n为投镖25. *总数,a,b为积分区间,c,d为函26. *数f的值域的端点值27. */28. doubleDarts(intn,do