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

设计正确的循环

摘要

循环一课教了如何写出重复；这一课教的是如何把它写对，并且知道它为什么是对的。本课从构成大多数循环的模式讲起（计数器、累加器、最大值与最小值、哨兵和标志），每一种模式都由它的变量在每一轮之后的含义来定义。这一观察引出核心概念：不变式，即关于变量的一个断言，它在第一轮之前和每一轮之后都成立，并且与退出条件一起蕴涵结果。这是对轮数的归纳，借助它，循环可以倒过来设计：先写最后应当成立的东西，再写不变式，最后才写循环体。终止性用变式来论证，变式已在从问题到算法一课中介绍过；本课还展示三个不终止的循环：一个使用实数条件，一个使用无符号计数器，还有一个的有符号计数器发生溢出，那是未定义行为。最后是与 Visual Studio Code 调试器的初次接触，它让程序停在某一行，并一轮一轮地显示程序的变量。

学习目标

  1. 在循环中识别计数器、累加器、最大值和哨兵这些模式，并用它们设计新的循环。
  2. 写出一个简单循环的不变式，并确认它在任意一轮中都得到保持。
  3. 用一个递减且有界的整数量来论证循环的终止性。
  4. 用 Visual Studio Code 的调试器，借助断点和变量视图，跟踪循环的执行。

模式

变量的含义

大多数循环不是发明出来的：它们由少数几种在所有程序中反复出现的部件拼装而成。每个部件都是一个变量，在循环之前有初始化，在循环之中有更新，更重要的是有一个在每一轮之后都成立的含义。按含义而不是按形式来认识这些部件，才能把它们组合起来而不出错。

  • 计数器的值是已经处理了多少个数据（或其中有多少个满足某个条件）。它初始化为 0，因为在第一轮之前一个数据也没有处理；它用 ++count 更新，并且只在有东西可数时才更新。
  • 累加器的值是已处理数据的组合：它们的和、它们的积。它初始化为运算的单位元（求和为 0，求积为 1），因为没有任何数据时，和是 0，积是 1。
  • 最大值的值是已处理数据中最大的那个，最小值则是最小的那个。没有任何数据时，最大值并不存在：所以它用第一个数据来初始化，而不是用一个随意选取的数。
  • 哨兵是输入中的一个值，它不是数据，而是数据已经结束的信号。这一模式要求在循环之前读一次，在循环体末尾再读一次，就像循环一课中累加到零为止的做法那样，这样条件会在每个值被处理之前先检查它，哨兵也永远不会被当作数据计入。
  • 标志是一个 bool，它表示在已处理的数据中某件事是否至少发生过一次。它初始化为 false，在这件事第一次发生时变为 true；之后的任何一轮都不会把它改回 false。

一个包含所有部件的例子

一份降雨记录记下每天降雨的毫米数。程序先读入一个阈值，然后读入若干天的测量值，以一个负数结束；负数不可能是测量值，正好用作哨兵。程序写出测量值的个数、它们的平均值、最大值、超过阈值的天数，以及是否有过无雨的日子。

C++ 程序
#include <iostream>#include <print>​int main(){    double threshold{};    std::cin >> threshold;    int count{0};          // 计数器：已处理的测量值    int aboveCount{0};     // 计数器：超过阈值的测量值    double total{0.0};     // 累加器：测量值之和    double largest{0.0};   // 最大值：仅当 count > 0 时有意义    bool dryDay{false};    // 标志：出现过无雨的日子    double value{};    std::cin >> value;    while (std::cin && value >= 0.0) {        if (count == 0 || value > largest) {            largest = value;        }        ++count;        total += value;        if (value > threshold) {            ++aboveCount;        }        if (value == 0.0) {            dryDay = true;        }        std::cin >> value;    }    if (count == 0) {        std::println("没有测量值。");    } else {        std::println("测量值：{} 个；平均：{:.2f} mm", count, total / count);        std::println("最大值：{:.1f} mm；超过 {:.1f} mm 的天数：{}", largest, threshold, aboveCount);        std::println("是否有无雨的日子：{}", dryDay ? "是" : "否");    }}
程序输入
104.5 0 12.5 21.5 7.5 -1
输出
测量值：5 个；平均：9.20 mm最大值：21.5 mm；超过 10.0 mm 的天数：2是否有无雨的日子：是

有四个决定值得说明。条件 count == 0 || value > largest 不用单独读取，就用第一个数据初始化了最大值：在第一轮中计数器为 0，赋值总会发生；在之后的各轮中，只有当数据超过最大值时才发生。比较 value == 0.0 是精确的，因为这个值是读入的，而不是计算出来的：数字 0 会被转换成精确的零，而浮点数一课对 == 的警告针对的是运算的结果。循环条件包含 std::cin，所以没有哨兵就结束的输入也会使循环终止。最后，只有在有测量值时才计算平均值：当 count 等于 0 时，total / count 将是 0/00/0，这在浮点运算中不是错误，而是“不是一个数”这个值，程序会不加任何提示地把它写出来。

例题一轮一轮看变量

证明

  1. 循环之前：阈值为 10，两个计数器和累加器都为 0，标志为假，并且第一个测量值 4.5 已经读入。最大值为 0，但只要 count 还是 0，这个值就没有任何意义。

  2. 第一轮：count 为 0，所以 4.5 成为最大值；计数器增加到 1，总和增加到 4.5。读入 0。

  3. 第二轮：0 没有超过最大值，但它把标志立了起来。读入 12.5。

  4. 第三轮：12.5 是新的最大值，并且超过阈值：aboveCount 增加到 1。读入 21.5。

  5. 第四轮：21.5 是新的最大值，也超过阈值。读入 7.5。

  6. 第五轮：7.5 既不改变最大值，也不改变 aboveCount；总和达到 46。读入 −1-1。

  7. 条件检查 −1-1，它是负数：循环没有处理它就终止了。平均值为 46/5=9.246 / 5 = 9.2。

请注意，在图的每一行中，每个变量相对于到那时为止已处理的测量值都符合它的含义：total 是它们的和，largest 是它们的最大值，dryDay 说明其中是否有过零。这个在每一轮之后都成立的性质，有一个名字。