基本情報 科目Bのアルゴリズム：擬似言語をトレース表で読む

この記事は基本情報のセキュリティの続きで、科目Bの残りの8割にあたるアルゴリズムとプログラミングを扱います。順次・分岐・反復やフローチャートのような基礎はアルゴリズムの基本に、共通テスト「情報I」の出題範囲は共通テスト「情報I」対策まとめにまとめています。ここではその先の、試験の擬似言語を正確に追う方法に絞ります。

科目Bで問われること

2023年4月からの基本情報技術者試験では、科目Bは20問で、そのうち16問がアルゴリズムとプログラミング、4問が情報セキュリティです（IPAの試験要綱による）。アルゴリズムとプログラミングの問題では、擬似言語で書かれたプログラムが示され、主に次の形で問われます。

• プログラムの空欄に入れる字句を選ぶ
• ある引数で呼び出したときの戻り値や、処理を終えたあとの配列の中身を選ぶ
• ある行が何回実行されるか、繰り返しが何周するかを選ぶ

どの形でも、やることは同じです。プログラムを1行ずつ実行したつもりになり、変数の値がどう変わるかを追います。アルゴリズムの名前を知っていると見通しは立ちますが、答えを決めるのは、問題のプログラムを実際に追った結果です。名前を知っている処理でも、問題ごとに配列の始まりや境界の扱いが少しずつ違うからです。

IPAは、2027年度から新しい試験制度を始める予定を公表しており、基本情報技術者試験のシラバス案も2026年9月に掲載されました。この記事は2026年度時点の制度で書いています。受験する回の出題範囲と出題数は、IPAの基本情報技術者試験のページと新試験制度のシラバス案のページで確認してください。

擬似言語の記述形式

試験の擬似言語は、IPAの「試験で使用する情報技術に関する用語・プログラム言語など」の別紙2「擬似言語の記述形式」で書き方が決まっています。問題文に注記がない限り、この形式で書かれていると考えて読みます。

読み違えやすいのは、繰り返しの判定の位置です。while は条件を先に調べるので、最初から偽なら処理は0回です。do 〜 while は処理を先にするので、条件が最初から偽でも1回は実行します。練習問題の問4は、この違いだけで答えが変わる問題です。

演算子の優先度

式の中に演算子が並んだときは、優先度の高いものから計算します。記述形式では次の順です。

mod は割り算の余りで、× や ÷ と同じ優先度です。3 + 17 mod 5 は、先に 17 mod 5 の2を求めて5になります。and が or より先なので、p or q and r は p or (q and r) と読みます。論理型の定数は true と false です。

配列と未定義

配列の要素は a[3] のように [ ] に要素番号を書いて参照し、二次元配列は b[行, 列] の順に書きます。配列の中身をまとめて書くときは {3, 8, 2} のように { } で囲みます。二次元配列なら、内側の { } が1行分です。変数に値が入っていない状態は「未定義」と呼び、「未定義の値」を代入するとその変数は未定義になります。

配列の要素番号が0から始まるか1から始まるかは、記述形式では決まっていません。各問題の注記（「配列の要素番号は1から始まる」など）で示されます。1から始まる問題が多いのですが、0から始まる配列に慣れていると、最後の要素を1つずれて読みがちです。読み始める前に、注記を必ず確かめます。この記事のコードは、どれも要素番号を1から数えます。

記述形式の表には載っていなくても、問題では決まって使われる書き方があります。関数の戻り値を返す return、配列の要素の数を表す aの要素数、○整数型: gcd(整数型: num1, 整数型: num2) のような戻り値と引数の型を付けた宣言、for (i を 1 から n まで 1 ずつ増やす) の制御記述です。どれもIPAが公開している科目Bのサンプル問題で使われており、この記事のコードも同じ書き方にそろえています。整数どうしの ÷ の結果を整数にするかどうかは記述形式では決まっていないので、サンプル問題と同じく、商だけを使う場面では (low + high) ÷ 2 の商 のように書いて示します。試験でも、こうした細かな約束は問題文で説明されるので、問題の前置きの文章を読み飛ばさないようにします。

DNCLとの違い

共通テスト「情報I」のプログラム表記（DNCL）を学んだ人は、考え方の大部分をそのまま使えます。分岐も繰り返しも配列も同じ働きです。違うのは記号で、とくに = の役目が入れ替わる点で引っかかります。下の表の左の列は、このサイトのプログラムのなぞり書きで動く書き方です。

情報Iを学んだ人が最初に引っかかるのは、if (a[i] = x) を「代入してしまう」と読むことです。基本情報の擬似言語で代入は ← だけなので、= は必ず比べる記号です。逆の向きの失敗もあります。DNCLの字下げに慣れていると、endif や endwhile の位置を見ずに字下げだけで範囲を判断しがちです。範囲は終わりの印で確かめます。もう一つは要素番号で、プログラムのなぞり書きの例題は0から数えますが、基本情報の問題は注記で示された番号から数えます。

トレース表の書き方

トレース表は、プログラムを実行したときの変数の値の移り変わりを、表に書き出したものです。列に変数を並べ、繰り返し1周を1行にします。条件式を調べた結果（真か偽か）の列も作ると、どこで繰り返しを抜けたかが表に残ります。次の関数で試します。

○整数型: sumOdd(整数型: n)  整数型: s, k  s ← 0  k ← 1  while (k ≦ n)    s ← s + k    k ← k + 2  endwhile  return s

sumOdd(7) を呼び出したとして、3行目と4行目を実行した直後を「開始前」の行に、5行目から7行目までの1周を1行に書きます。

戻り値は16です。表にしたことで、4周目の判定 7 ≦ 7 が真になることがはっきりします。頭の中で追うと、ここを「7まで来たから終わり」と読んで、9を答えてしまいます。≦ か < かで周の数が1つ変わるので、この判定は必ず値を当てはめて確かめます。

書くときの決まりは、次の三つで足ります。

1. 値が変わる変数だけを列にする。一度も変わらない n のような引数は、表の上に1回書けばよい。
2. 代入した直後の値を書く。同じ周の中で2回変わる変数は、列を2つに分ける。
3. 条件式は、値を当てはめた形（7 ≦ 7）と真偽を書く。繰り返しを抜けた判定も1行として残す。

表を全部埋める必要はありません。上の例なら、2周ほど書けば「s は奇数を順に足した値、k は次の奇数」という規則が見えます。規則が見えたら残りの周は計算で済ませ、最後の周と、繰り返しを抜ける判定だけをもう一度表で確かめます。

よく出る処理の型

ここからは、科目Bでよく使われる処理を、短いオリジナルのコードと「どこを見るか」で整理します。型を知っていれば、初めて見るプログラムでも「この部分は最大値を探している」と見当を付けてから細部を追えます。ただし、型に当てはめて決めつけるのは危険です。問題のコードは、境界や比べる向きを少し変えてあることがあります。

合計と最大値

○整数型: max(整数型の配列: a)  整数型: m, i  m ← a[1]  for (i を 2 から aの要素数 まで 1 ずつ増やす)    if (a[i] > m)      m ← a[i]    endif  endfor  return m

見るのは、初めの値と繰り返しの始まりの組です。m を a[1] で始めるので、繰り返しは2から始まります。m を0で始めると、全部が負の数の配列で0を返してしまいます。合計なら、和を入れる変数を0で始めて1から繰り返します。比べる記号が > か ≧ かは、同じ値が複数あるときにどれを選ぶかを決めます（練習問題の問5）。

このコードと同じ型の例題を1行ずつ動かす（プログラムのなぞり書きの基本情報モード）

線形探索

○整数型: find(整数型の配列: a, 整数型: x)  整数型: i  for (i を 1 から aの要素数 まで 1 ずつ増やす)    if (a[i] = x)      return i    endif  endfor  return −1

先頭から順に比べ、見つかった時点で return します。return を実行すると、繰り返しの途中でも関数はそこで終わります。最後の return −1 に来るのは、全部比べても見つからなかったときだけです。a ＝ {7, 3, 9, 3} で x ＝ 3 を探すと、最初に見つかった2を返し、4番の3は調べません。探索アルゴリズムの用語集も参考になります。

このコードと同じ型の例題を1行ずつ動かす（プログラムのなぞり書きの基本情報モード）

二分探索

○整数型: binSearch(整数型の配列: a, 整数型: x)  整数型: low, high, mid  low ← 1  high ← aの要素数  while (low ≦ high)    mid ← (low + high) ÷ 2 の商    if (a[mid] = x)      return mid    elseif (a[mid] < x)      low ← mid + 1    else      high ← mid − 1    endif  endwhile  return −1

配列が小さい順に並んでいることが前提です。調べる範囲を low から high までとし、中央の mid と比べて範囲を半分にします。見るのは3か所で、中央の求め方 (low + high) ÷ 2 の商、範囲の更新 mid + 1 と mid − 1、繰り返しの条件 low ≦ high です。a ＝ {3, 8, 15, 21, 30, 42, 57} で x ＝ 30 を探すと、次のようになります。

3周目は low と high が同じ5です。条件が low < high だったら、この周に入れず、30を見つけられずに −1 を返します。範囲の更新に ＋1・−1 が付くのは、mid の位置はもう調べ終わったからです。付けないと、範囲が縮まずに同じ周を繰り返すことがあります（練習問題の問7）。整列済みの配列での比べる回数の少なさは、計算量の考え方につながります。

このコードと同じ型の例題を1行ずつ動かす（プログラムのなぞり書きの基本情報モード）／線形探索と二分探索の動きを並べて見る（可視化スタディ）

交換法（バブルソート）

○sort(整数型の配列: a)  整数型: n, i, j, tmp  n ← aの要素数  for (i を n から 2 まで 1 ずつ減らす)    for (j を 1 から i − 1 まで 1 ずつ増やす)      if (a[j] > a[j + 1])        tmp ← a[j]        a[j] ← a[j + 1]        a[j + 1] ← tmp      endif    endfor  endfor

隣どうしを比べ、左が大きければ入れ替えます。内側の繰り返しを1回終えるたびに、残りの中で最も大きい値が右端に移って確定します。そのため、内側の範囲は1周ごとに1つずつ縮みます。見るのは内側の終わり i − 1 で、ここが i だと a[j + 1] が範囲の外を指します。a ＝ {4, 2, 5, 1, 3} を並べると、次のようになります。

太字は確定した部分です。比べた回数は 4＋3＋2＋1＝10回で、配列の中身によらず決まります。入れ替えた回数は中身によって変わり、この例では6回でした。「比べる回数」と「入れ替える回数」のどちらを聞かれているかを、問題文で確かめます。ほかの並べ方はソートアルゴリズムの用語集にまとめています。

このコードと同じ型の例題を1行ずつ動かす（プログラムのなぞり書きの基本情報モード）／バブル・挿入・選択・マージ・クイックの各ソートをコマ送りで見る（可視化スタディ）

ユークリッドの互除法

○整数型: gcd(整数型: m, 整数型: n)  整数型: r  while (n ≠ 0)    r ← m mod n    m ← n    n ← r  endwhile  return m

2つの数の最大公約数は、「大きいほうを小さいほうで割った余り」と「小さいほう」の最大公約数に等しい、という性質を繰り返し使います。余りが0になったときの割る数が答えです。gcd(84, 36) なら、1周目に r ＝ 84 mod 36 ＝ 12 で m ＝ 36、n ＝ 12、2周目に r ＝ 0 で m ＝ 12、n ＝ 0 となり、12を返します。

見るのは代入の順番です。m ← n と n ← r を逆にすると、m にも n にも余りが入ってしまいます。値を移す順番の問題は交換法の tmp と同じ形で、トレース表で各行の直後の値を書くと間違いに気づけます。返すのが n ではなく m であることも、繰り返しを抜けたときに n が0であることから確かめられます。

このコードと同じ型の例題を1行ずつ動かす（プログラムのなぞり書きの基本情報モード）

再帰

○整数型: fact(整数型: n)  if (n ≦ 1)    return 1  endif  return n × fact(n − 1)

関数の中で同じ関数を呼び出すのが再帰です。関数を呼び出すと、呼んだ側は戻り値が返ってくるまで計算を止めて待ちます。トレース表では、呼び出しを1段ずつ下に積み、戻り値が決まったら下の段から順に上へ返します。

表は上から下へ書き、戻り値の列は下から上へ埋めます。見るのは、呼び出しが止まる条件（ここでは n ≦ 1）と、呼び出すたびに引数が止まる条件へ近づいているかです。fact(n − 1) が fact(n) だったら、呼び出しは終わりません。

このコードと同じ型の例題を1行ずつ動かす（プログラムのなぞり書きの基本情報モード）／再帰の呼び出しが積まれて戻る様子を見る（可視化スタディ）

空欄を埋める問題の解き方

空欄の問題では、プログラムの目的が問題文に書いてあります。選択肢をにらんで「これが正しそうだ」と決めると、似た選択肢の間で迷います。確実なのは、選択肢を1つずつ空欄に入れ、小さな入力で1周だけトレースする方法です。

1. 問題文から、関数が何を返すべきかを一文で書き出す。同じ値が複数あるとき、見つからないときの扱いも拾う。
2. 要素が3個ほどの小さな入力を自分で決める。正しい答えを先に手で求めておく。
3. 選択肢を入れて、1周目をトレースする。ここで明らかにおかしい選択肢を外す。
4. 残った選択肢を、境界で確かめる。最後の周、繰り返しを抜ける判定、要素が0個や1個のとき。

たとえば、配列の合計を求めるプログラムの for (i を 1 から ［空欄］ まで 1 ずつ増やす) に、aの要素数 − 1、aの要素数、aの要素数 + 1 が並んでいたとします。1周目はどれも同じ動きなので区別できません。差が出るのは最後の周です。要素数3の配列で確かめると、− 1 は a[3] を足さずに終わり、+ 1 は存在しない a[4] を参照します。残るのは aの要素数 です。

境界で確かめるのは、選択肢の違いがたいてい境界にしか現れないからです。< と ≦、mid と mid + 1、i と i − 1 は、繰り返しの途中ではどちらも同じように動き、最初か最後の1周でだけ結果が分かれます。

1行ずつ動かして確かめるツール

トレース表を自分で書いたら、答え合わせをしたくなります。このサイトには、プログラムの動きを目で確かめるツールがあります。

• プログラムのなぞり書き：プログラムを1行ずつ実行し、変数の値と出力の変化を表示します。上の切り替えで「擬似言語（基本情報）」を選ぶと、擬似言語の書き方で動かせます。関数を呼ぶたびに呼び出しの段が積み重なる様子も見えます。前の節の型ごとのリンクから、同じ型の例題を開けます。この記事のコードを貼り付けて動かすときは、最初の ○ より前の行に、呼び出す文（例：出力する(gcd(84, 36))）を書き足します。
• 可視化スタディ（ソート）：バブル・挿入・選択・マージ・クイックの各ソートで、配列が並び替わる様子をコマ送りで見られます。同じシリーズに探索と再帰もあります。
• てじゅんカード：処理の手順を書いたカードを正しい順に並べ替えます。代入の順番を入れ替えると結果が変わる、という互除法や交換法の注意点を、手を動かして確かめられます。

ツールで動かすのは、自分のトレース表を書いたあとにします。先に動かしてしまうと、表を書く練習になりません。合わなかったときは、どの行で値がずれたかをツールの表示と見比べると、自分がどこで読み違えたかが分かります。

練習問題

この記事の内容から作ったオリジナルの問題です。配列の要素番号は、どの問題も1から始まります。トレース表を書いてから選んでください。選ぶとその場で正誤と解説が出ます。最初に選んだ答えで採点し、最後に正答数を表示します。