擬似言語のトレース｜代入・ループ・配列・関数を実行順に追う

プログラムの空欄を埋めるとき、変数の名前から意図を推測するだけでは境界の誤りを見逃します。代入の直前と直後、条件を判定する時点、配列の有効な添字を一行ずつ記録すれば、短いプログラムの動きを確かめられます。

この記事で理解すること

• 代入と比較、条件分岐と繰返しを、実行時の状態として追跡する。

• 配列の添字・要素数・最後の位置を区別して境界を確認する。

• 関数の引数と戻り値、参照される配列を呼出し元と対応付ける。

架空の倉庫で、出庫数の配列から累計を求め、累計が目標に届いた最初の位置を返す処理を使います。擬似言語はこの記事独自の表記です。配列は0始まり、nは要素数、divは整数の商、←は代入と定義します。IPAの問題では、その問題に指定された文法・添字・丸め方を優先します。

変数と代入：式を評価してから値を書き換える

変数は処理中の値を保持する名前です。x ← x + 1は、右辺を現在のxで計算し、その結果を左辺xへ格納します。数学の等式のように、同時に左右が等しいという主張ではありません。比較のx = 1とは働きが異なります。

x ← 2
y ← x
x ← x + 3
結果：xは5、yは2

この例の数値代入は値を写すため、後でxを変えてもyは変わりません。一方、配列やオブジェクトが参照を共有する方式では、一方を通した変更が他方から見える場合があります。数値の代入の例を、あらゆるデータ型へ無条件に一般化しないようにします。

二つの値を交換するなら一時変数が必要です。x ← yの後にy ← xとすると、元のxは既に失われています。tmp ← x、x ← y、y ← tmpの順序で、保存した値を使います。

条件分岐：判定時点の値で経路を選ぶ

ifは条件が真なら指定した処理へ進み、偽なら別の処理へ進みます。複数の独立したifと、if・else ifの連鎖は違います。独立したifは前の処理で値が変わった後に次の条件を判定するため、両方が実行されることがあります。

たとえばxが0のとき「x = 0ならxを1へ」の後に独立した「x = 1ならxを2へ」があれば、結果は2です。else ifなら最初の分岐を実行した時点で後の候補を選ばず、結果は1です。字面が似ていても、制御の構造を確認します。

累計のループ：配列と更新の順序を表にする

firstReached(A, n, target)
  sum ← 0
  i ← 0
  while i < n
    sum ← sum + A[i]
    if sum >= target
      return i
    i ← i + 1
  return -1

入力をA = [2, 0, 3, 1]、n = 4、target = 4とします。添字は0から3です。各回で要素を累計へ加え、その後に目標到達を判定します。到達した時点でreturnすると関数全体を終了し、残りの要素は読みません。

結果の2は、0始まりの添字です。「三つ目の要素」と同じ位置でも、個数3という値とは区別します。ループの最初の状態だけでなく、加算と判定の順序も追うことが必要です。

境界条件：0、1、末尾、未発見を試す

要素数がnなら、有効な添字は0からn−1です。この表記でi <= nを条件にすると、未発見のまま進んだ場合にA[n]を読もうとします。配列外アクセスは、言語によって例外や不正動作の原因になります。i < nという境界と、iを増やす位置を一組で確認します。

空配列ではn = 0なのでループへ入らず−1を返します。一要素だけなら、その要素を読んで判定するか、未発見で終了します。末尾で到達する場合と、どこでも到達しない場合も確認します。典型的な入力で動いても、境界で正しいとは限りません。

この関数はtargetが正で、各出庫数が0以上という条件を置きます。累計が目標に達していないことから後の可能性を考えるときは、この非負条件が重要です。負の数を許す問題へ条件を持ち込まないようにします。targetが0の場合に開始前の到達を扱いたいなら、仕様と処理を別に定めます。

ループ不変条件：今までに何を処理したか

ループ不変条件は、各回の決まった時点で成り立つ性質です。この処理ではループ開始時にsumがA[0]からA[i−1]までの合計であり、まだ到達していないから次の回へ来ています。i = 0なら処理済みの要素はなく、合計は0です。

A[i]を加えた後のsumはA[0]からA[i]までの合計です。判定に失敗してiを一つ増やすと、次の開始時も同じ性質が成り立ちます。「初期値」「一回の更新」「終了時」をつなぐと、ただ値を並べるだけでなく処理の正しさを説明できます。

不変条件の時点を曖昧にすると、i番目を含むのか含まないのかが逆になります。文章で説明するときも「加算前」「加算後」を明示します。

関数・引数・戻り値：呼出しごとに状態を分ける

関数は入力を受けて処理をまとめる単位です。呼出し元のfirstReached(A, 4, 4)が、この関数のA、n、targetへ対応します。戻り値2は呼出し元の式の結果になります。sumやiはこの呼出しのローカル変数として扱います。

ここでは配列Aは読取専用とし、nは配列の要素数と等しい前提です。nが配列より大きいと配列外を読み、小さいと一部しか調べません。実装では要素数を配列から得る方式もあります。引数が渡されたから正しいとせず、入力の前提も点検します。

returnとbreakは同じではありません。returnは関数を終了し、breakは通常、対象のループから抜けて後続処理へ進みます。関数を何度も呼ぶ場合は毎回の初期化を確認し、前回のsumを引き継いでいると推測しないようにします。

トレース表の作り方

最初に配列の添字規則、初期値、整数計算、入力の制約を欄外へ書きます。次に、一行で状態が変わる変数だけを更新します。最後に、条件の真偽と移動先を記録します。空欄候補は、開始時の意味を維持し、末尾まで安全に進むかで比較します。

探索の構造やキュー・スタックはデータ構造の記事、計算量と整列はそれぞれの主担当記事へ分けます。このトレースの方法は、それらを読んだときにも使えますが、ここで全アルゴリズムの定義を重ねることはしません。

演習1：代入の値

条件：xは2。y ← xの後にx ← x + 3を行う。値を写す数値代入とする。

問い：最後のxとyを答える。

解答例：xは5、yは2。yへ写した値は、その後のxの更新で変わらない。

根拠と誤答の確認：代入を数学の等式や参照の共有と混同しません。

演習2：目標到達

条件：A = [2,0,3,1]、n = 4、target = 4。上の関数を使う。

問い：返す値と、終了直前のsumを答える。

解答例：戻り値は2、sumは5。添字2の3を加えた後に到達する。

根拠と誤答の確認：要素の個数3と添字2を混同しません。

演習3：未発見

条件：A = [1,1]、n = 2、target = 3。

問い：返す値は何か。

解答例：−1。全要素を加えた合計2でも到達しないため。

根拠と誤答の確認：存在しない添字2を返す設計ではありません。

演習4：空配列

条件：A = []、n = 0、target = 1。

問い：配列を読むか。戻り値も答える。

解答例：読まない。最初のi < nが偽なので−1を返す。

根拠と誤答の確認：空の場合のA[0]読取りが発生しないことを確認します。

演習5：終了する範囲

条件：ループ内のreturn iをbreakに置き換え、最後のreturn −1はそのままにする。

問い：到達した場合も同じ戻り値になるか。

解答例：ならない。ループを抜けた後、最後のreturn −1へ進むため。

根拠と誤答の確認：関数を終了する処理とループを終了する処理は別です。

演習6：累計の意味

条件：上の処理のループ開始時、iは2、A = [2,0,3,1]。

問い：その時点のsumが表す範囲と値を答える。

解答例：A[0]からA[1]までの合計で2。A[2]はこれから加える。

根拠と誤答の確認：加算後の5を、開始時の値として答えないようにします。

参照資料とこの記事の範囲

事例・図・演習は教材用に独自に作成しました。公式・教育機関の資料で仕組みを確認し、特定年度の問題本文を前提にせず学べる構成にしています。

Python公式 チュートリアル：数値・代入・リスト

Python公式 制御フロー・関数

IPA APシラバス

関連テーマを続けて学ぶ

データ構造と探索｜スタック・キュー・二分探索木・AVL・BFSを図で理解する

記述式の設問と本文根拠の読み方