コンテンツへスキップ
Topos Uranos
日本語

正しいループの設計

要約

レッスン ループ では繰り返しの書き方を学んだ。このレッスンでは、それを正しく書く方法と、なぜ正しいのかを知る方法を学ぶ。まず、大部分のループを組み立てるパターン（カウンタ、累積変数、最大値と最小値、番兵、フラグ）から始め、それぞれをその変数が各周回の後に何を意味するかによって定義する。この観察が中心となる概念に導く。不変条件、すなわち変数についての主張で、最初の周回の前と各周回の後に成り立ち、ループを抜ける条件と合わせて結果を導くものである。これは周回数についての帰納法であり、これを使うとループは逆向きに設計される。まず最後に成り立つべきこと、次に不変条件、最後に本体である。停止性は、レッスン 問題からアルゴリズムへ ですでに紹介した変量によって示す。さらにこのレッスンでは、停止しないループを三つ示す。実数の条件をもつもの、符号なしのカウンタをもつもの、そして符号付きのカウンタがオーバーフローするもので、最後のものは未定義動作である。締めくくりに Visual Studio Code のデバッガに初めて触れる。デバッガはプログラムをある行で止め、その変数を周回ごとに表示する。

学習目標

  1. ループのなかにカウンタ、累積変数、最大値、番兵のパターンを見分け、それらを使って新しいループを設計する。
  2. 簡単なループの不変条件を述べ、それが任意の周回で維持されることを確かめる。
  3. 減少し、かつ有界な整数の量によって、ループの停止性を示す。
  4. Visual Studio Code のデバッガで、ブレークポイントと変数のビューを使ってループの実行を追う。

パターン

変数が意味すること

大部分のループは発明されるものではない。あらゆるプログラムに繰り返し現れる少数の部品から組み立てられる。各部品は一つの変数であり、ループの前の初期化、ループのなかの更新、そして何よりも、各周回の後に成り立つ意味をもつ。部品を形ではなく意味によって知っていることが、それらを誤りなく組み合わせることを可能にする。

  • カウンタの値は、処理したデータの個数（あるいは、そのうちある条件を満たすものの個数）である。最初の周回の前には一つも処理していないので 0 で初期化し、数えるものがあるときにだけ ++count で更新する。
  • 累積変数の値は、処理したデータを組み合わせたもの、つまりその和や積である。演算の単位元（和なら 0、積なら 1）で初期化する。データが一つもないときの和は 0 であり、積は 1 だからである。
  • 最大値の値は処理したデータのうち最大のものであり、最小値の値は最小のものである。データが一つもないときの最大値は存在しない。だから最大値は最初のデータで初期化し、適当に選んだ数では初期化しない。
  • 番兵は入力に含まれる値で、データではなく、データが終わったことを示す合図である。このパターンでは、レッスン ループ で 0 まで合計したときのように、ループの前に一度、本体の最後にもう一度読む。こうすると、条件は各値を処理する前に調べることになり、番兵がデータとして数えられることはない。
  • フラグは、処理したデータのなかで何かが一度でも起こったかどうかを表す 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. 1周回目：count が 0 なので、4.5 が最大値になる。カウンタは 1 に、合計は 4.5 に増える。0 を読む。

  3. 2周回目：0 は最大値を上回らないが、フラグを立てる。12.5 を読む。

  4. 3周回目：12.5 は新しい最大値で、しきい値を超える。aboveCount は 1 に増える。21.5 を読む。

  5. 4周回目：21.5 は新しい最大値で、これもしきい値を超える。7.5 を読む。

  6. 5周回目：7.5 は最大値も aboveCount も変えない。合計は 46 に達する。−1-1 を読む。

  7. 条件は −1-1 を調べ、これは負である。ループはそれを処理せずに終了する。平均は 46/5=9.246 / 5 = 9.2 である。

図の各行で、それぞれの変数が、その時点までに処理した測定値に対して自分の意味を満たしていることに注意しよう。total はそれらの和、largest はそれらの最大値であり、dryDay はそれらのなかにゼロがあったかどうかを表す。各周回の後に成り立つこの性質には名前がある。