-1

1 から 1200 までの数字を頭の中で無作為に選択しました。私が「はい」または「いいえ」でしか答えられない質問しかできない場合、私が頭の中で選んだ番号の答えにたどり着く前に、いくつの質問をする必要がありますか?

4

2 に答える 2

5

二分探索を調べます。それがあなたが探しているものです。

http://en.wikipedia.org/wiki/Binary_search_algorithm

上記のリンクで、数当てゲームを検索してください

于 2013-01-20T08:42:22.640 に答える
1

これについては、 http://en.wikipedia.org/wiki/Binary_search_algorithmのウィキペディア ページで説明されていることが既に指摘されています。

答えが ceil(log(1200)/log(2)=11) であることが実際に真であるかどうかを確認するために、もう少し詳しく見てみましょう。これが真であるためには、次の 2 つのことを示す必要があります。

  1. 11の質問で数字を特定できる
  2. 11問未満で番号を特定することはできません

(1) の場合:

誰もが述べたように、二分探索であるアルゴリズムを与えるだけで十分です。例えば:

  • 1024未満です
  • はいの場合、512未満ですか、
    など。

直感を与えるために: 数が 3 であると仮定すると、< 1024 (1 つの質問)、< 512 (2)、< 256 (3)、< 128 (4)、< 64 (5)、< 32 (6) となります。 、< 16 (7)、< 8 (8)、< 4 (9)、(not) < 2 (10)、< 3 (11)。

これは機能しますか?これを厳密に示すことはしませんが、考えている数値が x = a[10]*1+...a[0]*2^10 (バイナリ表現) であるとします。2^10 未満かどうかを尋ね始め、n 番目に sum(a[j]*2^(10-j)+2^(10-n), j=0. ..n-1)。各 i 番目の質問について、答えが「はい」の場合、a[i-1] = 0 (そうでない場合は a[i-1]=1) に注意してください。11 の質問 (i=0,...10) の後、すべての a[0]...a[10] が明らかになります。

(2) については、[繰り返しますが、厳密ではありません]

N 個の質問をしたとします。これらの N 個の質問から、2^N 個の数しか推測できません。これは、答えを出す方法が 2^N 個しかないためです。N < 11 の場合、2^N <= 1024 < 1200 と仮定します。したがって、ピジョン ホールの原理により、N<11 で 1200 個の数字すべてを一意に識別することはできません。

実際、この引数の行 (#2) は、比較ソートが O(n log n) よりも高速ではないことを示すために使用されます。

さて、誰かがこの厳密な :p を 1200 の代わりに M に一般化できるようにできるとよいでしょう。

わかりました、それで十分簡単です。次の質問を許可されている場合はどうでしょうか: 複雑な数式で作成された数値 y は、複雑な数式で作成された数値 z より小さいか、等しいか、または大きいですか? (答えは、より小さい、等しい、またはより大きい) 必要な質問はいくつありますか?

于 2013-01-20T09:16:37.667 に答える