【科目B対策】線形探索法を擬似プログラミング言語で理解する

― 初学者のためのアルゴリズム入門 ―

はじめに

基本情報技術者試験の科目Bでは、「プログラムを書けるか」ではなく、

アルゴリズムの動きを正しく読み取れるかが問われます。

その中でも、最初に理解しておきたい探索アルゴリズムが

線形探索法（せんけいたんさくほう）です。

この記事では、

  • アルゴリズムとは何か
  • 線形探索法の考え方
  • 科目Bで使われる擬似プログラミング言語
  • 試験での読み取りポイント

を、初学者向けにやさしく解説します。

アルゴリズムとは何か？

アルゴリズムとは、簡単に言うと

「問題を解決するための手順」

です。

料理で言えばレシピ、地図で言えば目的地までの道順、それをコンピュータ向けに整理したものがアルゴリズムです。

探索アルゴリズムとは？

探索アルゴリズムとは、

「たくさんのデータの中から、目的のデータを見つける方法」

のことです。

例えば、

  • 名簿から特定の名前を探す
  • 配列の中から特定の数値を探す

こうした場面で使われます。

線形探索法とは？

考え方（超重要）

線形探索法は、次のような方法です。

先頭から順番に、1つずつ調べていく

とてもシンプルで、人間が自然にやっている探し方に近いのが特徴です。

イメージ例

配列が次のように並んでいるとします。

A = [ 30, 12, 45, 7, 18 ]

ここから 「7」 を探す場合、

  1. 30 → 違う
  2. 12 → 違う
  3. 45 → 違う
  4. 7 → 見つかった！

というように、先頭から順番に確認します。

科目Bで使われる擬似プログラミング言語

科目Bでは、特定のプログラミング言語（C#やJavaなど）ではありません。

次のような特徴があります。

  • 代入に「=」は使わない
  • 「←」を使って値を代入する
  • for / if などは英単語

線形探索法の擬似プログラム例

前提条件

  • 配列 A に N 個のデータが入っている
  • 探したい値を KEY とする

擬似プログラム

FOUND ← false

for i ← 1 to N
  if A[i] = KEY then
    FOUND ← true
  endif
endfor

処理の流れを日本語で説明すると

  1. 「見つかったかどうか」を表す変数 FOUND を false にする
  2. 配列の先頭から最後まで順番に調べる
  3. もし A[i] が探したい値 KEY と同じなら
  4. FOUND を true にする

「見つかったら終了する」形（試験頻出）

実際の試験では、

見つかった時点で探索を終了する形もよく出ます。

FOUND ← false
i ← 1

while i ≤ N and FOUND = false
  if A[i] = KEY then
    FOUND ← true
  else
    i ← i + 1
  endif
endwhile

ここが読み取りポイント

  • FOUND が false の間だけ続く
  • 見つかった瞬間にループが止まる
  • 無駄に最後まで調べない

線形探索法の特徴まとめ

項目内容
探し方先頭から順番
理解のしやすさ非常に高い
処理速度遅くなることもある
並び順並んでいなくてもOK

科目Bでの注意点（超重要）

① 添字は 1 から始まることがある

科目Bでは、

A[1], A[2], A[3] ...

のように、1始まりが普通です。

普段のプログラミング経験がある人ほど注意が必要です。

② アルゴリズムを「実行」しない

科目Bでは、

  • 実際にコードを書く
  • コンパイルする

のではなく、

紙の上で、頭の中で1行ずつ追いかける

ことが重要です。

まとめ

  • 線形探索法は、科目Bの最重要基礎アルゴリズム
  • 「先頭から順番に調べる」だけ
  • 擬似プログラミング言語の書き方に慣れることが合格への近道
  • まずは 1行ずつ丁寧に追う練習 をしよう

訪問数 3 回, 今日の訪問数 3回

アルゴリズム,基本情報技術者,情報処理試験

Posted by hidepon