1

考虑数字 20 题游戏。在这个游戏中,玩家 1 想出一个介于 1 到 n 之间的数字。玩家 2 必须通过询问最少数量的真/假问题来计算出这个数字。假设没有人作弊。一世。如果 n 已知,最优策略是什么?ii. 什么是好的策略是 n 未知?

4

1 回答 1

7

请参考这个wiki:二分搜索数字猜谜游戏

如果 n 已知,则使用二分查找算法查找,所以问的问题不超过floor(log2(n)).

如果 n 未知,您可以先通过重复加倍找到一个上限,然后应用二分查找。很明显,问的问题不超过2 * floor(log2(k)) + 1,其中 k 是未知的选定数。

于 2013-02-21T13:36:40.290 回答