用函数进行设计

摘要

前两课讲了函数是什么，以及它的数据如何进出；这一课讲如何决定要写哪些函数。方法是逐步求精：先写一个简短的 main，让它调用尚不存在的函数，每个函数都带有自己的契约，然后逐一深入每个函数，直到得到几行就能写完的部分。本课确立好接口的标准、“一个函数，一项任务”的规则及暴露违反这一规则的迹象，以及重载：它让不同类型上的同一项任务共用一个名字。凭借这些标准，本课改写第 4 单元中原本都写在 main 里的算法，并对它们分别测试。统一这一切的概念是自顶向下的分解：设计良好的程序读起来就像它自己的规格说明。

学习目标

用逐步求精把问题分解为子问题，并写出分解树。
在写函数体之前设计每个函数的接口（名字、参数、返回值和契约）。
把第 4 单元的一个整块程序改写成一组内聚的函数，并用测试用 main 对每个函数分别测试。
依据“一个函数，一项任务”的规则以及有无隐藏的作用来评判一个设计。
重载一个函数，预测每次调用选中哪个版本，并解释为什么某次调用有歧义。

逐步求精

从题目到几行的 main

第 4 单元的程序都整个写在 main 里。只要它们能放进一屏，这还可以容忍；然而，这样写成的两百行程序要求人同时把一切记在脑中，而且只能对整体进行测试。逐步求精，也称自顶向下设计，颠倒了工作的顺序：先用问题的语言写出程序做什么，写成对尚不存在的函数的一串调用；然后把其中每个函数当作一个新的、更小的问题，重复这一过程，直到得到简单到无需再分解就能写出函数体的函数。

下面的问题可作为例子。一个整数 $n \geq 1$ 称为完全数，如果它的真因数（异于 $n$ 的正因数）之和等于 $n$ ；和较小时称为亏数，较大时称为盈数： $28 = 1 + 2 + 4 + 7 + 14$ ，所以 28 是完全数；8（ $1 + 2 + 4 = 7$ ）是亏数；12（ $1 + 2 + 3 + 4 + 6 = 16$ ）是盈数。要编写一个程序，读入 $n$ ，写出它的真因数之和及其类别。设计的第一层是 main，它最先写出：

C++ 程序

#include <cstdint>#include <iostream>#include <print>#include <string>enum class Kind { deficient, perfect, abundant };// n 的所有正因数之和。// 前置条件：n >= 1。// 后置条件：返回 n 的所有正因数之和，包括 n 本身。std::int64_t divisorSum(int n);// 按真因数之和确定 n 的类别。// 前置条件：n >= 1。// 后置条件：依据该和小于、等于或大于 n，返回 deficient、perfect 或 abundant。Kind classify(int n);// 类别的名称，供输出用。// 前置条件：无。// 后置条件：返回“亏数”“完全数”或“盈数”。std::string kindName(Kind kind);int main(){    int n{};    std::cin >> n;    std::println("{} 的真因数：和为 {}", n, divisorSum(n) - n);    std::println("{} 是{}", n, kindName(classify(n)));}

链接器信息

/usr/bin/x86_64-linux-gnu-ld.bfd: main.o: in function `main':main.cpp:27:(.text+0x22a): undefined reference to `divisorSum(int)'/usr/bin/x86_64-linux-gnu-ld.bfd: main.cpp:28:(.text+0x3fd): undefined reference to `classify(int)'/usr/bin/x86_64-linux-gnu-ld.bfd: main.cpp:28:(.text+0x40d): undefined reference to `kindName[abi:cxx11](Kind)'collect2: error: ld returned 1 exit status

这个程序编译时没有任何警告，因为每次调用都与其声明一致，而这正是编译器唯一检查的东西，函数一课已经讲过。失败的是链接：链接器寻找定义却找不到（“undefined reference”，即未定义的引用；附加的 [abi:cxx11] 是 GCC 对返回 std::string 的函数所加的内部标记）。这种状态恰好就是设计此刻的状态：接口已经确定，函数体还没有。如果是这样，main 已经可以当作程序的规格说明来读，而三个声明就是待完成的任务，每一个都比原问题小。

分解树

第二层深入每一个声明。kindName 是一个三种情形的判断。classify 依靠 divisorSum：一个数是完全数，当且仅当它所有因数之和为 $2n$ 。而 divisorSum 就是成对 $(d, n/d)$ 枚举因数的循环（见数值算法一课），它在 $\sqrt{n}$ 处停止。结果画成一棵树：根是整个问题；每个结点的子结点是解决它的子问题；叶子是语言已经提供的运算。

例题整数分类器的树

图按照设计的顺序，一层一层地展开这棵树。

证明

第一层是整个问题，由 main 负责，尚未分解。
第二层是由五个操作组成的 main：读入、求和、分类、命名、输出。每个结点都是一次调用；库中的调用已经存在，其余的已声明、尚待完成。
第三层分解 classify，它只是调用 divisorSum 并进行比较。同一个函数在树中出现两次，却只写一次：在写代码之前，复用就已经在树中看得见了。
最后一层是叶子：整除判断和成对枚举的界限，都是语言本身的运算。到了这里求精就结束了，因为已经没有什么可分解的了。

树完成之后，自底向上写出各个定义，使每个函数都依靠已经写好的函数：

C++ 程序

#include <cstdint>#include <iostream>#include <print>#include <string>enum class Kind { deficient, perfect, abundant };// n 的所有正因数之和。// 前置条件：n >= 1。// 后置条件：返回 n 的所有正因数之和，包括 n 本身。std::int64_t divisorSum(int n){    std::int64_t sum{0};    for (int d{1}; d <= n / d; ++d) {        if (n % d == 0) {            sum += d;            if (d != n / d) {                sum += n / d;            }        }    }    return sum;}// 按真因数之和确定 n 的类别。// 前置条件：n >= 1。// 后置条件：依据该和小于、等于或大于 n，返回 deficient、perfect 或 abundant。Kind classify(int n){    const std::int64_t proper{divisorSum(n) - n};    if (proper < n) {        return Kind::deficient;    }    if (proper == n) {        return Kind::perfect;    }    return Kind::abundant;}// 类别的名称，供输出用。// 前置条件：无。// 后置条件：返回“亏数”“完全数”或“盈数”。std::string kindName(Kind kind){    if (kind == Kind::deficient) {        return "亏数";    }    if (kind == Kind::perfect) {        return "完全数";    }    return "盈数";}int main(){    int n{};    std::cin >> n;    std::println("{} 的真因数：和为 {}", n, divisorSum(n) - n);    std::println("{} 是{}", n, kindName(classify(n)));}

程序输入

输出

28 的真因数：和为 2828 是完全数

结果有三个特点源于这一方法。第一，写下层内容时 main 没有改变。第二，和以 std::int64_t 返回（来自 <cstdint>，即递归一课也要用到的 64 位整数），因为对于接近 int 最大值的 $n$ ，其因数之和可能超过它，在接口中作出这一决定就保护了所有调用者。第三，每个函数都单独检验：divisorSum(28) 应得 56，divisorSum(1) 应得 1，divisorSum(36) 应得 91，其中数对 $(6, 6)$ 只计一次；本课的最后一节把这些检验变成一个程序。

摘要

学习目标

逐步求精

从题目到几行的 main

分解树

您关于本课的疑问

关于本课的问题