多くのデータの中から、目的のデータを見つけ出すことを探索といい、代表的な探索の方…
多くのデータの中から、目的のデータを見つけ出すことを探索といい、代表的な探索の方法の一つに線形探索法がある。線形探索法は、目的のデータを先頭から順番に一つずつ比べて探索を行う方法であり、データがどのような順番で並んでいても、目的のデータが存在していれば見つけ出せるという利点がある。
いま、無作為に並んでいるN個のデータから、線形探索法を用いて目的のデータを探索し、目的のデータを発見できた場合は「発見」、発見できなかった場合は「存在しない」と表示するプログラムを作ることとした。このプログラムの内容は、次の手順で表される。
○ はじめに、a に 1 を、n に N を入れる。
○ 「a 番目は目的のデータと等しいか」を調べ、「はい」であれば【ウ】を表示して終わる。
○ 「いいえ」であれば「a = n」かどうかを調べ、「はい」であれば【イ】を表示して終わる。
○ 「いいえ」であれば【ア】の処理を行い、ふたたび「a 番目は目的のデータと等しいか」を調べるところへ戻る。
ア、イ、ウに当てはまるものの組合せとして最も妥当なのはどれか。
- ⑴ ア:a に a-1 を入れる/イ:「存在しない」/ウ:「発見」aを1ずつ減らすと先頭より前へ戻ってしまい、探索になりません。
- ⑵ ア:a に a+1 を入れる/イ:「存在しない」/ウ:「発見」aを1ずつ増やし、見つかれば「発見」、最後まで見つからなければ「存在しない」とする正しい組合せです。
- ⑶ ア:a に a+1 を入れる/イ:「発見」/ウ:「存在しない」「発見」と「存在しない」の位置が入れ替わっています。
- ⑷ ア:a に n+1 を入れる/イ:「存在しない」/ウ:「発見」aにnより大きい値を入れると、途中の要素を調べられません。
- ⑸ ア:a に n+1 を入れる/イ:「発見」/ウ:「存在しない」aにnより大きい値を入れるうえ、表示の内容も入れ替わっています。
解説
正解は⑵です。線形探索は先頭から順に一つずつ比べていく方法なので、比べる位置を表すaを1ずつ増やしていきます。これがアに当たります。a番目が目的のデータと等しければ探索は成功ですから、ウには「発見」が入ります。等しくないまま最後のn番目まで比べ終えたときは見つからなかったということなので、イには「存在しない」が入ります。流れ図は、分岐の「はい」と「いいえ」がどちらへ進むかを確かめながら読みます。
出典:人事院ホームページ(https://www.jinji.go.jp/saiyo/siken/mondairei/mondairei_15.html)を加工して作成