algorithm - 数字を推測するために、どれだけ質問を減らすことができますか?

Question

頭の中で 1 から 1200 までの数字を選んでもらうとします。彼がイエスかノーでしか答えない質問しかできない場合、彼が私の頭の中で選んだ数字の答えにたどり着く前に、いくつの質問をする必要がありますか?

できるだけ少ない質問数を探しています。実証済みのソリューションはどれも評価に値します。

Answer 1

1からnまでの数字のどれが選択されているかを判断するには、少なくともlog2nの質問をする必要があり_ます。より良い方法はありません。

この答えの直感は次のとおりです。合計k個の質問をするとします。それらが互いに依存している場合でも、それらの質問に対して受け取ることができるさまざまな可能な回答の最大数は^2kです。選択できる可能性のある数はn個あるため、次のようにkを選択する必要があります。

^2k≥n _ _

これは正確に

k≥log2n _{_} _

言い換えれば、それぞれの可能な数をいくつかの可能な結果に関連付けるのに十分な異なる可能な結果を​​得ることができるように、少なくともlog2nの質問をする必要があります_。質問の数は常に自然数でなければならないため、質問できる最小数は少なくとも⌈log2n⌉でなければなりませ_ん。

これは純粋に答えの下限です。現時点では、答えを得るためにこれよりはるかに多くの質問が必要になる可能性を排除することはできません。ただし、バイナリ検索アルゴリズムについて知っているということは、回答を得るために⌈log2n⌉以上の質問が必要になることはないということを意味します_。これは、バイナリを実行している場合に尋ねる質問の数だからです。探す。これは、少数の質問をする方法がないため、二分探索アルゴリズムを最適化する必要があることを意味します。

お役に立てれば！

Answer 2

1200の対数基数2、整数に切り上げ：11です。基本的に、すべての質問は可能な範囲を半分にカットするため、可能な範囲の長さが1になるまでバイナリ検索を続行します。

Answer 3

数のすべてのビットを求めます。そのためには11の質問で十分です。編集：少なくとも最悪の場合、2進表現と10進表現の間の二元性のために、これ以上のことは不可能だと私は主張します。

Answer 4

これは、下限の複雑さを見つけるために使用される敵対的引数法の古典的な例でもあります。私たちの場合、番号を知っている人が敵です。そのため、あなたが新しい質問をすると、彼は賢明にも本当の答えを変えるでしょう。彼は各ステップでの答えをどのように決定しますか? たとえば、数値が 1 ～ 100 の間であるとします。

あなたは尋ねます: n>=50 ですか?. 彼は、間隔が等しいので、YES または NO と言うかもしれません。彼がイエスと言ったとしましょう。

次に、50<=N<=100 の間の数を言います。たとえば、n>=80 とします。次に、彼が選んだ数が 80 より大きい場合でも、50<=n<=80 はより大きな間隔。現在、数値は 50 から 80 の間である可能性があります

この方法を維持すると、二分探索のように間隔サイズが減少するため、ログに記録される質問の最大数が保証されます。