跳至内容
Topos Uranos
中文 (中国)

循环

摘要

从问题到算法一课辨认出组合步骤的三种方式：顺序、选择和重复。前两种在 C++ 中已经有了自己的写法；本课为第三种给出它的写法。本课研究循环的三种形式：while 在每一轮之前对条件求值，可能一次也不执行循环体；do 在之后求值，至少执行一次循环体；for 把初始化、条件和支配重复的那个变量的步进汇集在一行里。本课说明这三种形式表达的是同一个机制，因此每一种都能变换成另外两种，并教人选择最清楚的一种；介绍改变一轮进程的 break 和 continue；最后讲嵌套循环，其内层循环体的执行次数要用一个求和来计算。贯穿全课的工具是跟踪表：手工执行一个循环，一轮一轮地跟下去，就能预测循环体执行多少次，以及循环退出时留下什么。

学习目标

  1. 为给定的重复编写 while、do 或 for 循环，并选择最清楚的形式。
  2. 用跟踪表手工执行一个循环，并预测循环体执行的次数。
  3. 把循环从一种形式变换为另一种形式，同时保持其含义。
  4. 编写嵌套循环，并计算内层循环体执行的次数。

while

while 的形式

while 这样写：

C++ 代码
while (条件) {    循环体}

它的含义分三步表述：对条件求值；若为假，循环终止，执行从关闭它的花括号之后继续；若为真，执行循环体，然后回到第一步。循环体的每一次执行称为一轮（或一次迭代）。条件是像关系与逻辑一课中那样的布尔表达式，循环体是一个块；判断一课确立的花括号规则在这里同样适用：循环体总是带花括号，即使它只含一条语句。

由定义可以得出两个推论。第一，条件在每一轮之前求值，所以如果它一开始就为假，循环体一次也不执行。第二，要让循环终止，循环体必须改变条件所读取的某样东西；如果什么都不变，曾经为真的条件将永远为真。然而，改变还不够：从问题到算法一课说明了，需要一个每一轮都减小的自然数量，即变式，而设计正确的循环一课将把它变成一种方法。

连续减法求商

本课程中第一个带重复的算法是连续减法求商：只要余数不小于除数，就从余数中减去除数，并给商加一。用 C++ 写出来，这个算法几乎可以逐字照搬。

例题用减法求商和余数
C++ 程序
#include <iostream>#include <print>​int main(){    int a{};    int b{};    std::cin >> a >> b;    int q{0};    int r{a};    while (r >= b) {        r -= b;        ++q;    }    std::println("{} = {} · {} + {}", a, b, q, r);}
程序输入
23 7
输出
23 = 7 · 3 + 2

第 9 行和第 10 行给变量赋初值：还没有减去任何东西，所以商是 0，余数是整个被除数。第 11 行是算法第 2 步的条件；第 12 行和第 13 行是循环体。程序和算法一样，假定 a≥0a \geq 0 且 b>0b > 0：若 b=0b = 0，第 12 行不会改变 r，循环也不会终止。

跟踪表

手工执行循环就是填一张表：每一轮一行，每个变量一列，再加一列记录条件，在该轮开始时求值。第 0 行记录第一次求值之前的状态；最后一行记录结果为假、使循环终止的那次求值。

例题23 除以 7 的跟踪

证明

  1. 循环之前执行第 9 行和第 10 行：q=0q = 0，r=23r = 23。这是第 0 行；条件还没有求值。

  2. 第一轮。条件 23≥723 \geq 7 为真，所以执行循环体：rr 变为 16，qq 变为 1。然后执行回到第 11 行。

  3. 第二轮。16≥716 \geq 7 为真：rr 变为 9，qq 变为 2。

  4. 第三轮。9≥79 \geq 7 为真：rr 变为 2，qq 变为 3。

  5. 第四次求值 2≥72 \geq 7 为假：循环体不执行，循环终止，第 15 行写出 23=7⋅3+223 = 7 \cdot 3 + 2。

跟踪教人计数。循环体执行了三次，与商相等，而条件求值了四次：每轮一次，再加上失败的那一次。这个关系对每个因条件而终止的 while 都成立：若循环体执行 kk 次，条件就求值 k+1k + 1 次。极端情形也证实了这一点：输入 5 7 时，第一次求值 5≥75 \geq 7 就已为假，循环体执行零次，程序写出 5=7⋅0+55 = 7 \cdot 0 + 5，这是正确的。写得好的 while 不需要额外代码，就能处理没有东西需要重复的情形。