algorithm - 使用排序算法

Question

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

Answer 1

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

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

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