関数による設計

段階的詳細化

問題文から数行の 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 であり、ほかの何よりも先に書く。

#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] は、std::string を返す関数に GCC が付ける内部的な印である）。この状態は、この時点での設計の状態そのものである。インタフェースは決まっているが、本体はまだない。そうであれば、main はすでにプログラムの仕様として読め、三つの宣言は残された仕事であり、どれも元の問題より小さい。

分解の木

第二段階では各宣言へ降りていく。kindName は三つの場合の判断である。classify は divisorSum に頼る。数が完全数であるのは、そのすべての約数の和が $2n$ のときである。そして divisorSum は、約数を $(d, n/d)$ の組で調べるループ（レッスン 数値アルゴリズム のもの）であり、$\sqrt{n}$ で止まる。結果は木として描かれる。根は問題全体、各節点の子はそれを解く部分問題、葉は言語がすでに用意している演算である。

木が完成したら、下から上へ定義を書いていく。こうすれば、どの関数もすでに書かれた関数に頼ることになる。

#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

28 の真の約数：和は 2828 は完全数

結果の三つの特徴は、この方法によるものである。第一に、下の部分を書いている間、main は変わらなかった。第二に、和は std::int64_t として返される（<cstdint> にある 64 ビットの整数で、レッスン 再帰 でも使う）。$n$ が int の最大値に近いと約数の和がそれを超えうるからであり、それをインタフェースで決めておけば、呼び出し側すべてが守られる。第三に、各関数は別々に確かめられる。divisorSum(28) は 56、divisorSum(1) は 1、divisorSum(36) は 91 にならなければならず、最後の場合には組 $(6, 6)$ を一度だけ数える。このレッスンの最後の節で、これらの確認をプログラムにする。