CadetAnswer2018

カデット問題解説(中学1年生・2年生)

  • A

    2018-島をつなぐ橋-解説

    • 考案国:イタリア
    • 正解
      • 「36」
    • 説明
      • 橋でつながっている2つの島の数を足し合わせると、いちばん小さい数は「25と12の37」で、すべてが37以上であることがわかります。
        橋でつながっていない2つの島の数を足し合わせると、いちばん大きい数は「11と25の36」で、すべてが36以下であることがわかります。
    • 実際のコンピュータでは
      • この問題の橋と島のような関係を表現するために、点と線で表現する「グラフ」というデータ構造が使われます。「36以下は橋を作らない」「37以上なら橋を作る」のような「条件によって処理を行うかを決める」条件分岐という考え方はコンピュータのプログラムで有効に利用されています。

    2018-レモネードパーティ-解説

    • 考案国:アメリカ
    • 正解
      • 画像の説明
    • 説明
      • 正解は「32リットル、4リットル、1リットル」の組み合わせです。
        大きな瓶から試していきましょう。37リットルから32リットルの瓶に入れると、残りは5リットル。5リットルから4リットルの瓶に入れると残りは1リットル。これはちょうど1リットルの瓶に入ります。
    • 実際のコンピュータでは
      • 私たちは生活の中で「1,10,100,1000,...」のように、10倍ずつの数を使う「10進法」で数を扱っています。
        コンピュータの中では、1,2,4,8,16,32,...のように、2倍ずつの数を使う「2進法」で数を扱っています。

    2018-キャンプ-解説

    • 考案国:韓国
    • 正解
      • 「海、山」
    • 説明
      • 公園に行くと、バドミントンのラケットと野球のグローブより右に、残りの3個が並びます。もう一箇所に行ったとしても、3個のうち1個は右に残ってしまいます。よって、公園には行っていないことがわかります。
    • 実際のコンピュータでは
      • この問題ではモノが横に並んだ配列を表しています。「いちばん最後に使ったものを端に移す」アルゴリズムはLRUと呼ばれ、日本語変換で漢字の候補を表示する際に使われています。

    2018-ぬり絵-解説

    • 考案国:イギリス
    • 正解例

      画像の説明

    • 説明
      • 3色で塗り分けることができますが、2色では塗り分けることはできません。正解例のように3色で塗り分けられると正解となります。
    • 実際のコンピュータでは
  • B

    2018-ふうせん-解説

    • 考案国:アイルランド
    • 正解
      • 「1と3」
    • 説明
      • AとC,DとBは同じに見えます。CをAに、DをBに、それぞれ置き換えて見比べてみましょう。
    • 実際のコンピュータでは
      • 文字の並びを比較することはコンピュータの処理でよく行われます。私たちが使う文字の検索でも、「Aとaのような大文字と小文字」「あとアのような仮名」を同一に扱う検索は便利に使われています。

    2018-水もれ-解説

    • 考案国:南アフリカ共和国
    • 正解
      • 「4」
    • 説明
      • 最初は、16軒の家のどこで水漏れがおきているか分かりません。
      • まず、15 個の中で真ん中の8軒目と9軒目のバルブを閉めます。メーターが動いてると1軒目〜8軒目のどこかで、メーターが止まると9軒目から16軒目のどこかで、水漏れがおきていることが分かります。つまり、水漏れがおきている可能性がある場所が16ヶ所から8ヶ所と、半分になります。
      • 水漏れがおきている可能性がある場所の真ん中のバルフを閉めることで 水漏れがおきている可能性がある場所を半分にするということを繰り返すと、2回目で可能性がある場所は4ヶ所となり、3回目で2ヶ所ととなり、4回目で1ヶ所、つまり、水漏れしている場所を特定できます。
    • 実際のコンピュータでは
      • 上の説明のように、目的のデータや障害の箇所を探すのに、対象を半分ずつに分けて探しているデータや原因がどちらにあるかを探していく方法を、二分探索といいます。
      • この問題では、原因を左から順に探していくと、最悪の場合は16回の検査が必要になってしまいます。4回で原因を特定できる二分探索のようなアルゴリズムは大量のデータを扱うときに有用です。

    2018-スケジュール-解説

    • 考案国:インドネシア
    • 正解

      画像の説明

    • 説明
      • コンピュータになったつもりで、ルールのとおりに色を塗っていきましょう。
    • 実際のコンピュータでは
      • コンピュータは「文字の入力」「日本語変換」「ネットワーク通信」「時刻の表示」などの複数の処理を、細かく処理を分割することで並行して行っています。ひとつの処理だけに時間を使って他の処理が止まらないように、全体の処理のバランスを取ることは重要です。

    2018-無限のアイスクリーム-解説

    • 考案国:アイルランド
    • 正解

      正解の図

    • 説明
      • 手順1で2個のフレーバー「AA」を置き、手順2で1個のフレーバー「B」を置くことを繰り返すとき、Bは直前のAAとは違った色にする必要があります。このルールに当てはまらないものを探しましょう。
    • 実際のコンピュータでは
      • 画像はピクセルと呼ばれる細かい点の集まりで表現されます。コンピュータは大量のピクセルの中からパターンを探すことで、画像の処理や検索を行っています。
  • C

    2018-矢印-解説

    • 考案国:ハンガリー
    • 正解

      画像の説明

    • 説明
      • 条件を満たす解を見つけるため、ある矢印から始めて、仮に白か黒に決め、その矢印が指している矢印の色を条件を満たすように仮に決める(複数の可能性がある場合は、そのうちの一つを選び)ということを繰り返し、うまく選べなくなったら複数の可能性から選択した矢印まで戻り、まだ試してない可能性を選択するという方法があります。戻ったとき、もう選ぶ選択肢がない場合は、さらに戻ります。
      • このように、ある状況から可能性を探索し、ステップバイステップで進み、行き詰まるともとに戻る方法を、情報科学ではバックトラックと言います。 バックトラックは、8クイーンパズルや数独などのパズルを解くのに、また,ナップザック問題などの組み合わせ最適化問題を解決するのにも使用できます。他にも、様々な応用があります。
        https://ja.wikipedia.org/wiki/バックトラッキング
        https://ja.wikipedia.org/wiki/論理プログラミング

     

    2018-関係-解説

    • 考案国:カナダ
    • 正解
      • 「5」
    • 説明
      • まず、上段中央の「=4」の円に注目します。この円とつながっている円はちょうど4つなので、つながっている4つの円全てに色を塗りましょう。
      • 次に、右下の「=2」の円に注目します。この円とつながっている円はちょうど2つなので、つながっている2つの円に色を塗りましょう。
      • すると下の図のようになります。この図で、残りの円の条件を見ていくと、すべての条件が満たされていることがわかります。よって、この時点で塗られた5個の円が正解になります。

        解答例

    • 実際のコンピュータでは
      • いろいろな組み合わせが考えられる問題を、手当たり次第に解くと時間がかかってしまいます。この問題には9個の円がありましたので、すべての組み合わせを考えると512通りについて考えなければなりません。そこで、今回の解法のように、調べる組み合わせの候補を少なくする工夫が行われています。

    2018-手旗信号-解説

    • 考案国:台湾
    • 正解
      • 「QPPTP」
    • 説明
      • 「水平を0、垂直を1」で表すと、次のようになります。
        問題  :10010010
        RPQSR:100100110
        RPSP :1000010
        QPPTP:10010010
        TSQ :10010011
    • 実際のコンピュータでは
      • コンピュータは2進数で動くため、文字も0と1の組み合わせで表現しています。どの文字にどのような0と1の組み合わせを割り当てるかは重要です。この問題のように「S(10)はQ(1)とP(0)の並びとも解釈できる」ような割り当てにすると、解釈に曖昧さが生まれてしまいます。実は、選択肢にはありませんが、TSP (10010011) も問題の図の信号になります。

    2018-短いプログラム-解説

    • 考案国:イギリス
    • 正解例

      正解例

    • 説明
      • 解答を得るアプローチを1つ示しましょう:
        • まずは、ブロックの数が多くても良いのでゴールに到達できる単純なプログラムを作成します。
        • 次に、同じブロックのパターンを繰り返している部分を repeat でまとめて、使用するブロックの数を減らします。これを何度か繰り返します。
      • 道順によっては、使用するブロックの数を十分小さくできないこともあるでしょう。この迷路の場合は、スタートのあたりは道順がいろいろと考えられますが、図1のように、途中からは一本道です。途中からの道順を良く観察して解析すると、図2のようにパターンを繰り返せば良いことが分かるでしょう。
      • 図2の道順で進むことにして、単純なプログラムをつくって見ましょう。図3・図4のようにまとめられそうなブロックのパターンを見つけます。
        図1図2
        Step1Step2
        図3図4
        Step3Step4
    • 実際のコンピュータでは
      • この問題では、繰り返されているパターンを見つけて、問題を解決しました。
        これは、プログラマのコードをタイプする手間を節約するだけでなく、エラーがあった場合にそれをすばやく修正するのにも役立ちます。
        繰り返しを活用しなければ、この問題では29個のブロックを使用する必要があります。
      • 情報科学やプログラミングにおいて、パターンにうまく抽出することは、あるタイプの問題に対する適切な解決方法を知る上で重要です。パターンや類似の特性に気づくことで、解決法の道筋を見つけ、問題を解決できます。
      • この問題であなたが発見した繰り返しのパターンは、アルゴリズムやプログラムの反復構造になります。

カデット問題に戻る

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

最新の更新 RSS  Valid XHTML 1.0 Transitional