程序员的数学课14 程序的循环：如何利用数学归纳法进行程序开发？

我们在上一讲提到程序有顺序、选择、循环这三大基本结构，而在这其中，循环是处理复杂运算最有效的一种结构。

循环结构可以用短短几行代码，执行成千上万次的运算。从计算机编程的视角来看，循环结构又有三种实现方法，分别是 for 循环、while 循环和 do while 循环；而从数学视角来看，循环结构很像是数学归纳法。

所以这一讲，我们就从数学的视角来重新看待循环结构。

从“多米诺骨牌”看循环归纳思想

在多米诺骨牌的游戏中，游戏者手动推倒第一个骨牌，接着第一个骨牌就会撞倒第二个骨牌，第二个骨牌还会撞倒第三个骨牌。以此类推，即使骨牌数量再多，也会逐一被放倒。

我们对多米诺骨牌全部放倒的结果进行剖析，你会发现它成立的条件有以下两个：

• 第一，对于任意第 i 个骨牌而言，它的倒下能带动第 i+1 个骨牌倒下；

• 第二，有一个参与游戏的人手动推倒第一个骨牌。

只要这两个条件都满足，就能让全部的骨牌都倒下。

“循环”的思想也存在我们的古文化中，《愚公移山》的“虽我之死，有子存焉。子又生孙，孙又生子；子又有子，子又有孙；子子孙孙无穷匮也。”简而言之就是，我有儿子，我儿子也有儿子，我儿子的儿子也会有儿子。以此类推，子子孙孙无穷尽。

在这其中不难发现，子子孙孙无穷匮的条件也有两个：

• 第一，任意一代男子（或者说是儿子），都要再生至少一个儿子；

• 第二，愚公有个儿子。

只要这两个条件都满足，就可以做到子子孙孙无穷匮也。

数学归纳法

对这两个例子的两个条件进行抽象，你会发现这就是高中学习的数学归纳法，下面我们用数学语言描述一下。

最简单常见的数学归纳法是，用来证明当 n 等于任意一个自然数时某个命题成立，其证明步骤可以分下面两步：

• 第一，当 n=1 时，命题成立；

• 第二，假设对于任意一个数字 i 命题成立，可以推导出在对于 i+1，命题依然成立。

只要这两个条件都满足，命题就得证。

例如，要证明所有的多米诺骨牌能倒下，也就是要证明游戏者手动推倒第一个骨牌，且任意一个骨牌倒下能带动下一个骨牌倒下。又比如，要证明愚公子孙无穷匮，也就是要证明愚公有儿子，愚公任意一代后代，至少有一个儿子。

接下来，我们利用数学归纳法来处理两个真实的数学问题。

【例 1】证明对于任意一个正整数 n，它的 2n 是偶数。

• 第一步，当 n=1 时，2n = 2×1 = 2 是偶数。

• 第二步，假设对于某个正整数 i 而言，2i 是偶数，则 2(i+1)=2i+2。其中 2i 为偶数，2 为偶数，两个偶数之和也是偶数，因此 2(i+1) 也是偶数。

根据数学归纳法可以知道，对于任意一个正整数 n，2n 是偶数，原命题得证。

【例 2】求证 1+3+5+...+(2k-1) = k²，我们依然可以用数学归纳法的思路来证明。

• 第一步，当 k=1 时，1=1² 成立。

• 第二步，假设对于任意一个正整数 i 而言，1+3+5+...+(2i-1) = i²，则 1+3+5+...+(2i-1)+[2(i+1)-1] = i²+[2(i+1)-1] = i²+2i+2-1 = i²+2i+1 = (i+1)² 原命题依然成立。

因此 1+3+5+...+(2k-1) = k² 这一原命题成立。

综上这两个例子，你会发现它们都是要证明“下一张多米诺骨牌”能够倒下，也就是在证明“i 推进到 i+1 的过程”。具体而言，这两个例子的第二步都分别在求证 2(i+1) 是偶数，以及 (i+1)² 成立，这种数学归纳的思想在循环结构中可以得以体现。

循环结构

程序中的循环结构完全可以用来表达数学归纳法，利用数学归纳法来处理的数学问题，可以被无缝迁移到一个循环结构的程序中。

我们在大学 C 语言的课程中曾经学过，循环结构的实现方法有三种，分别是 for 循环、while 循环和 do-while 循环。为了简洁，下面我们定义 s₁ 是初始表达式，s₂ 是条件表达式，s₃ 叫作末尾循环体，s₄ 是中间循环体，并将其代入这三个循环结构中，对比学习它们之间的联系与不同。

1.for 循环

for 循环的代码结构如下：

for(s1;s2;s3)
{
  s4;
}
1
2
3
4

如刚刚所定义的，s₁ 是初始表达式，s₂ 是条件表达式，s₃ 叫作末尾循环体，s₄ 是中间循环体。
for 循环的执行顺序是 s₁、(s₂,s₄,s₃)、(s₂,s₄,s₃)、...、(s₂,s₄,s₃)、s₂。

例如，求解 1 到 50 所有整数之和，可以用 for 循环这样编写代码：

int result = 0;
for(int i= 1; i <= 50; i++)
{
  result += i;
}
1
2
3
4
5

这段代码的 i=1 对应的是 s₁ 初始表达式，i≤50 对应的是 s₂ 条件表达式，i++对应的是 s₃ 末尾循环体，最后第 4 行运算对应的是 s₄ 中间循环体。
这段代码的执行顺序如下：

• 先执行 i=1，再判断 i≤50 与否，如果为真，则执行第 4 行的运算，最后执行 i++；

• 接着循环，再判断 i≤50 与否，如果为真，则执行第 4 行的运算，最后执行 i++；

• 经过多次循环后，再判断 i≤50 与否，直到结果为假，跳出循环结束。

for 循环还有很多变种，具体而言就是 s₁、s₂ 和 s₄ 都可以被省略或部分省略。围绕上面的例子，s₁ 的定义可以单独抽出来放在第 2 行；而 for 循环语句中，可以空出 s₁ 的部分，这样新的代码可以写作：

int result = 0;
int i= 1;
for(; i <= 50; i++)
{
  result += i;
}
1
2
3
4
5
6

根据代码执行的顺序，可以发现 s₃ 的执行永远是在 s₄ 之后。因此，可以把 s₃ 和 s₄ 写在一起，再把 s₄ 的位置空出来，这样新的代码可以写作：

int result = 0;
int i= 1;
for(; i <= 50; )
{
  result += i;
  i++;
}
1
2
3
4
5
6
7

同样，s₂ 的执行永远在 s₄ 之前，也就意味着s₂ 可以被放在循环体中的 s₄ 之前，而把 for 语句中 s₂ 的位置空闲出来。但最后一次的 s₂ 执行，还肩负着结束循环的任务，因此需要结合 if 条件判断语句和 break 语句，完成最后跳出循环的实现，这样新的代码可以写作：

int result = 0;
int i= 1;
for(; ; )
{
  if (i > 50){
   break;
  }
  result += i;
  i++;
}
1
2
3
4
5
6
7
8
9
10

2.while 循环

循环的另外一个实现方式是 while 循环，while 循环的代码结构如下：

while (s2)
{
  s4;
}
1
2
3
4

如刚刚所定义的，s₂ 是条件表达式，s₄ 是中间循环体。

while 循环的执行顺序是 (s₂,s₄)、(s₂,s₄)...(s₂,s₄)、s₂。具体而言，是首先判断 s₂ 是否成立，如果为真，则执行 s₄；继续循环判断 s₂ 是否成立，如果为真，则执行 s₄；如此循环多次后，直到 s₂ 不再成立，跳出循环结束。

我们继续使用 while 循环来实现 1～50 所有整数求和，代码如下：

int i = 0;
int result = 0;
while (i < =50)
{
  result += i;
}
1
2
3
4
5
6

同样地，如 for 循环一样，while 循环也有一些变种。具体而言，s₂ 也是可以被省略而用其他方法实现。从循环执行的顺序可以发现，s₂ 的执行总是在 s₄ 之前；而最后一次 s₂ 的执行，需要肩负起跳出循环的任务。

这就需要 if 条件语句和 break 语句了，这样变形之后的代码为：

int i = 0;
int result = 0;
while (1)
{
  if (i > 50){
    break;
  }
  result += i;
}
1
2
3
4
5
6
7
8
9

3.do while 循环

最后一种循环实现的方法是 do while 循环，do while 循环的基本结构如下：

do {
  s4;
}while(s2);
1
2
3

如刚刚所定义的，s₂ 是条件表达式，s₄ 是中间循环体。

do while 循环与 while 循环相比，区别就是执行顺序的调整。do while 循环中，无论 s₂ 是真是假，都会至少执行一次 s₄。这样它的执行顺序就是 (s₄,s₂)、(s₄,s₂)...(s₄,s₂)。

具体而言就是：先执行s₄，再来判断 s₂ 是真是假，如果为真，则执行 s₄；再来判断 s₂ 是真是假，如果为真，则执行 s₄；再来判断 s₂ 是真是假……如此循环多次之后，直到 s₂ 为假，跳出循环结束。

我们仍以 1～50 所有整数求和为例，看一下 do while 语句实现的代码：

int i = 1;
int result = 0;
do {
  result += i;
}while(i <= 49);
1
2
3
4
5

do while 循环也有一些变种，其 s₂ 语句也可以被调整到其循环体中，可以考虑用 if 条件语句和 break 语句实现：

int i = 1;
int result = 0;
do {
  result += i;
  if (i > 49){
    break;
  }
}while(1);
1
2
3
4
5
6
7
8

4.三种循环结构的区别

这三个循环的基本代码结构如下图所示，我们总结一下这三种循环结构的本质不同。

从代码执行的顺序来看，while 循环与 for 循环都是先判断条件，再执行循环体。在极端情况下，第一次判断条件就不成功，循环体就有可能一次也不被执行；而 do while 循环则相反，它先执行循环体，再判断条件，因此循环体至少会被执行一次。

从编码的视角来看，while 循环和 do while 循环，在条件判断的括号中只需要写循环条件；而 for 循环则循环变量赋初值、循环条件、循环变量改变方式都写在一起。

最后，从功能上来看，这三个循环结构完全一致，是可以彼此切换的。你可能会有这样的困惑：do while 循环至少会执行一次循环体，它如何能被其他循环结构替代呢？这就要借助 break 语句提前跳出循环体了，具体如何切换，我接下来就要讲解。

三种循环实现的切换

在不考虑代码结构的美观时，这三种循环语句可以在功能上实现彼此之间的切换，我们以 for 向 while 和 do while 的切换为例。

如下是任意一个for 循环语句：

for(s1;s2;s3)
{
  s4;
}
1
2
3
4

其执行顺序为 s₁、(s₂,s₄,s₃)、(s₂,s₄,s₃)...(s₂,s₄,s₃)、s₂。

它可以用下面的 while 循环语句来实现其功能：

s1;
while(s2)
{
  s4;
  s3;
}
1
2
3
4
5
6

根据 while 语句的执行顺序可知，这段代码的执行顺序为 s₁、(s₂,s₄,s₃)、(s₂,s₄,s₃)...(s₂,s₄,s₃)、s₂，因此可以得知，两段代码的功能结果完全一致。

而如果非要采用 do while 循环，可以按照如下方式实现：

s1;
do {
  if(!s2)
  {
    break;
  }
  s4;
  s3;
}while(1);
1
2
3
4
5
6
7
8
9

在这里，我们补充一下 break 语句的知识。break 语句的作用是，终止并跳出循环，继续执行循环语句后续的代码。

以上面的代码为例，一旦第 3 行的条件判断通过，则需要执行 break 语句。break 语句会帮助程序跳出当前循环，这样程序就会从第 4 行跳转至第 10 行继续执行。基于 break 语句，再根据 do while 语句的执行顺序可知，这段代码的执行顺序为 s₁、(s₂,s₄,s₃)、(s₂,s₄,s₃)...(s₂,s₄,s₃)、s₂，因此可以得知两段代码的功能结果完全一致。

这里要给大家提个醒：如果是在技术面试时，千万不要说某某功能的开发，只能用 for 循环、while 循环或 do while 循环，这一定是错的。因为，功能上这三种循环的实现是完全可以实现互换的；只不过，三者在代码美观上可能是有所区别。

数学归纳法与循环结构

数学归纳法和循环结构有很多相似之处，它们都是从某个起点开始，不断地重复执行某个或某组相似的动作集合。

不过，二者也有一些区别：

• 数学归纳法不关注归纳过程的结束，它就是用一种重复动作，由有穷尽朝着无穷尽的方向去前进；

• 而循环结构作为一种程序开发逻辑，则必须要关注循环过程的结束，否则就会造成系统陷入死循环或死机。

接下来，我们试着把一个数学归纳法的计算过程，用循环结构改写。为了让二者没有区别，我们对数学归纳法的问题增加一个截止条件的限制，那就是 k 小于 100 时。

这道例题是：证明在 k<100 时，1+3+5+... +(2k-1) = k² 成立。

我们说过，用数学归纳法来证明这个问题需要两个步骤，分别是：

• 证明 k=1 时等式成立；

• 假设 k=i 时等式成立后，k=i+1 等式依然成立。

我们把这两个步骤进行拆解。

令 s₁ 为 k=1，s₄ 为等式成立，s₃ 为 k=i 或 k=i+1，再补充题目的终止条件 k<100 为 s₂。这样，根据 for 循环执行的逻辑，把这些动作按照 s₁、(s₂,s₄,s₃)、(s₂,s₄,s₃)...(s₂,s₄,s₃)、s₂ 串联起来，就得到了基本的 for 循环代码框架。

• 在这个框架中，最开始的 s₁、s₂、s₄，即为当 k=1 时等式成立，对应数学归纳法的第一步。

• 在这个框架中，任意相邻的两组(s₂,s₄,s₃)、(s₂,s₄,s₃)，就是假设 k=i 时等式成立后，k=i+1 等式依然成立，对应数学归纳法的第二步。

也就是说，此时的数学归纳法证明和 for 循环实现，在功能上是等价的，我们给出 for 循环的代码如下：

int left = 0;
int left_temp = 0;
int right = 0;
for (int k = 1; k < 100; k++) // s1;s2;s3
{
    //s4
    left_temp = 2 * k - 1;
    left += left_temp;
    right = k * k;
    if (left == right)
    {
        printf("%d is right!\n",k);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

我们对代码进行走读：

• 代码的前三行定义了 3 个变量，分别是 left、left_temp 和 right，其中 left 和 right 分别用来存储等式两边的结果，left_temp 用来存储公式中每轮增加的一项；

• 第 4 行，进入 for 循环，得到对应的 s₁、s₂ 和 s₃；

• 第 6 行，计算出当前一轮的 left_temp 值；

• 第 7 行，把 left_temp 作为增量，增加到 left 的值中；

• 第 8 行，计算等式右侧的 k² 的值；

• 第 9 行，对等式左边和等式右边是否相等做出判断；

• 第 10～12 行进行判断，如果等式相等，打印结果，代码的部分执行结果如下图。

可见原命题得到证明。

小结

这一讲我们学习了数学归纳法的理论知识，以及循环结构的代码开发知识。然后我们从原理上分析了数学归纳法和循环结构的异同，介绍了 for 循环、while 循环和 do while 循环这三种循环结构的实现方法。

最后我们留一个练习题：本讲最后一个例题用 for 循环实现了等式的证明，请你试着分别用 while 和 do while 循环再次实现这段代码的功能。

下一讲，我们将学习《15 | 递归：如何计算汉诺塔问题的移动步数？》递归与循环之间有什么关联和区别吗？下周我会告诉你哦，别忘来听课～

---

精选评论