1 から 1200 までの数字を頭の中で無作為に選択しました。私が「はい」または「いいえ」でしか答えられない質問しかできない場合、私が頭の中で選んだ番号の答えにたどり着く前に、いくつの質問をする必要がありますか?
2 に答える
二分探索を調べます。それがあなたが探しているものです。
http://en.wikipedia.org/wiki/Binary_search_algorithm
上記のリンクで、数当てゲームを検索してください
これについては、 http://en.wikipedia.org/wiki/Binary_search_algorithmのウィキペディア ページで説明されていることが既に指摘されています。
答えが ceil(log(1200)/log(2)=11) であることが実際に真であるかどうかを確認するために、もう少し詳しく見てみましょう。これが真であるためには、次の 2 つのことを示す必要があります。
- 11の質問で数字を特定できる
- 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 より小さいか、等しいか、または大きいですか? (答えは、より小さい、等しい、またはより大きい) 必要な質問はいくつありますか?