程序员的数学（一）迭代法与数学归纳法

我想传递的是一种感觉

我一直和师弟师妹们说，一个知识，你不学出点哲学的意思，就不算了解它的原理，只停留在表面，别人说什么就是什么，永远停留在“器”的层面，也没法举一反三。

有的时候我们对一个知识点可以很容易地深入理解，有时候则需要和我们其他的知识点联系一下，你才能总结出它们之间的共性部分，也就是原理。

这次博客的内容也是这样的，我们初中的数学知识，数学归纳法。但不仅仅是数学归纳，还包括如何将其与我们平时的编程相互印证，找到二者的共性。

这次博客看起来很简单，但是我想传递的是一种感觉，一种思考方式。

首先我们先讲一个我们初中学习指数的时候，数学老师为了让我们理解指数爆炸的威力时举的一个例子：

古印度国王舍罕酷爱下棋，他打算重赏国际象棋的发明人宰相西萨·班·达依尔。这位聪明的大臣指着象棋盘对国王说：“陛下，我不要别的赏赐，请您在这张棋盘的第一个小格内放入一粒麦子，在第二个小格内放入两粒，第三小格内放入给四粒，以此类推，每一小格内都比前一小格加一倍的麦子，直至放满 64 个格子，然后将棋盘上所有的麦粒都赏给您的仆人我吧！”

听过这个故事的应该都知道，如果真的按照这个方法赏赐，当时整个印度未来50年的所有税收都不够。

放满这 64 格到底需要多少粒麦子呢？这是个相当相当大的数字，想要手动算出结果并不容易。如果你觉得自己厉害，可以试着拿笔算算。其实，这整个算麦粒的过程，在数学上，是有对应方法的，这也正是我们今天要讲的第一个概念：迭代法（Iterative Method）。

迭代法

到底什么是迭代法？

迭代法，简单来说，其实就是不断地用旧的变量值，递推计算新的变量值。

我这么说可能还是比较抽象，不容易理解。我们还回到刚才的故事。大臣要求每一格的麦子都是前一格的两倍，那么前一格里麦子的数量就是旧的变量值，我们可以先记作 Xn−1；而当前格子里麦子的数量就是新的变量值，我们记作 Xn。这两个变量的递推关系就是这样的：f(n) = f(n - 1) * 2

如果你稍微有点编程经验，应该能发现，迭代法的思想，很容易通过计算机语言中的循环语言来实现。你知道，计算机本身就适合做重复性的工作，我们可以通过循环语句，让计算机重复执行迭代中的递推步骤，然后推导出变量的最终值。

具体怎么实现我就不放代码了，很简单。

迭代法有什么具体应用？

看到这里，你可能大概已经理解迭代法的核心理念了。迭代法在无论是在数学，还是计算机领域都有很广泛的应用。大体上，迭代法可以运用在以下几个方面：

• 求数值的精确或者近似解。典型的方法包括二分法（Bisection method）和牛顿迭代法（Newton’s method）。

• 在一定范围内查找目标值。典型的方法包括二分查找。

• 机器学习算法中的迭代。相关的算法或者模型有很多，比如 K- 均值算法（K-means clustering）、PageRank 的马尔科夫链（Markov chain）、梯度下降法（Gradient descent）等等。迭代法之所以在机器学习中有广泛的应用，是因为很多时候机器学习的过程，就是根据已知的数据和一定的假设，求一个局部最优解。而迭代法可以帮助学习算法逐步搜索，直至发现这种解。

数学归纳法

什么是数学归纳法？

上节我们提到，在棋盘上放麦粒的规则是，第一格放一粒，第二格放两粒，以此类推，每一小格内都比前一小格多一倍的麦子，直至放满 64 个格子。

我们假想一下自己穿越到了古印度，正站在国王的身边，看着这个棋盘，你发现第 1 格到第 8 格的麦子数分别是：1、2、4、8、16、32、64、128。这个时候，国王想知道总共需要多少粒麦子。

如果按照刚才迭代法的思想，我们需要循环64次，计算出每个格子的数量，然后相加。

那我们能不能试着找出一个规律，让我们直接求出总数来。

我们是不是可以大胆假设，前 n 个格子的麦粒总数就是 2n−1 呢？如果这个假设成立，那么填满 64 格需要的麦粒总数，就是 1+2+22+23+24+……＋263＝264−1＝18446744073709551615。

这个假设是否成立，我们还有待验证。但是对于类似这种无穷数列的问题，我们通常可以采用**数学归纳法（Mathematical Induction）**来证明。

在数论中，数学归纳法用来证明任意一个给定的情形都是正确的，也就是说，第一个、第二个、第三个，一直到所有情形，概不例外。

数学归纳法的一般步骤

• 证明基本情况（通常是 n=1 的时候）是否成立；

• 假设 n=k−1 成立，再证明 n=k 也是成立的（k 为任意大于 1 的自然数）。只要学过数学，我想你对这个步骤都不陌生。但是，现在你需要牢记这个步骤，然后我们用这个步骤来证明下开头的例子。

如何解决这个题目

为了让你更好地理解，我将原有的命题分为两个子命题来证明。第一个子命题是，第 n 个棋格放的麦粒数为 2n−1。第二个子命题是，前 n 个棋格放的麦粒数总和为 2n−1。

首先，我们来证明第一个子命题。

• 基本情况：我们已经验证了 n=1 的时候，第一格内的麦粒数为 1，和 21−1 相等。因此，命题在 k=1 的时候成立。

• 假设第 k−1 格的麦粒数为 2k−2。那么第 k 格的麦粒数为第 k−1 格的 2 倍，也就是 2k−2∗2=2k−1。因此，如果命题在 k=n−1 的时候成立，那么在 k=n 的时候也成立。

所以，第一个子命题成立。在这个基础之上，我再来证明第二个子命题。

• 基本情况：我们已经验证了 n=1 的时候，所有格子的麦粒总数为 1。因此命题在 k=1 的时候成立。

• 假设前 k−1 格的麦粒总数为 2k−1−1，基于前一个命题的结论，第 k 格的麦粒数为 2k−1。那么前 k 格的麦粒总数为 (2k−1−1)+(2k−1)=2∗2k−1−1=2k−1。

因此，如果命题在 k=n−1 的时候成立，那么在 k=n 的时候也成立。说到这里，我已经证明了这两个命题都是成立的。和使用迭代法的计算相比，数学归纳法最大的特点就在于“归纳”二字。它已经总结出了规律。只要我们能够证明这个规律是正确的，就没有必要进行逐步的推算，可以节省很多时间和资源。

递归调用和数学归纳的逻辑是相同的

不知道大家发现没有，其实我们数学归纳的证明过程类似于递归调用的过程。

但只是过程和思想相似，其实还是有细微的差别，比如我们例子这种归纳出来的结果只和n有关，这种就可以直接求取，有的则不仅和n有关，比如斐波那契数列这种，那就需要用到迭代法了，只不过我们可以用动态规划的思想去优化。

总结

最后再重复一下我想传递的思想：

一个知识，你不学出点哲学的意思，就不算了解它的原理，只停留在表面，别人说什么就是什么，永远停留在“器”的层面，也没法举一反三。

迭代法和数学归纳是我们初中的基础数学知识，也是我们编程中常用的思想，只是我们可能没有意识到。

计算机擅长做重复性问题，一般遇到重复性问题：

• 我们第一反应就是用循环，这就是很朴素的迭代法思想。
• 但是我们可以在迭代的基础上考虑下能不能用数学归纳的思想总结出第n次的结果，因为一般用迭代解决的都可以用递归解决，而数学归纳的证明过程就是递归的过程。
• 如果总结出的结果只与n有关，我们就可以跳过n次循环，直接得出结果。
• 如果不可以，我们可以考虑用动态规划来减少迭代中的重复计算。