《归纳与贪心 .ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 贪心方法与解题策略 例题6：新俄罗斯方块 新俄罗斯方块的基本规则与传统的有不同： 容纳基块的容器高度没有限制 玩家可以自己选择使用哪一种基块（与传统的俄罗斯方块一样，共有19种，每种都由4个小方块构成，包括了所有变化） 选取摆放的位置不能使得摆放后任意小方格悬空或超过两边的界限 最后的任务是使得所有列上的小方格数都为0 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 贪心方法与解题策略 【解法】 这道题使用的贪心方法非常简单： 给每种基块打一个分（下表面越宽的分值越高），每次找到能恰好填补最低处又符合规则的分值最高的方块填上即可。 题目的要求恰好允许用贪心方法实现，因为题目没有要求用最少的步骤数，只规定了一个步数范围。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 贪心方法与解题策略 虽然这道题已知的最优方法是分治法，而且这种贪心策略还没有办法证明其正确性。但在竞赛中，贪心方法实现简单，又能达到一定的正确率，因而不失为一种好方法。 尤其是在以拿分为目的的竞赛中，作为一种解题策略，贪心方法是很有意义的。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 贪心方法与解题策略 近年来，近似算法的题目越来越多，比如： 并行计算（NOI’98） 输入一个由+，-，*，/，(，)，变量（大写字母）组成的四则运算表达式，输出一段指令，控制有两个运算器的并行计算机在尽量短的时间内正确计算表达式的值。程序的得分将取决于其所能找到的最优解与标准答案相比较的优劣程度。 贪心方法作为一种较优算法，在这种类型的题目中是不容忽视的。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 贪心方法小结 贪心作为一种解题思路，虽然有时无法证明它的正确性，但在无法找到其他算法的时候，不失为一种好方法。并且，贪心与其他算法的结合，可以对其他算法起到优化作用。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 第二部分 归纳策略 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 归纳法的基本思想 归纳法的基本思想是通过列举少量的特殊情况，经过分析，最后找出一般的关系。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出有用的结论或解决问题的有效途径。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 归纳法解题的过程 细心的观察； 丰富的联想； 继续尝试； 总结归纳出结论。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 归纳法解题的过程 归纳是—种抽象，即从特殊现象中找出一般关系。由于在归纳的过程中不可能对所有的可能情况进行枚举，因而最后得到的结论还只是一种猜测(即归纳假设)。所以，严格说来对于归纳假设还必须加以严格的证明。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profi