トレース表を作る
変数ごとに列を作り、代入が起きるたびに新しい値を下に書き足します。繰返しの変数(i など)も列に入れると、何回目の繰返しかを見失いません。例えば、一の位を取り出して足していくプログラムでは、x が4096、409、40、4、0と変わる間に、合計の s が0、6、15、15、19と変わります。
値が変わらない回も飛ばさずに書きます。足す値が0の回(4096の百の位)でも、繰返しは1回進んでいます。
空欄の問題は小さな入力で試す
空欄に入る答えを選ぶ問題では、問題文の説明に合う小さな入力を一つ決め、選択肢を一つずつ空欄に入れてトレースします。要素数1や2の配列、0や1のような境界の値を使うと、誤りの選択肢はすぐに崩れます。
例えば2分探索で範囲の下端を更新する空欄に low ← mid を入れると、low と high が隣り合ったときに mid が変わらず、繰返しが終わらなくなります。探す値が見つからない場合を一度試すだけで、正しい low ← mid + 1 と区別できます。
境界を確かめる
誤りが入りやすいのは、繰返しの最初と最後、配列の先頭と末尾、空の配列、リストの末尾です。for の終了値が含まれるか、while の条件が < か ≦ か、要素番号が要素数を超えないかを、一番端の値で確かめます。
再帰では、引数がどう変わって終了の条件に届くかを先に確かめます。g(n) が g(n - 1) と g(n - 2) を呼ぶ関数では、g(5) の呼出しは全部で15回になり、同じ引数での呼出しが何度も繰り返されます。
出題範囲の題材
IPAの試験要綱は、科目Bの出題範囲に、再帰、スタック、キュー、木構造、グラフ、連結リスト、整列、文字列処理などのデータ構造とアルゴリズムを挙げています。当サイトの練習問題は、これらの題材に、変数と制御構造、配列、計算量、数値計算、オブジェクト指向の問題を加えて分野別に並べています。
まずはアルゴリズムとプログラミングの練習問題 セット1を時間制限なしで解き、解説のトレースと自分のトレースを比べてみましょう。
時間配分
本番は20問を100分で解くので、1問あたりの平均は5分です。トレースに時間がかかりそうな問題は印を付けて後に回し、全体を一度見通してから戻ると、解ける問題を取りこぼしません。