名校noip讲义一归纳与贪心.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 贪心方法与解题策略 例题6：新俄罗斯方块 新俄罗斯方块的基本规则与传统的有不同： 容纳基块的容器高度没有限制 玩家可以自己选择使用哪一种基块（与传统的俄罗斯方块一样，共有19种，每种都由4个小方块构成，包括了所有变化） 选取摆放的位置不能使得摆放后任意小方格悬空或超过两边的界限 最后的任务是使得所有列上的小方格数都为0 贪心方法与解题策略 【解法】 这道题使用的贪心方法非常简单： 给每种基块打一个分（下表面越宽的分值越高），每次找到能恰好填补最低处又符合规则的分值最高的方块填上即可。 题目的要求恰好允许用贪心方法实现，因为题目没有要求用最少的步骤数，只规定了一个步数范围。 贪心方法与解题策略 虽然这道题已知的最优方法是分治法，而且这种贪心策略还没有办法证明其正确性。但在竞赛中，贪心方法实现简单，又能达到一定的正确率，因而不失为一种好方法。 尤其是在以拿分为目的的竞赛中，作为一种解题策略，贪心方法是很有意义的。 贪心方法与解题策略 近年来，近似算法的题目越来越多，比如： 并行计算（NOI’98） 输入一个由+，-，*，/，(，)，变量（大写字母）组成的四则运算表达式，输出一段指令，控制有两个运算器的并行计算机在尽量短的时间内正确计算表达式的值。程序的得分将取决于其所能找到的最优解与标准答案相比较的优劣程度。 贪心方法作为一种较优算法，在这种类型的题目中是不容忽视的。 贪心方法小结 贪心作为一种解题思路，虽然有时无法证明它的正确性，但在无法找到其他算法的时候，不失为一种好方法。并且，贪心与其他算法的结合，可以对其他算法起到优化作用。 第二部分 归纳策略 归纳法的基本思想 归纳法的基本思想是通过列举少量的特殊情况，经过分析，最后找出一般的关系。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出有用的结论或解决问题的有效途径。 归纳法解题的过程 细心的观察； 丰富的联想； 继续尝试； 总结归纳出结论。 归纳法解题的过程 归纳是—种抽象，即从特殊现象中找出一般关系。由于在归纳的过程中不可能对所有的可能情况进行枚举，因而最后得到的结论还只是一种猜测(即归纳假设)。所以，严格说来对于归纳假设还必须加以严格的证明。 归纳策略解题应注意的问题： 从问题的简单具体状态分析入手，目的是去寻求可以推广的一般性规律，因此应考虑简单状态与一般性状态之间的联系。 从简单状态中分析出来的规律特征应能够被验证是正确的，不能想当然或任意地提出猜想，否则归纳出来的结论是错误的，必然导致整个问题的解是错解。 归纳策略的应用 例题1： 求前n个自然数的平方之和： S=12+22+32+……+n2 归纳策略的应用 【分析】这本是一道很简单的题目，但如果能找出S值与n的关系，则此题将更进一步得到简化，由数学证明得知： (12+22+32+…+n2)/(1+2+3+…+n) =(2n+1)/3 又由于 1+2+3+…+n=n(n+1)/2，因此得到： 12+22+32+…+n2=n(n+1) (2n+1)/6 但这只是通过总结归纳而得到的一种猜测，是否正确还需证明，对归纳假设的证明通常采用数学归纳法（证略）。 归纳策略的应用 例题2：若干个正整数之和为n，其中：n2000，试求它们乘积的最大值以及该最大值的位数k。 归纳策略的应用 【分析】根据数学规律可知,若要使和固定的数的乘积最大，必须使这些数尽可能的多为3，于是可推得以下规律： 当N mod 3＝1 时，N可分解为一个4和若干个3的和； 当N mod 3＝2 时，N 可分解为一个2和若干个3的和； 当N mod 3＝0 时，N 直接分解为若干个3的和。 按照这一分解方法，所有因数的乘积必定最大。 注意：因N 的最大值可达2000，乘积将超过长整型数据范围，所以需用高精度运算。 归纳策略的应用 例题3：极值问题（最高时限15s） 已知m、n为整数，且满足下列两个条件： ① m、n∈1，2，…，K，（1≤K≤109） ② (n 2－mn－m2)2＝1 编一程序，由键盘输入K，求一组满足上述两个条件的m、n，并且使m2＋n2的值最大。例如，若K＝1995，则m＝987，n＝1597，则m、n满足条件，且可使m2＋n2的值最大。 归纳策略的应用 【分析】方法一 从初等数学的角度考虑： 由条件②（n 2－mn－m2）2＝1得出： n 2－mn－m2 + 1 = 0 n 2－mn－m2－1 = 0 根据求根