whileのトレース
同じ行を何度も通ります
分岐では行を飛ばしました。繰返しでは、同じ行を何度も通ります。トレース表の行番号の列に同じ番号が繰り返し現れるようになり、表は一気に縦に長くなります。ここが科目 B の山で、そして得点源でもあります。
while は「条件を確かめてから入る」
擬似言語の while は次の形です。
while (n < 20)
n ← n × 2
endwhile動きは 3 段階です。まず丸括弧の中の条件を評価します。真なら中身を上から実行し、endwhile まで来たら条件の行へ戻ります。偽なら中身をまるごと飛ばして endwhile の次の行へ抜けます。
大切なのは、条件が確かめられるのが中身に入る前だという点です。最初から条件が偽なら、中身は 1 回も実行されません。逆に、少なくとも 1 回は実行してから判定したいときのために do と until の組が用意されています。この違いは科目 A でもそのまま問われます。
終わるのは、条件が偽になったときだけ
while が終わる理由は 1 つしかありません。条件の行に戻ってきたときに、その条件が偽になっていることです。したがって中身のどこかで、条件に使われている変数が必ず変化していなければなりません。上の例なら n が 2 倍されるので、いつかは 20 以上になって止まります。もし中身から n の書き換えが消えたら、条件は永久に真のままで、繰返しは終わりません。これが無限ループです。
トレースするときは、コードを読み始めた最初の段階で「条件に出てくる変数はどこで変わるか」を目で追って確かめてください。そこが分かれば、何回まわるかの見当が先に付きます。
回数の数え方
何回まわるかは、条件が偽になる直前までを数えます。上の例で n が 1 から始まるなら、n は 1、2、4、8、16、32 と変化します。中身に入るのは条件が真だったときなので、n が 1、2、4、8、16 の 5 回です。n が 32 になって条件の行へ戻った時点で偽になり、そこで抜けます。32 になった回は中身を実行していないという点に注意してください。ここを 1 回多く数える間違いが、繰返しの問題でいちばん多い失点です。
表は 2 周目まで書けば十分です
実際の試験では 10 回以上まわるコードも出ます。全部を書いていると時間が足りません。1 周目と 2 周目をきちんと書いて、変数がどう変化する規則なのかを掴んだら、あとはその規則で最後まで一気に計算します。規則が読めていれば、10 周でも 100 周でも同じ手間で終わります。書くのは規則を掴むまで、と決めておいてください。
やってみます
下の演習は、1 から始めて 2 倍を繰り返し、20 以上になるまでに何回かかるかを数えるコードです。条件の行も 1 行として表に現れます。2 周目まで追いかけたら、あとは規則で最後まで進めてください。
課題
- 各行を実行したあとの値を入れる
- 値が変わらない変数はそのままの値を入れる
- 条件の行も 1 行として数える