情報活用編プラス
第3章「コンピュータとプログラミング」
IP02-08
実践プログラム① 探索アルゴリズム 線形探索
4. 線形探索の手順 ( 4 / 12 )
学習の目的
1. 線形探索の手順と比較回数
2. アルゴリズム学習ツールについて
3. データが存在する場合の線形探索
4. データが存在しない場合の線形探索
線形探索の手順と比較回数の確認を「アルゴリズム学習ツール(線形探索)」を利用しておこないます。
アルゴリズム学習ツールは、コンピュータがどのように処理をしていくのかを線形探索の手順を追って確かめることができます。
アルゴリズム学習ツール(線形探索)を使って、1ステップずつの実行手順と比較回数を確認していきます。
なぜ比較回数の表示があるのですか？
それはですね、探索処理の場合は、比較回数がアルゴリズムの効率の良さを表す指標になるからです。
よくわかりません。
コンピュータの良いところは、処理を高速に行い結果がすぐに出るところです。
そのため、同じ結果になっても実行する命令(ステップ)数が少ないほうが効率の良いアルゴリズムと言われます。
なるほど、それじゃ探索処理の場合は比較回数が少ないほうが良いってことなんですね。
そうです。線形探索では特に次の2つに注目して学習しましょう。
それでは上記2点に注目してアルゴリズム学習ツールを使って学習を進めましょう。
最初に下記のボタンをクリックして「アルゴリズム学習ツール(線形探索)」のページを開きましょう。
アルゴリズム学習ツールは、誰でも簡単にアルゴリズムを1ステップずつ確認することができます。
操作は「① スタートボタン」、「② 進む・戻るボタン」を押すだけです。現在、どのような処理をしているかはメッセージ欄に表示されます。
それでは実際に、探索をしてみましょう。
最初は、「23」を探索(探索データが存在するケース)を確認します。
次の点を意識しながら探索を進めてください。
添字の値や探索が終了するタイミングは、プログラムを作るうえで重要なポイントになります。
そっか。配列で繰り返し処理をするから、添字やどこまで繰り返すのかわからないといけないですものね。
なるほど！きちんと確認しないとな。
スタートボタンを押したら、「23」を発見するまで進むボタンを押して処理を進めましょう。
手順を確認したい場合は、下記の「手順を確認する」をクリックしましょう。
今回は、学習モードを使って線形探索の手順及び比較回数を確認します。
学習モードでは次の10個のデータを配列に格納しています。
目的のデータ23をどのように探していくか確認しましょう。
配列操作ですので、どの位置のデータと比較しているか添字の動きも確認をしていきましょう。
スタートボタンを押すと探索を開始します。
先頭データから探索をするので、配列の先頭要素(0番目)のデータと探索値23が同じ値かどうか比較します。
画面のポイント
配列要素のデータと比べるので、添字で位置指定をすることを意識しましょう。
プログラムにしたときにどうなるかをイメージしながら処理を確認します。
一致しない場合は、次のデータと比べるために添字を移動して次のデータの探索処理に移動します。
「進む」ボタンを押して次のステップに進みましょう。
1番目の要素「7」と探索値「23」が同じか比較します。
一致しないので、添字を移動して次の要素と比較します。
探索値「23」が見つかるまで進めましょう。
添字を移動させるたびに比較するので、比較回数が増えていくところも確認しましょう。
4番目の要素「23」と探索値「23」が同じか比較します。
添字4のデータが23なので探索値と一致しました。探索値が見つかったら探索処理を中断します。
ここで、線形探索の手順のポイントをまとめます。
続いて、探索データが潜在しないケースを確認しましょう。
最初に、探索値を配列データに存在しない「99」を選択します。
99を選択したら、スタートボタンを押して最後まで探索を行ってみましょう。
探索データが発見できた場合と、できなかった場合で手順はなにか変わりましたか？
えーっと、見つかった場合はそこで探索処理をやめていたけれど、今回は最後まで探索をしたところが違いました。
そうですね。添字を使って最後まで探索したことを表すにはどうしますか？
添字は0から1つずつカウントアップされていくので、添字の値が9を超えたら配列の要素をすべて比較したことになると思います。
完璧ですね。探索処理を中断する条件は2つあります。一つは発見されたときと、もう一つは発見できなかった(データをすべて探索した)ときです。
発見できた場合とできなかった場合を考えた処理手順は次のようになります。
探索値が見つかった場合と見つからなかった場合で、探索処理を中断する条件は、線形探索のプログラムを作成するときにとても重要な条件になります。
処理手順のあとは比較回数について学習します
アルゴリズム学習ツール(線形探索)の自由実行モードについて
自由実行モードは、次の指定ができます。
自由実行モードで、線形探索の動きを確認できます。いろいろなデータで実行してみましょう。
