算法作业和期末复习题_48304.doc

1．给出递推公式x(n)=x(n-1)+n,x(0)=0对应的通项公式计算过程？ 解： X(n)-X(n-1)=n X(n-1)-X(n-2)=n-1 …… …… X(1)-X(0)=1 X(n)-X(0)=(n+1)n\2 X(n)= (n+1)n\2 2．(、(、(之间的区别与联系 (描述增长率的上限 上限值越低，结果越有价值。 (用来表示算法的精确阶 (描述增长率的下限 下限值越高越有价值。 联系： 只要当考察问题规模充分大时，算法中基本语句的执行次数在渐近意义下的阶，通常使用3种等渐近符号。 3．什么是数据结构，什么是算法，两者有什么关系？ 数据结构：是指相互之间存在一定关系的数据元素的集合。 算法：是对特定问题求解步骤的一种描述是指令的有限序列。 程序=算法+数据结构 5．举例说明分治法、动态规划法和贪心法适用范围，及三者之间的区别。 答：分治法：适用于原问题可划分为子问题时如汉诺塔问题（循环赛，最近对，棋盘覆盖等） 动态规划：当原问题可分解为子问题并且问题重叠并且具有最优子结构时可用动态规划法，如TSP问题（多端最短路径问题，0/1背包问题等） 贪心：当一个问题具有最优子结构性质且具有贪心选择性时可用贪心算法，如最小生成树问题（背包问题，活动安排问题等） 在分治法的基础上，满足最优子结构性质才能用动态规划，在动态规划可行的基础上满足贪心选择性才能用贪心。 6．简述分治法、贪心法、蛮力法、回溯法、减治法的设计思想。 分治：建一个难以直接解决的大问题划分成一些规模较小的子问题，以便各个击破，分而治之。 贪心把一个问题分解为一系列较简单的局部最优选择，每一步选择都是对当前解的一个扩展，直到获得问题的完整解。（指根据当前已有信息做出选择，不从整体最优考虑，只选择局部最优 蛮力：采用一定的策略将待求解问题的所有元素依次处理一次，从而找出问题的解。 回溯：只构造可能解的一部分，然后评估这个部分解，如果这个部分解有可能导致一个完全解，则对其进一步构造，否则，就不必继续构造这个解了。 减治：把一个大问题划分为若干子问题，但些子问题不需要分别求解，只需求解其中那个一个子问题。 7．举例说明分治法和减治法的在设计上区别与联系。 分治法是将一个大问题分解为若干子问题分别求解，而减治法是只求解部分子问题。在排序问题中，分治法用用快速排序，以轴值为基准划分序列，再求每个子集递归序列，最后合并并操作。减治法则用选择问题算法，先选定轴值并划分，比轴值小的在左侧，比轴值大的在右侧，选择问题的查找区间减少一半，划分后只需处理一个子序列。 8．简述什么是欧拉回路，TSP问题，哈密顿回路问题。 欧拉回路：图G的一个回路，若它恰它通过G 中每条边一次，则称该回路为欧拉回路。TSP：从图的一个顶点出发，各个定点只能经历并访问一次，最后回到原点且使路径最短。哈密顿回路：从一个城市出发，经过每一个城市恰好一次，然后回到出发城市。 1．给出应用动态规划法设计算法的一般步骤，并用动态规划法求下面多段图中从顶点0到顶点15的最短路径，写出求解过程。 解：d(0,9)=min{c01 +d(1,9) , c02+d(2,9) , c03 +d(3,9)} d(1,9)=min{c14 +d(4,9) , c15+d(5,9) } d(2,9)=min{c24 +d(4,9) , c25+d(5,9) , c26 +d(6,9)} d(3,9)=min{c35 +d(5,9) , c36+d(6,9) } d(4,9)=min{c47 +d(7,9) , c48+d(8,9) } d(5,9)=min{c57 +d(7,9) , c58+d(8,9) } d(0,9)=min{c67 +d(7,9) , c68+d(8,9) } d(7,9)= c79 =7 (7→9) d(8,9)= c89 =3(8→9) d(6,9)=min{6+7,5+3}=8(6→8) d(5,9)= min{8+7,6+3}=9(5→8) d(4,9)= min{5+7,6+3}=9(4→8) d(3,9)=min{4+9,7+8}=13(3→5) d(2,9)=min{6+9,7+9,8+8}=15(2→4) d(1,9)=min{9+9,8+9}=17(1→5) d(0,9)=min{4+17,2+15,3+13}=16(0→3) 最后得最短路径为0→3→5→8→9 长度为16。 2．有4个物品，其重量分别为(4, 7, 5, 3)，物品的价值分别为(40, 42, 25, 12)，背包容量为10。试设计3种贪心策略,并给出在每种贪心策略下背包问题的解。