第 15 章 擬似言語プログラミング
科目B のプログラム問題を、トレースで読み解く。この章では次の 16 個の知識点を、解説・インタラクティブ教材・練習問題で学びます。
科目B の概要と読み方
科目B は 100 分で 20 問。そのうち 16 問がアルゴリズムとプログラミング（擬似言語で書かれたプログラムを読む問題）、4 問が情報セキュリティ。アルゴリズムの問題は大きく「空欄に入る式や文を選ぶ（空欄補充）」と「実行結果を求める（トレース）」の 2 タイプ。どちらも、まず「何を入れると何が出てくるプログラムか」をつかむのが第一歩。
宣言・型・注釈
○ で始まる行が手続・関数の宣言。○整数型: f(整数型: n) なら「整数を 1 つ受け取り、整数を返す関数 f」、戻り値の型がない ○p(…) は値を返さない手続。変数は 整数型: i のように型: 名前で宣言し、← 0 で初期値も付けられる。配列は 整数型の配列: a ← {1, 2, 3}、{} は要素数 0 の配列。どの関数からも使える変数は 大域: を付けて宣言する（大域変数）。/* … */ と // … は注釈で、処理には影響しないがヒントが書かれていることが多い。
順次処理と演算子
プログラムは上から 1 行ずつ実行される（順次）。x ← 式 は右辺をその時点の値で計算して x に入れる代入。演算子は + − × ÷ のほか、剰余の mod、商の整数部分を取る ÷ … の商、論理演算の and・or・not、比較の = ≠ < ≦ > ≧。優先順位は not → × ÷ mod → + − → 比較 → and → or。
選択処理（if 文）
if (条件1) … elseif (条件2) … else … endif は、上から順に条件を調べ、最初に true になった枝の処理だけを実行して endif の次へ進む。後ろの elseif に来た時点で「前の条件はすべて false だった」ことが分かっているので、条件を短く書ける。return は値を返してその場で関数を終える。
繰返し処理（while・do・for）
while (条件) … endwhile は先に条件を調べ、true の間くり返す（最初から false なら 1 回も実行しない）。do … while (条件) は先に 1 回実行してから条件を調べる。for (i を 1 から n まで 1 ずつ増やす) は i を 1, 2, …, n と変えながらくり返す（減らす なら逆向き）。途中で抜けるのが「繰返し処理を終了する」、その回の残りを飛ばして次へ進むのが「繰返し処理をスキップする」。
配列の操作
a[i] は配列 a の i 番目の要素。aの要素数 で長さ、aの末尾 に x を追加する で後ろに 1 つ増やせる。二次元配列は m[行, 列]、mの行数・mの列数 で大きさを得る。2 つの要素を入れ替えるには、片方を一時変数に退避してから上書きする（tmp ← a[i]、a[i] ← a[j]、a[j] ← tmp）。要素番号が 1 始まりか 0 始まりかで、最後の要素の番号（要素数 か 要素数 − 1 か）が変わる。
トレース（変数の値を追う）
トレースは、プログラムを 1 行ずつ実行したつもりで、変数の値の変化を表に書き出す技術。行に「実行した処理」、列に「変数」をとり、値が変わったときだけ書く。繰返しは「何回目か」と「条件の判定結果」も書く。科目B のすべての問題の土台で、空欄補充でも選択肢を当てはめたあとの確認に使う。
関数の呼出しと再帰
関数・手続を呼び出すと、呼び出された側を最後まで実行してから、呼び出した行の続きに戻る。戻り値はその呼出し式の値になる。関数の中で自分自身を呼び出すのが再帰。再帰には必ず呼び出さずに値を返す枝（終了条件）があり、引数が終了条件に近づくように呼び出す。値を求めるときは、終了条件から逆に積み上げると速い。
オブジェクト指向の擬似言語（クラス・インスタンス）
問題に出てくるクラスは、必ず説明の表（コンストラクタ・メンバ変数・メソッド）とセットで示される。Menu: m ← Menu("カレー", 800) でインスタンスを作って変数 m に入れ、m.price でメンバ変数、m.subtotal(2) でメソッドを使う。クラス型の変数に入っているのはインスタンスそのものではなく参照（どのインスタンスかを指す情報）なので、c ← a とすると c と a は同じインスタンスを指す。
リストのプログラム（追加・削除）
単方向リストの各要素は、値 val と次の要素への参照 next をもつインスタンス（クラス ListElement）。先頭は大域変数 listHead が指し、最後の要素の next は未定義。末尾への追加は「next が未定義の要素までたどって、その next に新しい要素をつなぐ」。削除は「1 つ前の要素の next を、消す要素の次（next.next）につなぎ替える」。先頭を消すときだけは listHead 自体を書き換える。
ビット演算のプログラム
∧（ビットごとの論理積）は取り出す、∨（論理和）は立てる・合成する、<<・>>（論理シフト）は位置をずらす操作。たとえば x ∧ 00000001 は最下位ビットだけを取り出し、(r << 1) ∨ b は r を 1 桁左へずらして空いた最下位に b を入れる。整数のまま mod 2ⁿ で下位 n ビット、÷ 2ⁿ の商 で右シフトと同じことができる（UTF-8 の符号化など）。
探索・整列・最大公約数のプログラム
科目B では、2分探索法・クイックソート・ビンソート・最大公約数などの定番アルゴリズムが、擬似言語で書かれて出題される。アルゴリズム自体を知っていると読むのが速いが、問われるのは「この書き方でどう動くか」。境界（low と high が隣り合ったとき、要素数が 1 や 2 のとき）でわざと動かしてみると、不具合や空欄の答えが見つかる。
データ構造のプログラム
スタック（後入れ先出し）・キュー（先入れ先出し）・優先度付きキューは、クラスのメソッド（push / pop、enqueue / dequeue）か、配列と「次に入れる位置」を表す変数で表される。2 分木は「子の番号の配列」や TreeNode クラスで表し、再帰で中間順などにたどったり、キューで幅優先探索をしたりする。ハッシュ表はハッシュ関数で格納位置を決め、衝突したら別の位置を探す（オープンアドレス法）。ヒープは親子の大小関係を保つように要素を入れ替える。
数値計算・文字列・統計のプログラム
問題文に計算式（ユークリッド距離、構成比、移動平均、チェックデジットなど）が示され、それをプログラムにしたときの空欄を問う形が多い。式の各部分（分子・分母・Σ の中身）が、プログラムのどの変数・どの繰返しに対応するかを線で結ぶように読むのがコツ。答えの確認には、問題文の具体例（「例えば…は 1.0 である」）をそのまま計算する。
ゲーム木の評価（ミニマックス法）
三目並べのように 2 人が交互に手を選ぶゲームでは、考えられる手をすべて展開したゲーム木で最善手を決める。葉（勝負がついた局面）に評価値（勝ち 10・引き分け 0・負け −10 など）を付け、自分の手番の節は子の最大値、相手の手番の節は子の最小値を、下から順に節の評価値とする（ミニマックス法）。相手は常に自分にとって最も不利な手を選ぶ、と考えるのがポイント。
グラフと動的計画法のプログラム
グラフ（頂点と辺）は、辺の両端を並べた辺の配列か、i 行 j 列に辺の有無や重みを入れた隣接行列（二次元配列）で表す。無向グラフの隣接行列は対称（[u, v] と [v, u] の両方に入れる）。最短距離は、すべての頂点の組について「k を経由した方が近ければ更新」を k = 1〜n でくり返すワーシャル–フロイド法や、近い頂点から確定していくダイクストラ法で求める。編集距離のように、小さな部分問題の答えを表に記録して積み上げる考え方が動的計画法。