戦艦

概要

コンピュータは大量のデータから情報を探すことを求められることが多く、そのために高速で効率の良い方法が必要です。今回の学習では、線形探索、二分探索、ハッシュ法という3種類の探索技術を扱います。

教科学習との関連

• [数と計算]数の比較:より大きい、以上、以下、未満、範囲。数の大小に関しては小1から扱っていますが、学習指導要領で「≧」は、中1の数と式の領域に配当されています。
• [数量関係(中)]座標は中1で学びます。でも、このような扱いなら気軽に素地指導としてもっと低学年の子どもに扱わせることができるでしょう

技能

• Logical reasoning 論理的推論を行う。

年齢

• 9 歳以上

教材

• 子どもごとに必要なもの
  • 戦艦ゲームのコピー
    • 1A、1B（ゲーム1用）　PDF
    • 2A、2B（ゲーム2用）　PDF
    • 3A、3B（ゲーム3用）　PDF

• 予備のゲームシートである1A'（PDF）、1B'（PDF）、2A'（PDF）、2B'（PDF）、3A'（PDF）、3B'（PDF）も数枚のコピーが必要かもしれません。

• 解説　PDF

戦艦　導入ゲーム

学習の概要

1. 15 人くらいの子どもを教室の前に並ばせましょう。彼らには 2 桁の数字が書かれたカード を持たせます ( 値は 0 から 99 で、順序はランダムです )。他の子どもには数字は見せない ようにします。
2. 他の子どもには 4 個から 5 個のおはじきの入った箱を持たせます。彼らは与えられた数を 探すのが仕事です。彼らは、おはじきを渡してカードを見せてもらうことができます。正しい数を見つけたときに手元に残っていたおはじきは自分のものになります。
3. 何回か繰り返してみましょう。
4. 次に、カードを切り直してもう一度配ります。今度は、子どもを自分たちで小さい順になるように並ばせます。そして数を探させます。

数が順番に並んでいる場合には、真ん中の子どもにおはじきを渡して数を聞くだけで、半分の子どもを候補から除くことができます。この処理を続けると、必ず 3 個のおはじき を使うだけで数を見つけることができます。明らかに効率的です。

学習
子どもは戦艦ゲームを通して、コンピュータがどのように探索を行っているかを体験できます。ゲームの中で、船をどうやって見つければよいかを考えさせていきましょう。

戦艦 線形探索ゲーム

子どもに次の指示を伝えてください

1. 自分たちで 2 人組を作ります。1 人は 1A のシートを、もう1人は 1B のシートを持ちます。 自分のシートは相手に見せないでください!
2. 両方とも、それぞれのゲームシートの上にある戦艦を1つ丸で囲み、相手にその番号を伝 えます。
3. 次に、かわりばんこに相手の船がどこにいるかを推測します。( あなたは船の名前(英字) をいい、相手はその名前の船の番号を答えます )
4. 相手の船の場所を当てるまでに、何回攻撃しましたか ? それがあなたの得点です。少ない ほうが勝ちです。
   ( シート 1A と 1B のほかに、もっとゲームをしたい子どもや間違って相手にシートを見せ てしまった子どものために 1A' と 1B' が用意されています。また、2A、2B や 3A、3B の予 備シートも用意されています。)

振り返りの議論

1. 何点でしたか ?
2. いちばん小さい得点といちばん大きい得点は何点でしょう ?
   ( 子どもが同じ船を 2 回以上攻撃しないと仮定すると、それぞれ 1 と 26。この探索手法は
   1 個ずつ調べていくため「線形探索」と呼ばれます )

戦艦 二分探索ゲーム

指示
このゲームのやり方は前のゲームと同じですが、船の数字は小さい順に並んでいます。「さっ きと並びが違うよ」など、このことを子どもに気づかせてから始めてください。

1. 自分たちで 2 人組を作ります。1 人は 2A のシートを、もう1人は 2B のシートを持ちます。 自分のシートを相手に見せてはいけません!
2. 両方とも、それぞれのゲームシートの上にある戦艦を1つ丸で囲み、相手にその番号を伝 えます。
3. 次に、かわりばんこに相手の船がどこにいるかを推測します。( あなたは船の名前(英字) をいい、相手はその名前の船の番号を答えます )
4. 相手の船の場所を当てるまでに、何回攻撃しましたか ? それがあなたの得点です。少ない ほうが勝ちです。

振り返りの議論

1. 何点でしたか ?
2. 勝つためにはどうすればよいですか ?
3. どの船を最初に選ぶべきだったでしょう ? ( 真ん中の船はあなたに、左右どちらの半分に目 的の船がいるかを伝えてくれます ) 次に選んだのはどれでしょう ? ( もう一度、あなたが選 んだ半分の真ん中の船を選ぶのが最も良い戦略です )
4. この戦略を使うと、目的の船を見つけるのに何回の攻撃が必要ですか ? (5 回以下 ) この探索手法は問題を 2 つの部分に分けていくことから「二分探索」と呼ばれます。

戦艦 ハッシュ法を使ったゲーム

指示

1. 前のゲームと同じようにシートを持ち、選んだ船の番号を相手に伝えなさい。
2. このゲームでは、0 から 9 のどの列にその船がいるかを見つけます。船の番号の各桁を足 し合わせた最後の桁が、船がいる列の番号になります。たとえば、2345 の船は 2+3+4+5 を計算して 14 になります。和の最後の桁は 4 なので、その船は 4 の列にあるはずです。列 がわかれば、あとはその中のどの船かを予想するだけです。この手法は数字を混ぜ合わせ ることからハッシュ法と呼ばれています。
3. 次に、新しい探索戦略を使ってゲームをしましょう。別の列を選ぶことで、同じシートを使っ て複数回遊ぶことができます。
   ( このゲームでは、3A と 3B は必ず組にして使ってください。列に入る船が対応している必 要があるからです )

振り返りの議論

1. 得点を集めて議論しなさい。
2. どの船が見つけやすかったですか ? ( 列に 1 個だけある船 ) どの船が見つけにくかったですか ? ( たくさん入っている列にある船 )
3. どの探索手法が速かったですか ? それはなぜでしょう ?

3 種類の探索手法は、それぞれどんなところが利点でしょう ?
2 番目は 1 番目より速いですが、1 番目はソートしておく手間が不要です。
3 番目は他の 2 個より速いことが多いですが、ごくたまにとても遅いことがあります。
すべての船が 1 個の列に入ったときは最悪のケースで、1 番目と同じ速さになってしまいます。

追加学習

1. 子どもに 3 種類のゲームを作らせましょう。2 番目のゲームでは、数を小さい順に並べる 必要があります。ハッシュ法のゲームでいちばん難しいものを作るやり方を考えさせましょ う。( すべての船が1つの列に入るものが最も難しいです ) いちばん易しくなる方法も考え させましょう。( それぞれの列に同じ数だけ船を入れさせてみます )
2. もし船が存在しない場合はどうなりますか ? ( 線形探索ではそれがわかるまでに 26 回攻撃 するでしょう。二分探索では 5 回必要です。ハッシュ法では該当する列にいくつ入ってい るかで結果が変わります )
3. 二分探索を使うと、100 個のときに何回の攻撃が必要でしょう ( 約 6 回 )、1000 個ならど うでしょう ( 約 9 回 )、100 万個なら ( 約 19 回 )? ( 船の数が増えても、攻撃の数はそれほど 増えないことに注意しましょう。攻撃は相手が2倍になるごとに 1 回増えるので、船の数 の対数に比例します )