Pascal归纳策略

第十一讲归纳策略归纳法的基本思想归纳法的基本思想是通过列举少量的特殊情况，经过分析，最后找出一般的关系。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出有用的结论或解决问题的有效途径。归纳法解题的过程1.细心的观察；2.丰富的联想；3.继续尝试；4.总结归纳出结论。归纳法解题的过程归纳是—种抽象，即从特殊现象中找出一般关系。由于在归纳的过程中不可能对所有的可能情况进行枚举，因而最后得到的结论还只是一种猜测(即归纳假设)。所以，严格说来对于归纳假设还必须加以严格的证明。归纳策略解题应注意的问题：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但这只是通过总结归纳而得到的一种猜测，是否正确还需证明，对归纳假设的证明通常采用数学归纳法（证略）。归纳策略的应用例题2：若干个正整数之和为n，其中：n2000，试求它们乘积的最大值以及该最大值的位数k。归纳策略的应用【分析】根据数学规律可知,若要使和固定的数的乘积最大，必须使这些数尽可能的多为3，于是可推得以下规律：当Nmod3＝1时，N可分解为一个4和若干个3的和；当Nmod3＝2时，N可分解为一个2和若干个3的和；当Nmod3＝0时，N直接分解为若干个3的和。按照这一分解方法，所有因数的乘积必定最大。注意：因N的最大值可达2000，乘积将超过长整型数据范围，所以需用高精度运算。归纳策略的应用例题3：“王”棋子遍历问题。题目大意：在n×n格（2＜＝n=20）棋盘上的任一格子中放置一个棋子，棋子每次只能往其上、下、左、右相邻方格移动一步，求一种遍历方法，使得棋子走n2-1步遍历整个棋盘，每个方格只能被访问一次。归纳策略的应用【分析】此题很容易想到采用搜索回溯的方法去求解，即从起点位置出发，扩展其相邻四个方格的状态节点，生成一个状态树，利用深度搜索的方法求解，但这种纯搜索的方法效率太低，因此可以考虑一些简单的情况时的遍历方法：归纳策略的应用【分析】当n=2时，该棋盘存在一条回路，所以任意一点作为起点均能遍历整个棋盘，考虑到当n=4,6时的情况，进而推广到n为偶数时，均可以按规律产生回路，从给定的起点开始沿着该回路均可遍历整个棋盘。归纳策略的应用【分析】再考虑n为奇数时的情况，先设定n=3时，棋盘可划分成5个白格和4个黑格，人工可以推出，从任一黑格出发将无法遍历整个棋盘，然后考虑n=5时的情况，同样可推出，从棋盘中的任一黑格出发无法遍历整个棋盘。规律：当n为奇数时，棋子的起始位置若满足其横坐标和纵坐标之和为奇数时（即图中所示的任一黑格位置），问题将无解。归纳策略的应用这一规律很容易能够得到验证,因为按照规则，从任一黑格出发，必走一白格再走一黑格，所以白格数目与黑格数目应相等，而图中两者数目并不相等，如n=5时，图中共有黑格12个，白格共有13个。归纳策略的应用【总结】通过上述归纳，我们在搜索求解问题时，将会较大地提高算法效率，尤其是在一些问题的无解判定时，运用归纳策略的作用将会十分明显。归纳策略的应用例题5：Kathy函数(HNCOI)Tiger非常喜欢数学，所以他参加了学校组织的数学课外兴趣小组。在兴趣小组的学习当中，老师向Tiger介绍了Kathy函数，Kathy函数是这样定义的：)(2)12(3)34()()12(2)14()()2(3)3(1)1(nfnfnfnfnfnfnfnfff