算法专题-归纳策略

摘要

    归纳法或归纳推理，有时叫做归纳逻辑，是从个别性知识，引出一般性知识的推理，是由已知真的前提，引出可能真的结论。

1.知识点梳理：

Ø 基本思想

归纳法的基本思想是通过列举少量的特殊情况，经过分析，最后找出一般的关系。归纳法要比枚举法更能反映问题的本质。但是，要从一个实际问题中总结归纳出一般的关系，并不是一件容易的事情，而且，归纳过程通常也没有一定的规则可供遵循。

Ø 求解步骤

通常归纳法分为以下四个步骤：（1）细心观察题目，理解题意；（2）发散思维，联想可能的归纳策略；（3）不断尝试，测试归纳策略的正确性；（4）总结归纳出最终结果。

Ø 注意事项

严格说来对于归纳假设还必须加以严格的证明。即便找不到证明方法，也必须尽可能多地提出那些容易出错和疏漏的边界情况加以验证，使归纳出的结论和解决问题的途径经得起各种测试数据的检验。

2.重难点分析：

u 归纳算法设计时，应发散思维，尝试各种归纳策略。

u 归纳算法需要证明，如果不能严格证明，也应尽可能多的拍出错误。

例题解析：