Pascal归纳策略.ppt

《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，其中：n<2000，试求它们乘积的最大值以及该最大值的位数k。归纳策略的应用【分析】根据数学规律可知,若要使和固定的数的乘积最大，必须使这些数尽可能的多为3，于是可推得以下规律：当Nmod3＝1时，N可分解为一个4和若干个3的和；当Nmod3＝2时，N可分解为一个2和若干个3的和；当Nmod3＝0时，N直接分解为若干个3的和。按照这一分解方法，所有因数的乘积必定最大。注意：因N的最大值可达2000，乘积将超过长整型数据范围，所以需用高精度运算。归纳策略的应用例题3：“王”棋子遍历问题。题目大意：

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

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

6、们在搜索求解问题时，将会较大地提高算法效率，尤其是在一些问题的无解判定时，运用归纳策略的作用将会十分明显。归纳策略的应用例题5：Kathy函数(HNCOI)Tiger非常喜欢数学，所以他参加了学校组织的数学课外兴趣小组。在兴趣小组的学习当中，老师向Tiger介绍了Kathy函数，Kathy函数是这样定义的：