サンタの汚れた靴下

サンタの汚れた靴下

概要

この活動は「分割統治」の考え方を、架空の深刻な問題を通して紹介しています。
サンタさんが届けようと しているプレゼントの 1 つに、1 組の汚れた靴下が誤って包装されてしまったので、それを受け取った子どもが 嫌な思いをしないように、それを見つける必要があります。

教材

  • 授業用補足資料 filePDF

活動

23_1.png

検査しなければいけない 1024 個の箱がある時、靴下が見つかるまでそれらのすべてを開ける代わりに、一回 で半分に減らしながら 1 個の箱になるよう繰り返し、とても素早く減らしていく(1024 個で始めた問題の大き さは、1 回の計量で 512 個の箱になり、そして 256、128、64、32、16、8、4、2、1 個になる)という解決法を 示しています。この考え方は、高速のコンピュータ・アルゴリズム設計によく出てきます。

この話を聞いた学生が、フォローアップの議論をするためにいくつかのアイディアがあります。これらの質問のいくつかは、重複し、また議論の単なるガイドラインに過ぎないかも知れません。

  • 天秤を用いて、32 個のおもりから他と異なる 1 個を特定する活動を想定して下さい。ではここで考えてみましょう。- もしおもりが 64 個あれば、計量は何回増えるでしょうか。[たった 1 回計量が増えるだけ です。]
  • もし、2048 個の箱があったら、この処理では何回計量するでしょう。[11 回の計量であり、1024 個の箱 の時よりもたった 1 回増えるだけです。]
  • 贈り物が倍になったら、何回計量が増えるでしょうか。[その半分の大きさの問題より 1 回多いだけ です。]
  • 贈り物が 4 倍になったらどうでしょう。[もう 2 回計量が必要です。]
  • 1024 倍になったどうでしょう。[もう 10 回計量が必要です。]
  • 直前の質問で、1024 倍になったら贈り物は何個になるでしょう。そして、何回計量することになるでしょう。[1024 × 1024 = 1、048、576 個の贈り物で、10 + 10 = 20 回の計量です。]
  • 30 回の計量では何個の贈り物をチェックできるでしょう。[1024 × 1024 × 1024 = 1、073、741、824 で、10億個を超えています。]
  • これは本当の話だと思いますか。[作り話です。]
  • あなたが、10 億(1、000、000、000)個の単語を探す検索エンジンを作っていると仮定し、その単語をアルファベット順に並べて下さい。検索エンジンは、リストの真ん中の単語を探し、1 回のチェックでリスト の半分を排除します。その 1 つを見つけるためあなたは何回単語をチェックしなければいけないでしょ う。[10 億語を探すのにたった 30 回のチェックでよいのです。学生には 1024 個程度の単語から始める か、辞書や電話帳を使ってやるといいでしょう。]

数学のより得意な学生のために:

  • 2 のべき乗でない個数の箱で行なうにはアルゴリズムをどうやって調整しますか。(例えば、30 個の箱の 重さを計測することを考えて下さい。)[1 つのやり方は次の通りです:n が偶数なら単純に半分に分けて重さを計測し、重い方の半分に同じことを繰り返します。n が奇数なら任意の 2 つの箱を取ってそれらを比較し、もしそれらが同じでなければ靴下が見つかるし、そうでなければ 2 つのうちどちらかをグループ に戻して、偶数個の箱の計量を行ない、重い方の半分にこの方法を繰り返します。]
  • もし n 個の箱があった時、実行される計量回数の式はどうなるでしょう? [それは約 log2 n で、n が 2 の べき乗でない時はもっと多くなりますが、2 log2 n より多くなることはありません。そして、運がよけれ ば最初の 2 つの比較で見つかるかも知れません。]

フォローアップ

非常に大きい入力に対処できる著しく速いアルゴリズムは、エルブのアルゴリズムと同じ比較回数になる整列 された値(数、単語、何かの情報)の大きなリストを探す二分探索と非常に似ています。だから、10 億の項目も ちょうど 30 回の比較で見つけることができます。

powered by Quick Homepage Maker 5.1
based on PukiWiki 1.4.7 License is GPL. QHM

最新の更新 RSS  Valid XHTML 1.0 Transitional