前回、高校「情報I」の教科書で紹介されたアルゴリズムを九九の５の段の制作を通して紹介しました。今回は、もう１つ「アルゴリズム」を紹介します。アルゴリズムの定番とも言える「探索」を一緒にみてみたいです。
探索という行動は、人間が日常的に行っています。例えば、バス停で次のバスの発車時間を時刻表から探す場合も、空港で自分のフライトの搭乗口を電子掲示板から探す場合も、高校や大学の合格者発表掲示板から自分の番号を探す場合も、探索のアルゴリズムが使われています。
今回は、学習塾を例にし、この探索のアルゴリズムを紹介します。
あなたはこどもICT塾の講師です。あなたのクラスには生徒10名います。先週英語の模擬試験を行いました。あなたは、それぞれの生徒の成績を表にまとめました。
では、あなたは、生徒IDが107番の生徒の成績を探したいです。どのようなアルゴリズムを考えればいいでしょうか？
前回と同じように、目標を達成するための行動を分析してみましょう。まず、人間のあなたなら、どのように107番の生徒の成績を見つけますか？
おそらく以下のような感じになります。
A 生徒IDの列から107番を見つけます。
B 107番の行の右にある、英語の列に書かれている数字が探したい成績です。
つまり、107番の生徒の英語成績は69点です。
人間の場合は、大体上記A、Bの2ステップで答えを見つけることができます。しかし、プログラムの場合はもう少し細かく考える必要があります。なぜなら、上記の人間の2ステップの中に、無意識にやっていることがいくつか含まれているからです。皆さん、無意識に何をしたか気づいていますか？プログラムを作るときは、それらの行動もプログラムにしなければなりません。
以下はプログラムの角度から答えの成績69を見つけ出す手順を説明します。
① 生徒IDの107を入力してもらいます。
② 生徒IDの列を、上から１つずつデータを取り出します。
③ 取り出したデータが107と比較し、同じかどうかを確認します。
④ 107でない場合は、次の生徒IDへ進みます。
⑤ 107である場合は、その行の左から3番目のデータが英語の成績となります。
⑥ 107番の成績が見つかった場合、探索を中断します。
⑦ 見つけた英語成績を表示します。
探索したいデータを見つけるには、以上の７つのステップがあります。実は人間の行動Aの中に、プログラムの①〜④が含まれています。②と③はほぼ無意識にやっています。しかし、プログラミングの考え方からみると、これらのステップも生徒自ら見つけ出さなければなりません。だから、プログラミングを学ぶと、思考力や問題の解決力を鍛えられるようになります。
今回紹介した探索方法は最も、基本的な探索手法の１つです。線形探索です。つまり、すべてのデータを最初から最後まで１つずつ比較しながら探す方法です。いわゆる総当りのやり方です。この線形探索のメリットは、アルゴリズムの仕組みがわかりやすいことです。そして、探したいものが全データの先頭近くにある場合、早く見つけることができます。上記の例の場合、101番の生徒の成績を探すなら、1回の処理で見つかります。しかし、110番の生徒の成績を探す場合、10回処理しないと見つかりません。処理の量は101番の時の10倍になります。つまり、探したいデータが全データの後部位置にあると、見つけるには処理時間がかかります。探索したいデータの位置によって計算量がかなり多くなる場合があるのが、この線形探索の弱点です。
では、上記の７つのステップを踏まえ、実際のプログラムを書いてみましょう。
前回と同じく、JavaScriptを使ってプログラムを書いてみましょう。
ちなみに、今回の例題には、もうひとつ情報Iで学ばないといけないポイントがあります。それがデータです。データはどのような形で保管されているかを学ぶ必要があります。今回のような複数の行に、複数の列があるデータは「配列」を使って管理するのが一般的です。配列はたくさんのデータをまとめて処理できるものです。私は「変数の集まり」と生徒に説明しています。１つの変数には１つのデータしか保管できないですが、１つの配列にはたくさんのデータを保管できます。今回は、すべての生徒のデータを配列に入れて管理します。
実際の処理プログラムは以下のようになります。今回は探索したい生徒IDの107をプログラムの中に直接書き込みます。
実行した結果はこうなります。
いかがでしょうか？上記のプログラムを理解できますか？
探索のアルゴリズムの勉強から、プログラミングの考え方を学ぶことができます。この考え方は、今後仕事でいろんな問題を解決するための方法を見つけるのに役に立ちます。探索のアルゴリズムはほかにもあります。情報Iの教科書には、二分探索も紹介されています。線形探索の時間がかかる弱点をクリアできる探索手法です。また次回、この二分探索を一緒に作って理解を深めていきましょう。
