A. はじめに
最近，**「アルゴリズム」**という言葉を見かける機会がかなり増えました．あと数週間で小学校におけるプログラミング教育が必修化されます．来年からは中学校でも必修になります．高等学校では新科目「情報Ⅰ」がじきに必修化されますが，そこでもアルゴリズムを学ぶことが学習指導要領に明記されています (下を参照)．
〔指導項目〕
(1) 情報社会の進展と情報産業
ア 情報社会の進展 イ 情報社会における問題解決 ウ 情報社会の将来と情報産業
(2) 情報とコミュニケーション
ア 情報の表現 イ 情報の管理 ウ 情報技術を活用したコミュニケーション
(3) コンピュータとプログラミング
ア コンピュータの仕組み イ アルゴリズムとプログラム ウ 情報通信ネットワークの活用
(4) 情報産業が果たす役割
ア 情報セキュリティ イ 情報産業の役割 ウ 情報技術者の責務
これからは アルゴリズムの時代 と言っても申し分ないかもしれません．
データ構造とは
さて，**「データ構造」**という言葉を聞いたことがありますか？ データ構造とは，ざっくり言えば 情報の持ち方 のことです．
例えば，「住所が書かれた名簿」と「家主の名前が書かれた地図」の関係を考えてみましょう．
- 「〇〇さんの家に手紙を出したい！」というときは，名簿を見て住所を調べると便利です．地図にはたくさんの家が載っているから探すのにかなり手間がかかります．名簿なら，名前の順番に並べておけばすぐに目的の住所を見つけることが出来ます．
- 「〇〇さんの家に行きたい！」というときは，地図を見て行き方を確認します．名簿で住所を調べても，家がどこにあるのかはよくわかりません．
このように，同じ「人物と家の場所」という情報 (データ) を持つにも，「名簿で住所を管理する」「地図で位置を管理する」という 2 つは得手不得手が全く異なります．
実は，コンピュータの中の世界でも，情報の持ち方で効率に大きな差が生じてしまうことがあります．データ構造はこのような問題を解決するための考え方で，アルゴリズムとも密接な関係があります．
これからアルゴリズムを学んだり教えたりする機会が増えてくると思われますが，その中でデータ構造も取り扱ってみませんか？
この記事について
この記事の目的は，極力コンピュータを使わず，アンプラグドで (プラグをコンセントに差さずに，つまり電子機器を使わずに) データ構造を学んでもらうことです．情報科学の世界でよく出てくるデータ構造について，ある アイテム といくつかの シチュエーション を活用してもらうことで，おままごとをしながら 学ぶことが出来るようになっています．また，マニュアル を書く作業を通して，アルゴリズムに関する思考力も高めることが出来ます．
主な対象は小学生から高校生ですが，もちろん大人の方でも楽しんで頂けます．また，必須ではありませんが グループワーク を勧めています．班や家族で是非遊びながら学んでください．
B. 準備
この記事ではアンプラグドでデータ構造を学んでもらうため，アイテム を用意しています．まずはその準備をしていきましょう．
次のものをできれば 1 人 1 つ用意してください．最低でもグループに 1 つは必要です．
- 完全に透明なクリアファイル (100 円ショップで 5 ～ 10 枚セットで売っています)
- 紙 A：ダウンロードして A4 サイズで印刷してください
- 紙 B：ダウンロードして A4 サイズで印刷してください
- 水性ペン (濃い色が見やすくておススメです，太すぎると不便です)
- ティッシュペーパー
次の手順に従って準備してください．
- クリアファイルに紙 A を入れてください．
- 紙 B を 24 個の正方形に切り分けて，上部分だけをセロハンテープでクリアファイルに貼り付けてください．
この結果次のようなアイテムが完成します．これは簡易的なホワイトボードです．水性ペンで書いたりティッシュペーパーでこすって消すことが出来ます．
C. ルール
- 今作ったアイテムは シート と呼ぶことにします．
- シートのうち，紙 A に印刷されていた正方形を 部屋 と呼ぶことにします．また，貼り付けた紙 B の正方形を 窓 と呼ぶことにします．各部屋には番号がつけられていて，窓に書かれた番号と一致します．
- 各部屋には値を 1 つだけ書くことが出来ます．値の種類は数だったり文字だったりいろいろです．シチュエーションごとに指定があります．
- 窓は基本閉めておいてください (部屋に書かれている値が見えないようにしてください)．開けたら閉めてください．
- 他の店員から情報が与えられたり，質問されたりすることをまとめて 指示 と呼ぶことにします．
みなさんは今大人気のパンケーキ店でアルバイトを始めました．しかし，この店では少しおかしな 担当 がいろいろとあるようです．いろいろな担当の仕事をうまくこなしましょう．
D. おススメの取り組み方
まずは 1 人でじっくり考えてみましょう．
十分な時間を取ったら，グループを構成して考えたことを話し合います．話し合いがまとまったら**「マニュアル」**を作りましょう．マニュアルにはシートの使い方を書いておきます．
マニュアルが書けたら，全員目隠しをします．1 人ずつ交代で目隠しを解除します．先生役はその人だけにわかるように指示を与えてください．その人は指示を聞いて，質問されたのでればこっそり答えます．必要に応じてシートに書かれている値を書き換えて，また目隠しをします．これを繰り返します．
では，さっそく様々なシチュエーションに取り組んでいきましょう！
1. テーブル席 (かんたん☆☆☆)
設定
次のようなシチュエーションを考えます．
- このお店には 9 つのテーブル席があります．それぞれの席には 1 ～ 9 の番号がつけられていて，「テーブル 3」のように呼びます．
- 各テーブル席には 9 人まで座ることが出来ます．
- 今，お客さんは 1 人もいません．
- あなたはテーブル席管理担当者になりました．
次の指示 (情報伝達または質問) が与えられます．
- 「テーブル〇にお客さんが△人やってきました」(このときテーブル〇には誰もいません)
- 「テーブル〇のお客さんが全員帰っていきました」(このときテーブル〇にはお客さんがいます)
- 「テーブル〇にいるお客さんは何人ですか？」
各テーブルにいるお客さんの人数をうまく管理しましょう．
制限
- 使える部屋は 1 ～ 9 です．
- 最初，すべての部屋に 0 と書かれています．
- 各部屋に書けるのは 0 以上 9 以下の整数です．
- 各指示があったときに開けてもいい窓は 1 つだけです．開けた部屋の値を書き換えても構いません．
例
- テーブル 1 にお客さんが 3 人やってきました
- テーブル 5 にお客さんが 2 人やってきました
- テーブル 5 にいるお客さんは何人ですか？ → 答えは 2 人
- テーブル 2 にいるお客さんは何人ですか？ → 答えは 0 人
- テーブル 5 のお客さんが全員帰っていきました
- テーブル 3 にお客さんが 4 人やってきました
- テーブル 5 にいるお客さんは何人ですか？ → 答えは 0 人
- テーブル 1 にいるお客さんは何人ですか？ → 答えは 3 人
解答例
あくまで一例です．
マニュアルの例
次のようなマニュアルを作ると，うまく指示を処理することが出来ます．
部屋 i に書かれている数をテーブル i にいるお客さんの人数と対応させます．
指示「テーブル〇にお客さんが△人やってきました」が与えられたら，部屋〇に書かれている数を△に変更します．
指示「テーブル〇のお客さんが全員帰っていきました」が与えられたら，部屋〇に書かれている数を 0 に変更します．
指示「テーブル〇にいるお客さんは何人ですか？」が与えられたら，部屋〇に書かれている数を答えます．
[発展] 情報科学では
情報科学では
情報科学ではこのようなデータ構造を 配列 と呼びます．最も基本的なデータ構造です．
2. 皿洗い (ふつう★☆☆)
設定
次のようなシチュエーションを考えます．
- このお店の厨房では使用済みのお皿がどんどん上に積まれていきます．洗うときは 一番上の お皿を取って洗います．
- それぞれのお皿には色がついています．
- 同時に積まれる皿は 5 枚までです．
- 今は 1 枚も積まれていません．
- あなたはお皿管理担当者になりました．
次の指示が与えられます．
- 「〇色の皿を上に積みます」
- 「一番上に載っている皿は何色ですか？ それを今から洗います」(このとき 1 皿以上積まれています)
積まれているお皿をうまく管理しましょう．
制限
- 使える部屋は 1 ～ 6 です．
- 最初，すべての部屋に 0 と書かれています．
- 各部屋に書けるのは 0 以上 9 以下の整数か色 1 色です．途中で書かれている値の種類を変えても構いません．
- 各指示があったときに開けてもいい窓は 2 つまでです．開けた部屋の値を書き換えても構いません．
例
- 赤色の皿を上に積みます
- 青色の皿を上に積みます
- 黄色の皿を上に積みます
- 一番上に載っている皿は何色ですか？ それを今から洗います → 答えは黄色
- 緑色の皿を上に積みます
- 紫色の皿を上に積みます
- 一番上に載っている皿は何色ですか？ それを今から洗います → 答えは紫色
- 一番上に載っている皿は何色ですか？ それを今から洗います → 答えは緑色
- 一番上に載っている皿は何色ですか？ それを今から洗います → 答えは青色
解答例
あくまで一例です．
マニュアルの例
次のようなマニュアルを作ると，うまく指示を処理することが出来ます．
まず部屋 1 を開けます．今，部屋 1 に書かれている数を s とします．
指示「〇色の皿を上に積みます」が与えられたら，部屋 1 に数 s+1 を書きます．また，部屋 s+2 に色〇を書きます．
指示「一番上に載っている皿は何色ですか？ それを今から洗います」が与えられたら，部屋 1 に数 s-1 を書きます．また，部屋 s+1 に書かれている色を答えます．
[発展] 情報科学では
情報科学では
情報科学ではこのようなデータ構造を スタック と呼びます．次の問題の後で詳しく解説します．
3. 整理券 (ややむずかしい★★☆)
設定
次のようなシチュエーションを考えます．
- たくさんのお客さんが来てくれたので，お店は大パニックです．そこで，整理券を配って 整理券を渡した順に 呼ぶことにしました．
- お客さんの名前は全員アルファベット 1 文字です．
- 同時に待つお客さんは多くても 4 人です．
- 今は誰も待っていません．
- あなたは待っているお客様対応担当者になりました．
次の指示が与えられます．
- 「〇さんに整理券を渡しました」
- 「次に呼べばいいのは誰ですか？ その人を今から呼びます」(このとき 1 人以上待っています)
待っているお客さんの名前をうまく管理しましょう．
制限
- 使える部屋は 1 ～ 6 です．
- 最初，すべての部屋に 0 と書かれています．
- 各部屋に書けるのは 0 以上 9 以下の整数かアルファベット 1 文字です．途中で書かれいている値の種類を変えても構いません．
- 各指示があったときに開けてもいい窓は 2 つまでです．開けた部屋の値を書き換えても構いません．
例
- A さんに整理券を渡しました
- C さんに整理券を渡しました
- B さんに整理券を渡しました
- 次に呼べばいいのは誰ですか？ その人を今から呼びます → 答えは A さん
- X さんに整理券を渡しました
- 次に呼べばいいのは誰ですか？ その人を今から呼びます → 答えは C さん
- Y さんに整理券を渡しました
- 次に呼べばいいのは誰ですか？ その人を今から呼びます → 答えは B さん
- 次に呼べばいいのは誰ですか？ その人を今から呼びます → 答えは X さん
解答例
あくまで一例です．
マニュアルの例
次のようなマニュアルを作ると，うまく指示を処理することが出来ます．
指示「〇さんに整理券を渡しました」が与えられたとき
まず，部屋 5 を開けます．書かれている数を s とします．部屋 5 に s+1 を 4 で割った余りを書きます．
次に，部屋 s+1 を開けます．部屋 s+1 にお客さんの名前〇を書きます．以上．
指示「〇さんに整理券を渡しました」が与えられたとき
まず，部屋 6 を開けます．書かれている数を s とします．部屋 6 に s+1 を 4 で割った余りを書きます．
次に，部屋 s+1 を開けます．部屋 s+1 に書かれているお客さんの名前を答えます．以上．
[発展] 情報科学では
情報科学では
情報科学ではこのようなデータ構造を キュー と呼びます．
上で紹介したスタックとこのキューは，対をなすようなデータ構造です．どちらも「値を追加する」「値を取り出す」という機能を持ってますが，値を取り出す順番が異なります．
後に追加された値を先に出すきまりを Last In First Out (LIFO) と呼び，これを実装したのがスタックです．
先に追加された値を先に出すきまりを First In First Out (FIFO) と呼び，これを実装したのがキューです．
難易度 UP！
- 使える部屋は 1 ～ 6 です．
- 同時に待つお客さんは多くても 5 人です．
この場合の戦略を新たに考えてみましょう．
ヒント
各部屋にはアルファベットしか書きません．
4. 円陣 (むずかしい★★★)
設定
次のようなシチュエーションを考えます．
- 今日はいよいよ新商品の発売日．店員みんなで円陣を組もうとしています．
- 困ったことに，みんな忙しいので輪に入ったり抜けたりしています．
- 店員は 6 人いて，それぞれ A さん，B さん，C さん，D さん，E さん，F さんです．
- 円陣には常に 2 人以上いて，今は A さんと B さんだけがいます．
- あなたは円陣担当者になりました．
次の指示が与えられます．
- 「〇さんの左に△さんが入ります」(このとき〇さんは既に円陣にいます)
- 「〇さんの右に△さんが入ります」(このとき〇さんは既に円陣にいます)
- 「〇さんが円陣から抜けました」(このとき〇さんは既に円陣にいます)
- 「〇さんの左にいるのは誰ですか？」(このとき〇さんは既に円陣にいます)
- 「〇さんの右にいるのは誰ですか？」(このとき〇さんは既に円陣にいます)
円陣に入っている人をうまく管理しましょう．
制限
- 使える部屋は 1 ～ 12 です．
- 最初，すべての部屋に何らかの値を自由に書くことができます．
- 各部屋に書けるのはアルファベット 1 文字です．
- 各指示があったときに開けてもいい窓は 4 つまでです．開けた部屋の値を書き換えても構いません．
例
- A さんの左に C さんが入ります
- A さんの左に D さんが入ります
- C さんの右にいるのは誰ですか？ → 答えは D さん
- D さんが円陣から抜けました
- C さんの右にいるのは誰ですか？ → 答えは A さん
- B さんの右に E さんが入ります
- B さんの左にいるのは誰ですか？ → 答えは A さん
- C さんの左にいるのは誰ですか？ → 答えは E さん
解答例
あくまで一例です．
マニュアルの例
次のようなマニュアルを作ると，うまく指示を処理することが出来ます．
A さんの左にいる人を部屋 1 に書く
A さんの右にいる人を部屋 7 に書く
B さんの左にいる人を部屋 2 に書く
B さんの右にいる人を部屋 8 に書く
...
[発展] 情報科学では
情報科学では
この問題は 連結リスト と呼ばれるデータ構造を参考に作りました．連結リストでは左右にある要素を保持しておくことで，要素の挿入や削除を高速に行うことが出来ます．
5. 年齢調査 (とてもむずかしい★★★★★)
おまけです．とてもむずかしいです．
設定
次のようなシチュエーションを考えます．
- このお店には 12 席のカウンター席があり，一列に並んでいます．それぞれの席には 1 ～ 12 の番号がつけられていて，「カウンター 3」のように呼びます．
- 今，お客さんは 1 人もいません．
- あなたは年齢調査担当者になりました．
次の指示が与えられます．
- 「カウンター〇に△歳のお客さんが座りました」(このとき△は 0 以上 90 以下です)
- 「カウンター〇のお客さんが帰りました」(このときカウンター〇にお客さんはいました)
- 「カウンター〇からカウンター△に座っている人のうち，最も 若い お客さんの年齢はいくつですか？」(このとき△は〇以上で，最低 1 人は座っています)
円陣に入っている人をうまく管理しましょう．
制限
- 使える部屋は 1 ～ 24 です．
- 最初，すべての部屋に 99 と書かれています．
- 各部屋に書けるのは 0 以上 99 以下の整数です．
- 各指示があったときに開けてもいい窓は 6 つまでです．開けた部屋の値を書き換えても構いません．
例
- カウンター 3 に 25 歳のお客さんが座りました
- カウンター 5 に 30 歳のお客さんが座りました
- カウンター 8 に 18 歳のお客さんが座りました
- カウンター 1 からカウンター 6 に座っているお客さんのうち，最も若いお客さんの年齢はいくつですか？ → 答えは 25 歳
- カウンター 4 からカウンター 8 に座っているお客さんのうち，最も若いお客さんの年齢はいくつですか？ → 答えは 18 歳
- カウンター 10 に 20 歳のお客さんが座りました．
- カウンター 8 のお客さんが帰りました
- カウンター 2 からカウンター 11 に座っているお客さんのうち，最も若いお客さんの年齢はいくつですか？ → 答えは 20 歳
解答例
おまけなので，ヒントだけ掲載します．
ヒント：使うデータ構造
Segment Tree と呼ばれるデータ構造を用いると，この問題は解くことが出来ます．説明すると長くなるので，自分で調べてみて下さい．
少し専門的ですが，このスライド もおススメです．33 ページ以降を参照してください．
難易度 UP！
カウンター席を 64 席に増やします．
- 最低でいくつ部屋が必要でしょうか？
- 各指示が与えられたとき，最悪の場合いくつ窓を開ける必要があるでしょうか？
1000 席ならどうでしょうか？
E. さいごに
以上が**「おままごとで学ぶデータ構造」**でした．
この教材を使えば，いろいろな担当の仕事をこなしながら，自然とデータをうまく扱う能力や，物事の手順 (アルゴリズム) を言語化できるようになると考えています．是非さまざまな場面で使ってください．
間違いを見つけられたり，提案をされたい場合はこの記事のコメントにお寄せください．感想も大歓迎です．
この記事がよかったと思っていただけたら，LGTM を是非押してください．ありがとうございました．
F. 参考文献など
この記事で使用している挿絵は いらすとや よりお借りしました．