什么是数学归纳法？

在棋盘上放麦粒的规则是，第一格放一粒，第二格放两粒，以此类推，每一小格内都比前一小格多一倍的麦子，直至放满 64 个格子。你发现第 1 格到第 8 格的麦子数分别是：1、2、4、8、16、32、64、128。

找规律

对于类似这种无穷数列的问题，我们通常可以采用数学归纳法（Mathematical Induction）来证明

数学归纳法步骤

• 证明基本情况（通常是 n=1 的时候）是否成立；
• 假设 n=k−1 成立，再证明 n=k 也是成立的（k 为任意大于 1 的自然数）。

和使用迭代法的计算相比，数学归纳法最大的特点就在于“归纳”二字。它已经总结出了规律。只要我们能够证明这个规律是正确的，就没有必要进行逐步的推算，可以节省很多时间和资源。

代码示例

  let grid = 63;
  console.time('归纳法耗时')
  console.log(`舍罕王给了这么多粒: ${  Math.pow(2, grid) - 1 }`)
  console.timeEnd('归纳法耗时')

递归调用的代码和数学归纳法的逻辑是一致的,但是数学归纳法实现的运行时间几乎为 0

数学归纳法需要我们能做出合理的命题假设，然后才能进行证明。

微信公众号

本文链接：