数学归纳法
什么是数学归纳法
对于某些使用迭代法或者递归的代码，验证的时候可以避免一步步的计算，直接从理论上证明某个结论，节约大量的计算资源和时间，这就是数学归纳法。
数学归纳法的步骤
- 证明基本情况（通常是 n = 1 的时候）是否成立
- 假设n = k – 1 成立，再证明 n = k 也是成立的（k 为任意大于1的自然数）
数学归纳和递归的关系
递归调用的代码和数学归纳法的逻辑是一致的，只要证明数学归纳法的逻辑是对的，递归调用的逻辑就是对的，没必要纠结递归函数是如何嵌套调用和返回的
数学归纳法最大的特点就是在于归纳。它已经总结出了规律。只要能证明这个规律是正确的，就没必要进行逐步的推算，节省了很多时间还和资源
练习
- 背景
- 分析
得出来的命题- 第n格的麦粒数是 2 n − 1 2^{n-1} 2n−1
- 前n个棋格订单麦粒总数和为 2 n 2^n 2n -1
证明
命题1证明
- 当n = 1 的时候，麦粒数：1，因此命题在n-1成立
- 当n = k – 1 时， k – 1格的麦粒数为 2 k − 2 2^{k-2} 2k−2， 那么第k格的麦粒数为第k-1格的2倍，也就是 2 k − 2 2^{k-2} 2k−2*2 = 2 k − 1 2^{k-1} 2k−1 因此命题在n=k-1成立，也就是n=k的时候也成立
命题2证明
- 当n = 1 的时候，所有格子的麦粒总数为1，因此命题在n = 1的时候成立
- 当n = k – 1 的时候，前k – 1 格的麦粒总数为2k-1-1，基于前一个命题的结论，第k格的麦粒数为2k-1。那么前k格的麦粒总数为(2k-1 -1)+(2k-1) = 2*2k-1-1= 2 k 2^k 2k-1 = 2 k 2^k 2k -1
图片引用于 极客时间–>黄申
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/227025.html原文链接：https://javaforall.net
