2018-リハーサル-解説

  • 考案国:ベルギー
  • 正解
    • 「Chloe」
  • 説明
    • バレリーナのデュエットの関係を次のように図で表してみましょう。バレリーナを円で表し、デュエットを踊る2人のバレリーナの円の間を線で結びます。

      画像の説明

    • バレリーナのどちらかは次のデュエットを踊り、その上、同じバレリーナが3回連続踊ることがないことから、最初の組で踊って次は踊らないバレリーナの円からスタートして、全ての線をちょうど1回ずつ辿れるはずです。(線は2人のバレリーナを結んでいるので、線を辿る順にその線の2人でリハーサルを踊ります。)
    • そのためには、最初と最後以外のバレリーナは偶数本の線で結ばれている必要があります。このことから、最初と最後のバレリーナはAかFとなります。AともFともデュエットを組まないバレリーナはCだけです。
  • 実際のコンピュータでは
    • データの関係を点と線で表す「グラフ」構造で表現することができます。グラフ構造を用いることで、この問題のようにデータ間の関係を視覚化して扱うことが可能になります。
    • この問題は、「グラフ」構造で考えると「ある点から出発して全て線をちょうど一度ずつ通ることができるか?」という問題となります。このような線のたどり方を「オイラー路」といいます。

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

最新の更新 RSS  Valid XHTML 1.0 Transitional