YES または NOで答える質問のテストがありますN。テストを受けて、教授が正解の数を教えてくれます。テストに合格する最も早い方法は何ですか? つまり、最小限の試行回数ですべての質問に正解することです。
上院試行による解決法はN+1明らかです。試行ごとに、1 つの質問に対する正解が得られます。これは 1 ビットの情報です。しかし、教授は毎回 0 から N までの数字を私たちに与えます。これは log 2 (N + 1) ビットの情報です。これが、最適な解決策がO(N / log(N))複雑である理由です。線形以下の最悪の時間計算量を持つソリューションを探しています。
ベストアンサー1
N+1 ソリューションに対する明らかな改善点:
すべて Y の回答から始めます。
そうすれば、「はい」と「いいえ」が正確にいくつあるかがわかります。
一般性を失うことなく、p任意の位置で「はい」となる確率を とします。p >= 1/2
次に、試行回数の平均で最初の 2 つの回答を明らかにします2 - p^2。
最初の 2 つの質問に対する答えを変更します。少なくとも、p^2両方の質問に対する正確な答えがわかるでしょう。そうでない場合は、少なくとも 1 つが Y で、もう 1 つが N であることがわかっているので、もう 1 つ質問する必要があります。
だから最悪の場合、p = 1/2私は必要になります1 + N * 7/8。