初心者向け「アルゴリズム」の教え方

1号(♂14才)が参加しているロボット教室で、思いつきで「アルゴリズム」について教えてみよう、と思った。
アルゴリズムを工夫することによって、

• 計算の精度を高める　(有効数字など)
• 計算量を削減できる　(計算時間の短縮)

を知ってもらえればいいと思った。
対象は小3〜中3である。
こんなかんじで始めた。

アルゴリズムとはコンピューティングにおける計算の順序のことで、これを工夫することによっていろいろなメリットがあります。

「計算の精度を高める」の説明
計算の精度を高める例として、次の算数を解いてもらう。

1　÷　3　×　3　=　？

算数で解くと、答えは「1」。
しかし、安い電卓を各自に回して解いてもらうと答えは「1」にはならず、「0.999...」となる。はてな？

これは、電卓が最初の「1　÷　3」の結果を2進数で表せず、「0.333...」の結果のみを保持してしまい、続く 「×　3」で「0.999...」となってしまうためである。
では、計算の順番を入れ替えるとどうなるか？

1　×　3　÷　3　=　？

この場合は、算数上も電卓上でも「1」である。ひゃっほー！

この説明での注意点は(安い)電卓を使うことである。
PCや、スマホのような高級なOSを持つ計算機や関数電卓では、そのあたりは配慮されていて、ちゃんと答えが「1」となるように仕組まれている。
この例題で、計算の順序によって「計算の精度」に影響が出ることを知ってもらうことができた。


さて、次に「計算量の削減」だが、ネットでネタ探しをすると、ソート(並べ替え)の話がメインなので、「バブルソート」や「バケツソート」「クイックソート」の実例を出してみても、いまいち食いつきが悪い。
というか、勝手講師の私が2度も「クイックソート」の説明でつまづいたので、とても下手な説明になってしまったのも失敗の要因として大きい(個人的にはショックが大きい…)。
もっとも、講師の下手さを差し引いても、まだ、小中学生の実生活でソーティングのお世話になるようなこともないので、興味を引かなかったようでもある。

「計算量を削減する」の説明
そこで、ソートではなく「絞り込みの順番」で考えてみるとした(バケツソートになっているけど)。
次の例題を考えた。

(目的) 男女同数24人づつ合計48人のクラスの中で、9月生まれの女子の人数を知りたい。
(前提条件)　質問は1人づつ1回に1種類しかできない。質問の結果によって次の質問の対象者を減らすことが出来る(絞込)。また、回答の際の声色で男女の区別は出来ないものとする(現実ではできちゃうので)。
(導きたい結果)　9月生まれは4人おり、そのうち女子は2人である。

必然的に以下の2種類の質問をすることになる。

A. あなたの性別は何ですか？　(男子ですか？　女子ですか？)
B. あなたは何月生まれですか？

この「質問の順序次第で質問の回数が大幅に変わること」を知ってもらうことが狙いである。

(A先B後の場合)
Aを最初に質問し、Bを続いて質問する場合は次の質問回数が期待値となる。

1. あなたの性別は何ですか？　　→　48回の質問
2. 女子24人に絞られる
3. (女子24人に対し)　あなたは何月生まれですか？　→　24回の質問
4. 女子で9月生まれの2人に絞り込まれた！

この場合、48回+24回=72回の質問が必要になる。

(B先A後の場合)
Bを先に質問し、Aを後にした場合は次のとおりとなる。

1. あなたは何月生まれですか？　　→　48回の質問
2. 9月生まれ4人に絞られる
3. (9月生まれ4人に対し)　あなたの性別は何ですか？　　→　4回の質問
4. 女子で9月生まれの2人に絞り込まれた！

この場合、48回+4回=52回の質問で済む。

質問の順序を工夫することで(=アルゴリズムを工夫することで)、20回も削減できた(28％OFF)。
最初の48回の質問回数は必須とすると、2番目の質問では24回から4回に減ったので、部分的に83％OFFと考えることもできる。ひゃっほー！
もっとも、期待値が推定出来る場合でないと有効ではないので、その点は注意が必要ではある。


次回のロボット教室でのチャンスに「計算量…」の説明で、子どもたちの合点が行くかどうか試してみる所存である。
その流れで、ロボット教室なのでセンサーの効率的なチェックの仕方や、合理的なif文の構造にまで踏み込めればいいかなと思う。

====

画像はiPhone5で撮影。
雨上がり、水たまりのアスファルトに溶け込んでいる朝の空。
そいういえば、今日、iPhone6が発表だな。NFC搭載だと嬉しいかも(買い換えないけど)。