0

「次のゲーム[Gar94]、＃52で予想される質問の数を最小限に抑える戦略を設計します。スペードのエース1枚、スペードのデュース2枚、スリー3枚、最大9枚で構成されるカードのデッキがあります。ナイン、全部で45枚のカードを作ります。誰かがシャッフルデッキからカードを1枚引き出します。これは、「はい」または「いいえ」で答えられる質問をすることで識別できます。」

これは、アルゴリズムの設計と分析からの演習です。

私の頭に浮かぶのは、それを解決する2つの方法です。

  1. 9ですか？いいえ：それは8ですか？いいえ：7ですか？... 等々。

  2. カードは>5ですか？いいえ：カードは2を超えていますか？... 等々。

正しいアプローチはどれですか？

どんな助けでも大歓迎です。

編集：欲張り法を使用することになっています。

4

1 に答える 1

5

どちらも最善のアプローチではありません。質問をさらに一般化して、「選択したカードは1、4、7、または8のいずれかですか？」のようにすることができます。

どの質問をするかを決めるには、数字を含むハフマンツリーを作成します。次に、「選択したカードは左側のサブツリーの番号の1つですか？」と尋ねます。そうである場合は、左側のサブツリーに移動して繰り返します。それ以外の場合は、右側のサブツリーに移動して繰り返します。

于 2012-10-21T16:00:54.567 に答える