【程序员必修数学课】->基础思想篇->数学归纳法->如何用数学归纳提高代码效率

大家好，欢迎来到IT知识分享网。基础思想篇->数学归纳法->如何用数学归纳提高代码效率"”>

上一篇文章里，我说了数学中的迭代法，并用编程实现了国际象棋发明者的那个麦粒的计算问题，这篇文章我们就来看看数学归纳法。通过数学归纳法，我们能直接从理论上证明某个结论，从而避免很多计算，节约大量的计算资源和时间。

平常我们说的归纳，就是从大量经验事实中找出普遍特征的认知方法。我在我的一篇文章里，介绍了模式识别和机器学习的区别，其中机器学习就是一种归纳的方法，是自下而上的，这也是人类的许多体系的构成方法。

但是日常生活中所讲的归纳，和数学中的归纳还是不一样的。它们的区别是什么？具体数学归纳法可以做什么？下面我就来解答这些问题。

什么是数学归纳法？

回到国际象棋的发明人和麦粒的故事。

传说，印度的舍罕国王打算重赏国际象棋的发明人——大臣西萨·班·达依尔。这位聪明的大臣跪在国王面敢说：“陛下，请你在这张棋盘的第一个小格内，赏给我一粒麦子，在第二个小格内给两粒，在第三个小格内给四粒，照这样下去，每一小格内都比前一小格加一倍。陛下啊，把这样摆满棋盘上所有64格的麦粒，都赏给您的仆人吧?”国王说：“你的要求不高，会如愿以偿的”。说着，他下令把一袋麦子拿到宝座前，计算麦粒的工作开始了。……还没到第二十小格，袋子已经空了，一袋又一袋的麦子被扛到国王面前来。但是，麦粒数一格接一格地增长得那样迅速，很快看出，即使拿出来全印度的粮食，国王也兑现不了他对象棋发明人许下的语言。

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

如果你站在国王的身边，看着这个棋盘，你发现从第一格到第八格的麦子数分别是：1、2、4、8、16、32、64、128。这个时候你突然灵机一动，发现了棋盘的规律，第一格是1粒，也就是2¹ – 1粒，到了第二格，这两格的麦粒数总和就是 2² – 1。然后你猜测，到第 n 格的麦子总数就是 2ⁿ – 1 粒，所以到了第64格，总共就需要2⁶⁴ – 1粒麦子。

这时候你拿出和你一起穿越到古印度的计算器，2⁶⁴ – 1 = 18446744073709551615

然后就可以提醒国王他拿出全国的粮食都不够了。

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

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

数学归纳法的一般步骤是这样的：

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

我相信只要大家对高中数学还有印象，就对这个步骤很熟悉。

现在我们就用数学归纳法来证明上面的例子。我将上面的命题分为两个子命题来证明。

第一个子命题是：第 n 个棋格放的麦粒数为 2^n-1。
第二个子命题是：前 n 个棋格放的麦粒数总和为 2ⁿ – 1。

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

(1) n = 1 时，第一格的麦粒数是 1，等于 2^1-1。所以，n = 1 时，命题成立；
(2) 假设 n = k – 1 时，命题成立，即麦粒数为 2^k-2。
(3) 那么当 n = k 时，麦粒数是 n = k – 1时的两倍，即 2^k-2 * 2 = 2^k-1。

由上面(1)(2)(3)可得，该命题在 n 等于任何数时都成立，得证。

在这个基础上，我们再来证明第二个子命题。

(1) n = 1时，所有格子的麦粒总数为 1，即 2ⁿ – 1 在 n = 1时成立；
(2) 假设 n = k – 1 时，命题成立，即在第 k – 1 格，麦粒总数为 2^k-1 – 1;
(3) 那么当 n = k 时，有第一个子命题的结论可得，第 k 格的麦粒总数为 2^k-1 – 1 + 2^k-1 = 2^k-1 * 2 – 1 = 2^k – 1 。所以命题在 n = k 时成立。

由上面(1)(2)(3)可得，该命题在 n 等于任何数时都成立，得证。

这样，我们就用数学归纳法将两个子命题证明完了。和使用迭代法的计算相比，数学归纳法的最大特点就在“归纳”二字。我们已经总结出了规律，只要证明这个规律是正确的，就不需要进行逐步的推算，可以节省很多时间和资源。

那么在迭代法中我们求麦粒个数的代码就可以改进了，
在迭代法中，我们的代码如下👇

#include <stdio.h>

long getNumberOfWheat(int grid);

long getNumberOfWheat(int grid) { 
   
	int i = 2;
	long sum = 0;                 //麦子的总数
	long numberOfWheatInGrid = 0; //当前格子上麦子的数量

	numberOfWheatInGrid = 1;
	sum += numberOfWheatInGrid;

	for (; i <= grid; i++) { 
   
		numberOfWheatInGrid *= 2;
		sum += numberOfWheatInGrid;
	}
	return sum;
}

int main() { 
   
	int grid;
	long sum;

	grid = 20;

	sum = getNumberOfWheat(grid);

	printf("国王已经给了这么多粒麦子:%ld", sum);

	return 0;
}

通过归纳法，我们已经总结出了规律，所以代码可以写出如下的样子👇

#include <stdio.h>
#include <math.h>

long getNumberOfWheat(int grid);

long getNumberOfWheat(int grid) { 
   
	/* int i = 2; long sum = 0; //麦子的总数 long numberOfWheatInGrid = 0; //当前格子上麦子的数量 numberOfWheatInGrid = 1; sum += numberOfWheatInGrid; for (; i <= grid; i++) { numberOfWheatInGrid *= 2; sum += numberOfWheatInGrid; } return sum; */
	return (pow(2, grid) - 1);
}

int main() { 
   
	int grid;
	long sum;

	grid = 20;

	sum = getNumberOfWheat(grid);

	printf("国王已经给了这么多粒麦子:%ld", sum);

	return 0;
}

只需要一行代码就够了，省去了循环所带来的时间堆积和资源浪费。数学归纳法的强大可见一斑。

递归调用 & 数学归纳

看到这里，可能有人会觉得数学归纳法的证明方法和函数的递归调用很像。

我们再看上面数学归纳法的证明过程，可以用代码逻辑写出来。

第一步：如果 n 为 1，那么我们就判断麦粒总数是否为 2^1-1 = 1。同时，返回当前棋格的麦粒数，以及从第 1 格到当前棋格的麦粒总数。

第二步：如果 n 为 k -1 的时候成立，那么判断 n 为 k 的时候是否也成立，此时的判断依赖于前一格 k -1 的麦粒数、第 1 格到 k -1 格的麦粒总数。这也是上一步返回的两个值。

这两部就对应了数学归纳法的两种情况，在数学归纳法的第二种情况下，我怕们只能假设 n = k -1 的时候命题成立。但是在代码中，我们就可以进行一个递归调用，直到被调用的函数逐步返回 k – 1 时命题是否成立。

所以，我们可以看到，递归调用的代码和数学归纳法的逻辑是一致的。 一旦你理解了数学归纳法，就很容易理解递归调用了。

总结这篇的内容，递归把计算交给计算机，归纳把计算交给人，前者是拿计算机的计算成本换人的时间，后者是拿人的时间换计算机的计算成本。

另，这篇文章的知识点来源于极客时间，黄申的《程序员的数学基础课》 。