Pascal归纳策略.ppt

1、,第十一讲 归纳策略,归纳法的基本思想,归纳法的基本思想是通过列举少量的特殊情况，经过分析，最后找出一般的关系。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出有用的结论或解决问题的有效途径。,归纳法解题的过程,细心的观察； 丰富的联想； 继续尝试； 总结归纳出结论。,归纳法解题的过程,归纳是种抽象，即从特殊现象中找出一般关系。由于在归纳的过程中不可能对所有的可能情况进行枚举，因而最后得到的结论还只是一种猜测(即归纳假设)。所以，严格说来对于归纳假设还必须加以严格的证明。,归纳策略解题应注意的问题：,从问题的简单具体状态分析入手，目的是去寻求可以推广的一般性规律，因此应考虑简单状态

2、与一般性状态之间的联系。 从简单状态中分析出来的规律特征应能够被验证是正确的，不能想当然或任意地提出猜想，否则归纳出来的结论是错误的，必然导致整个问题的解是错解。,归纳策略的应用,例题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 但这只是通过总结归纳而得到的一种猜测，是否正确还需证明，

3、对归纳假设的证明通常采用数学归纳法（证略）。,归纳策略的应用,例题2：若干个正整数之和为n，其中：n2000，试求它们乘积的最大值以及该最大值的位数k。,归纳策略的应用,【分析】根据数学规律可知,若要使和固定的数的乘积最大，必须使这些数尽可能的多为3，于是可推得以下规律： 当N mod 31 时，N可分解为一个4和若干个3的和； 当N mod 32 时，N 可分解为一个2和若干个3的和； 当N mod 30 时，N 直接分解为若干个3的和。 按照这一分解方法，所有因数的乘积必定最大。 注意：因N 的最大值可达2000，乘积将超过长整型数据范围，所以需用高精度运算。,归纳策略的应用,例题3：“王

4、”棋子遍历问题。 题目大意：在nn格（2n=20）棋盘上的任一格子中放置一个棋子，棋子每次只能往其上、下、左、右相邻方格移动一步，求一种遍历方法，使得棋子走n2-1步遍历整个棋盘，每个方格只能被访问一次。,归纳策略的应用,【分析】此题很容易想到采用搜索回溯的方法去求解，即从起点位置出发，扩展其相邻四个方格的状态节点，生成一个状态树，利用深度搜索的方法求解，但这种纯搜索的方法效率太低，因此可以考虑一些简单的情况时的遍历方法：,归纳策略的应用,【分析】当n=2时，该棋盘存在一条回路，所以任意一点作为起点均能遍历整个棋盘，考虑到当n=4,6时的情况，进而推广到n为偶数时，均可以按规律产生回路，从给定

5、的起点开始沿着该回路均可遍历整个棋盘。,归纳策略的应用,【分析】再考虑n为奇数时的情况，先设定n=3时，棋盘可划分成5个白格和4个黑格，人工可以推出，从任一黑格出发将无法遍历整个棋盘，然后考虑n=5时的情况，同样可推出，从棋盘中的任一黑格出发无法遍历整个棋盘。 规律：当n为奇数时，棋子的起始位置若满足其横坐标和纵坐标之和为奇数时（即图中所示的任一黑格位置），问题将无解。,归纳策略的应用,这一规律很容易能够得到验证,因为按照规则，从任一黑格出发，必走一白格再走一黑格，所以白格数目与黑格数目应相等，而图中两者数目并不相等，如n=5时，图中共有黑格12个，白格共有13个。,归纳策略的应用,【总结】通过上述归纳，我们在搜索求解问题时，将会较大地提高算法效率，尤其是在一些问题的无解判定时，运用归纳策略的作用将会十分明显。,归纳策略的应用,例题5：Kathy函数(H