algorithm - 並べ替えアルゴリズムを使用する

Question

数字の 20 問のゲームを考えてみましょう。このゲームでは、プレイヤー 1 は 1 から n までの範囲の数字を考えます。プレイヤー 2 は、真偽の質問をできるだけ少なくすることによって、この数を把握する必要があります。私。nが既知の場合、最適な戦略は何ですか? ii. n が不明な場合の適切な戦略とは?

Answer 1

この wiki を参照してください:数当てゲームの二分探索.

n がわかっている場合は、二分探索アルゴリズムを使用してそれを見つけますfloor(log2(n))。

n が不明な場合は、最初に倍加を繰り返して上限を見つけてから、二分探索を適用できます。尋ねられた質問が を超えないことは明らかです2 * floor(log2(k)) + 1。ここで、k は不明な選択数です。