入れ子のトレース

繰返しの中に繰返しが入ります

章の最後は入れ子です。繰返しの中に、さらに別の繰返しが置かれた形を入れ子と呼びます。二次元の表を走査するときや、すべての組合せを試すときに必ず出てくる形で、科目 B では避けて通れません。

外側が i、内側が j です。字下げと、endfor がどちらと対応しているかで、どこまでが内側かを見分けます。行数が増えてくると対応を取り違えやすいので、問題用紙の上で外側と内側を線で囲ってから読み始めるとよいです。

内側が先に回り切ります

入れ子の動きは 1 つの言い方に集約できます。外側が 1 周する間に、内側は最初から最後まで回り切るです。上の例なら、i が 1 のあいだに j が 1 と 2 の 2 周を終え、それから i が 2 になります。

したがって中身が実行される回数は、外側の回数と内側の回数の掛け算です。外側 3 回、内側 2 回なら 6 回です。トレースを始める前にこの数を出しておくと、途中で自分が今どこにいるのかを見失いません。

内側の変数は毎回はじめに戻ります

いちばん間違えやすいのがここです。内側の for は、外側が 1 つ進むたびに新しく開始されます。つまり j は、外側が進むたびに開始の値へ戻ります。1、2 と進んだ j が、次に外側へ戻ったときに 3 から続くことはありません。また 1 からです。

トレース表では、外側の for の行を実行した直後、j の欄には前の周の最後の値がまだ残っています。内側の for の行を実行して初めて j が開始の値に戻ります。表を 1 行ずつ書いていれば、この動きがそのまま目に見えます。

どこまで書くかを決めておきます

入れ子は表が長くなります。6 回程度なら全部書いても構いませんが、外側 10 回で内側 10 回のような形では 100 行になり、書き切れません。方針は前回と同じです。外側の 1 周目を内側まで全部書き、外側の 2 周目に入って内側が最初へ戻る瞬間まで書きます。ここまで書けば動きの規則は完全に見えているので、あとは掛け算と足し算で最後まで進めます。

配列が絡む問題では、内側と外側のどちらの変数が添字に使われているかで意味が変わります。i が行、j が列という形が多いのですが、決まりではありません。必ずコードを見て確かめてください。次の章から、その添字の扱いに入ります。

やってみます

下の演習は、中身が何回実行されるかを数えるだけのコードです。外側の 2 周目で j がどうなるかに注目してください。

1. 各行を実行したあとの値を入れる
2. 値が変わらない変数はそのままの値を入れる
3. 内側の for に入るまで j の値は前のままにする