アルゴリズムの基礎｜途中の状態を表にして追う

この分野で身に付けること

• 繰返しごとの変数と配列の状態を表に書ける。
• 添字の範囲と終了条件を、最初と最後の両方で確認できる。
• 探索・整列・累積和の処理目的を、状態変化から説明できる。

1. トレース表は、更新の前後を分けて書く

変数が増える、添字が進む、配列の要素が入れ替わる処理では、同じ行の中でも値が変わります。表の列を「ループ開始時」「条件判定」「更新後」に分けると、古い値と新しい値を混ぜずに追えます。特に代入が複数ある場合は、代入の順番どおりに行を増やします。

条件式は真か偽かだけでなく、何と何を比較しているかを残します。and、or、否定、不等号の境界は、数値を実際に入れて確かめると誤読が減ります。ループの回数と、条件を満たしたときだけ行う加算回数も別に数えます。

2. 添字は、どこからどこまでを含むかを見る

配列の要素番号が0から始まるか1から始まるか、両端を含む範囲かどうかは、問題ごとに確認します。二分探索なら、中央を調べた後にその要素を候補から除くため、leftやrightをmidの前後へ動かします。範囲が空になったときに終了することも表で確かめます。

累積和では、prefix[k]がどこまでの合計を表すかが定義の中心です。式を暗記するより、短い配列でprefixを実際に書き、区間の前までを引く理由を確認してください。添字が一つずれる原因は、番兵用の要素や終点を含むかどうかにあります。

3. データの並びと、たどる順序を区別する

連結リストでは、配列の物理的な並びではなく、nextなどのリンクをたどる順序が論理的な順序です。途中の参照を先に上書きすると、その後ろへ進む手掛かりを失うことがあります。挿入や削除は、つなぎ替える前に必要な参照を保存する手順で考えます。

整列では、何を比較し、どの要素を動かすかを小さな入力で追います。たとえば挿入ソートは、取り出した値を一時変数に保存し、大きい値を右へずらしてから空いた位置へ入れます。最終結果だけでなく、1回の外側ループでどこまで整列済みかを確認します。

用語・考え方の比較

例：7要素から16を探す二分探索を、3回の反復で追う

昇順の配列a = {2, 5, 8, 12, 16, 23, 38}からx = 16を探します。要素番号は1から7で、left・rightは両端を含む探索範囲です。midは(left + right) / 2の小数部を切り捨てます。以下は本教材用の擬似コードの読み方で、実際の言語の添字や整数除算の仕様とは区別します。

1. 処理は「left ← 1、right ← 7。left <= rightの間、midを計算する。a[mid] = xならmidを返して終了。a[mid] < xならleft ← mid + 1、それ以外ならright ← mid - 1。範囲が空になれば未発見」です。整列済みであることが、この範囲更新の前提です。
2. 1回目：left = 1、right = 7、mid = 4、a[4] = 12。12 < 16なのでleftを5にします。既に確認した4番目までを候補から除き、次の探索範囲は5〜7です。
3. 2回目：left = 5、right = 7、mid = 6、a[6] = 23。23 > 16なのでrightを5にします。6番目以降を候補から除き、次の探索範囲は5〜5です。
4. 3回目：left = 5、right = 5、mid = 5、a[5] = 16。探している値と一致するので、要素番号5を返します。調べた中央要素は順に12・23・16で、ループ本体は3回実行されました。
5. 未発見も検算します。同じ配列でx = 17なら、中央要素を12→23→16の順に調べた後、left = 6、right = 5となって終了します。この場合は本体3回、whileの条件判定4回です。値が見つかった場合の途中終了と区別してください。

ここで確認：left・right・mid・a[mid]の4列を毎回書くと、値16と要素番号5を混同せずに済みます。leftをmid、rightをmidのままにすると、最後の1要素で範囲が縮まらないことも具体的に確かめられます。

確認してから、演習へ進む

間違えやすいポイント

• whileの判定回数と、ループ本体の実行回数を同じものとしない。
• 更新後の添字を使う前に、更新前の値を記録する。
• 「以上」と「より大きい」、配列の端を含むかどうかを読み飛ばさない。

自分で確かめる三つの手順

1. 紙に列を作り、各ループで変わる変数だけを書く。
2. 一回の代入ごとに配列を写し、順番を省略しない。
3. 答えを出した後、別の小さい入力でも同じ手順を試す。

具体的なデータで、手を動かしてみよう

途中の表と解答を照合できる実習です。まず紙に自分の考えを書き、確認問題で条件を変えた場合も考えてみましょう。

• 連続達成回数を求める擬似言語を、一行ずつ追跡する（約25分）