基本情報技術者試験 科目Bのアルゴリズム問題について、基礎問題の例題を通してトレーニングします。
科目Bのアルゴリズムとは
アルゴリズムとは、目的を達成するための手順や処理の流れのことです。
例えば、「配列の中から最大値を見つける」「データを小さい順に並べ替える」といった処理もアルゴリズムの一つです。
科目Bでは、疑似言語（ぎじげんご）で書かれたプログラムを読み取り、「どのような処理が行われるのか」を考える問題が出題されます。
科目Bでアルゴリズムが重要な理由
科目Bでは、問題文を読んで知識を答えるだけではなく、プログラムの処理内容を読み取り、正しい結果を選ぶ力が求められます。
アルゴリズム問題の前提知識
アルゴリズムの問題を解くうえで必要になる知識は主に以下の内容です。
- 変数の扱い
- 配列
- 条件分岐や繰り返し処理
- 論理演算
- 木構造
これらの説明は本サイトの以下のページにありますので、未学習の方は下のリンクから学習ができます。
| 内容 | リンク |
|---|---|
| 論理演算 | 基数・論理演算・カルノー図 |
| 配列 | データ構造：配列とリスト |
| 変数の扱い 条件分岐 繰り返し処理 | 疑似言語 |
| 木構造 | データ構造：木構造 |
アルゴリズムのパターン
素数かどうかの判定
B科目では「ある整数が素数かどうかを判定するアルゴリズム」が出題されることがあります。
素数とは「1より大きく、1と自分自身以外では割り切れない整数」です。
例えば「36」が素数か調べる場合、2～35までで割り切れるかどうか確認すれば良いかもしれませんが、√36=6までを確認すれば良いです。
次のプログラムは、変数nが素数の場合、「nは素数です」と表示するプログラムです。（nは2以上とします。）
// 変数nが素数の場合、「nは素数です」と表示するプログラムです。nは2以上とします。
isPrime ← true
for (i を 2 から nの正の平方根の整数部分 まで 1 ずつ増やす)
if(n ÷ i の余り が 0 と等しい)
isPrime ← false
for 繰り返しを終了する
endif
endfor
if (isPrime が true と等しい)
「nは素数です」と表示
end if
配列の数値を使った計算
配列を使った計算の問題は、だいたいが配列の最初から最後までforでループして、１つずつ計算や比較判定をするといったパターンです。
探索
線形探索
探索の中では一番簡単なアルゴリズムで、配列の先頭から順番に探したい値を調べます。
二分探索
二分探索は、整列済みの配列を、探索範囲を半分ずつ狭めながら目的の値を探す方法です。
下のように、探索範囲の真ん中の値と探している値を比較して、真ん中の値が探している値より大きければ左側に、小さければ右側に探索範囲を絞ります。
図で見た動きをプログラムで表すと、次のようになります。
※配列 data は昇順に整列済みとする。
○整数型: search(整数型の配列: data, 整数型: target)
整数型: low, high, middle
low ← 1
high ← dataの要素数
while (low ≦ high)
middle ← (low + high) ÷ 2 の商
if (data[middle] < target)
low ← middle + 1
elseif (data[middle] > target)
high ← middle – 1
else
return middle
endif
endwhile
return -1
理解テストです。
【答え】
4 → 6 → 7
middleは次のようになります。
ソート
ソートとは、データを決められた順番に並べ替える処理のことです。
試験では、代表的なソートアルゴリズムの特徴や処理手順が出題されます。
| 名前 | 説明 |
|---|---|
| バブルソート | 隣り合うデータを比較し、順番が逆であれば交換します。この処理を繰り返すことで、大きい値（または小さい値）が端へ移動していきます。 |
| 選択ソート | まだ並んでいない範囲から最小値（または最大値）を探し、先頭のデータと交換します。 |
| 挿入ソート | 並び終わった部分に対して、新しいデータを正しい位置へ挿入していきます。 トランプを手札に並べる作業をイメージすると理解しやすいアルゴリズムです。 |
| クイックソート | 基準となる値（ピボット）を決め、それより小さいグループと大きいグループに分けます。この処理を再帰的に繰り返して並べ替えます。 |
本ページではバブルソートについてのみ説明します。他のソートはこちらの説明を参照してください。
では、腕試し問題です。
【答え】
同じビット同士の排他的論理和(XOR)は0になる。
基本情報技術者試験では、代表的なソートアルゴリズムの特徴や処理の流れが出題されます。まずは、それぞれの特徴を理解しておきましょう。
再帰処理
再起処理は、自分自身の関数を呼び出す処理のことです。
再帰処理と再帰処理を使わない場合
今度は再帰処理を使わない場合で同じ処理を実現する場合です。
試験ではプログラムの内容を問われます。
上の説明にもあるように、配列には直近3つの計算結果を保持しています。
data[1]：2つ前
data[2]：1つ前
data[3]：現在
■配列dataが3つの理由
この再帰式ではProc(n-2)とProc(n-1)だけ必要なので、3個あれば十分です。
論理演算のアルゴリズム
覚えておくとよいパターン
論理演算アルゴリズムの問題について、覚えておくとよい内容を例題を出すので、考えてみてください。
排他的論理和を使った値の一致判定
【例題】
関数 isEqual は，x と y が等しいときだけ 00000000 を返す。
□には何が入るか答えよ。
演算子 ∧，∨，▽ はそれぞれビット単位の論理積，論理和，排他的論理和を表す。
[プログラム]
○8ビット型: isEqual(8ビット型: x, 8ビット型: y)
return □
【答え】
x ▽ y
同じビット同士の排他的論理和(XOR)は0になる。
排他的論理和を使った反転
【例題】
関数 invert は，引数として渡された8ビット型の値 x の各ビットを反転した値を返す。
□には何が入るか答えよ。
演算子 ∧，∨，▽ はそれぞれビット単位の論理積，論理和，排他的論理和を表す。
[プログラム]
○8ビット型: invert(8ビット型: x)
8ビット型: y
y ← □
return y
【答え】
x ▽ 11111111
全て1の値と排他的論理和(XOR)で計算すると反転する。
加算するとオール1になる値を求める
関数 minusOne は，引数 x に加算すると 11111111 になる8ビット型の値を返す。
□には何が入るか答えよ。
※8ビット加算では，あふれた桁は無視する。
※演算子 ∧，∨，▽ はそれぞれビット単位の論理積，論理和，排他的論理和を表す。
[プログラム]
○8ビット型: minusOne(8ビット型: x)
8ビット型: y
y ← □
return y
【答え】
x ▽ 11111111
全て1の値と排他的論理和(XOR)で計算すると反転するので、これに元の値を加算すると全て1になる。
トレース問題の解き方
トレースとは、プログラムを1行ずつ読みながら、変数や配列の値がどのように変化するかを確認する作業です。
例えば、下のプログラムは、「引数の配列に格納されている整数の最大値を返す」という内容です。
forで配列の要素数分ループし、変数maxに格納されている値と比較して大きい場合は、maxを更新することで、maxに最大値を格納できます。
登場する変数i、data配列、maxがプログラムの中でどのように変化するのかを書き出して求めます。
コメント