可视化计算第章基本算法和策略.pptVIP

0-1背包回溯算法说明 Maxvalue是一个递归实现的子程序，其中的主要传递参数如下： w： 项目物体的重量数组 v： 项目物体的价值数组 length_of(w)： 重量数组的长度，也是最后一个物件下标，遍历循环的开始点，直到第一个元素 max_weight：背包的最大容量 ｘ：最后的返回值，即背包中物体的价值 * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 动态规划 计算Fibonacci数列的第n项：当项数大于2时，F（n）=F（n-1）+F（n-2） 如果计算Fibonacci数列第n项，这需要计算从第3项到第n-1项 随着n值的增大，递归解法的算法时间复杂性会按几何级数增长 这类问题的关键是子问题（sub-problem）有重叠，因而分治法并不适合于此类问题的求解 * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 动态规划 基本思想是：如果一个较大问题可以被分解为若干个子问题，并且子问题有重叠，那么，可以将每个子问题的解存放到一个表中，然后通过查表来解决问题，减少不必要的重复计算 动态规划是20世纪50年代美国数学家Richard Bellman提出的 在这个术语中，Programming与编程没有关系，而是规划和设计的意思 * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 动态规划解Fibonacci数列第n项 * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 算法说明 算法递归子程序中的三个传递参数的作用分别是： a：第n项的输入参数 b：第n项的结果输出 c：计算过程中的中间结果存留数组（也就是一个线形表） 在计算过程中，每次计算的结果都保存在c数组中，出现重叠子问题时，直接到c[]数组中调取结果 * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 动态规划的分析 要消除计算过程中的重复性过程，动态规划是比较好的选择 这也是计算机科学中，进行问题求解的重要途径之一 由于动态规划需要保存中间计算结果，势必占用较大的内存空间（这点贪心法就完全不同），但时间复杂性则会降低 这就是所谓“空间换时间“的策略 * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 动态规划的分析 动态规划与贪心法不同的地方，它是一种最优化算法 当所有的解空间可以遍历的前提下，利用动态规划的思想保存所有可能的解 再通过比较就可以得到最优的解 实现原理非常简单，但非常实用，也是计算机科学中最常用的算法策略 请设计使用动态规划求解数字三角形 * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 将递归算法转成非递归的实现 递归是计算机科学中非常重要的概念，其主要优点是递归的代码量比非递归的代码量少，算法可以设计的非常简洁 这是由于递归所使用的方式是函数调用 这在计算机算法实现中属于非常自然的栈结构 不需要记录位置信息，不需要添加控制语句 这些工作都由函数调用的特性自行解决 * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 第3章 基本算法和策略PART B 《可视化计算》 Evaluation only. Created with Aspose.Slides fo