基础数学课4-归纳
数学归纳法是一种类似现实世界中归纳法的方法。
根据理论来推断某个计算的结果。
这里我们以棋盘上放麦粒为举例
第一个落子放1粒，第二个落子放2粒，然后以后每一格都多一倍的麦子，直到放满。
那么我们是否可以推断出一种规律。
前n个麦粒的总数为 2的n次方 – 1呢？
这里我们需要进行归纳证明
首先是证明基本情况 n = 1时候是否成立这个公式
然后对 n = k-1的时候，推断n=k的情况，并验证它。
首先是n= 1的时候，麦粒必然为1
其次是根据n=k-1的时候，推断n=k的情况
因为 2的k-1次方 -1对应着 k-1格
那么2的k次方为
2的k-1次方 -1 + 2的k-1次方
最终为 2的 k次方 -1
所以结果成立
因为这个规律的成立，所以在计算某个值的时候，就没必要进行逐步的推算，最终节省资源。
而在验证规律的时候，我们甚至还可以使用编程中递归的思想进行校验，
就比如我们需要校验 第k格的麦粒总数，是否可以不断的递归下去，获取上一格的麦粒总数，然后相加呢
不过需要注意，当n=1的时候，直接返回1。
| class Result {
public long wheatNum = 0; // 当前格的麦粒数 public long wheatTotalNum = 0; // 目前为止麦粒的总数 } public class Lesson4_2 { /** * @Description: 使用函数的递归（嵌套）调用，进行数学归纳法证明 * @param k-放到第几格，result-保存当前格子的麦粒数和麦粒总数 * @return boolean-放到第k格时是否成立 */ public static boolean prove(int k, Result result) { // 证明n = 1时，命题是否成立 if (k == 1) { if ((Math.pow(2, 1) – 1) == 1) { result.wheatNum = 1; result.wheatTotalNum = 1; return true; } else return false; } // 如果n = (k-1)时命题成立，证明n = k时命题是否成立 else { boolean proveOfPreviousOne = prove(k – 1, result); result.wheatNum *= 2; result.wheatTotalNum += result.wheatNum; boolean proveOfCurrentOne = false; if (result.wheatTotalNum == (Math.pow(2, k) – 1)) proveOfCurrentOne = true; if (proveOfPreviousOne && proveOfCurrentOne) return true; else return false; } } } |
这样利用递归，从而验证了数据归纳法的推断是正确的。
这里我们说了下数学归纳法
如果可以对某个事情进行总结，得到规律，那么就无需迭代一样反复计算，从而节省大量的资源，提升性能了。不过这需要我们合理的提出假设并进行证明。