コンテンツへスキップ
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. 1 周目。条件 23≥723 \geq 7 は真なので、本体が実行される。rr は 16 に、qq は 1 になる。そのあと実行は 11 行目に戻る。

  3. 2 周目。16≥716 \geq 7 は真である。rr は 9 に、qq は 2 になる。

  4. 3 周目。9≥79 \geq 7 は真である。rr は 2 に、qq は 3 になる。

  5. 4 回目の計算 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 は、繰り返すものが何もない場合を、余分なコードなしに扱う。