高校「情報Ⅰ」からみるプログラミングの考え方 ②

2023年5月12日中山涼一

高校「情報Ⅰ」からみるプログラミングの考え方 ②

前回、高校「情報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」で学ばないといけないポイントがあります。それがデータです。データはどのような形で保管されているかを学ぶ必要があります。
今回のような複数の行に、複数の列があるデータは「配列」を使って管理するのが一般的です。配列はたくさんのデータをまとめて処理できるものです。私は「変数の集まり」と生徒に説明しています。
１つの変数には１つのデータしか保管できないですが、１つの配列にはたくさんのデータを保管できます。今回は、すべての生徒のデータを配列に入れて管理します。