如果我让一个人在他的脑海中选择一个介于 1 到 1200 之间的数字。如果我只能问他只会回答“是”或“否”的问题，我需要问多少个问题才能得到他在我脑海中选择的数字的答案？
我正在寻找尽可能少的问题。任何经过验证的解决方案都将是可观的。
问问题
2312 次
4 回答
5
要确定选择 1 和 n 之间的哪个数字，您需要至少询问 log 2 n 个问题。没有办法做得更好。
这个答案的直觉如下。假设你一共问了 k 个问题。对于这些问题，即使它们相互依赖，您可以收到的不同可能答案的最大数量是 2 k。由于可以选择 n 个可能的数字，因此您需要选择 k 使得
2 k ≥ n
这恰好发生在
k≥log 2 n
换句话说，你必须至少问 log 2 n 个问题，才能获得足够多不同的可能结果，以便将每个可能的数字与一些可能的结果联系起来。由于问题的数量必须始终是自然数，因此您可以提出的最小问题数量必须至少为 ⌈log 2 n⌉
这纯粹是答案的下限。在这一点上，我们不能排除您可能需要比这更多的问题才能得到答案的可能性。然而，我们知道二分搜索算法这一事实意味着我们知道你永远不需要超过 ⌈log 2 n⌉ 个问题来获得答案，因为这是你在做二分搜索时会问的问题的数量搜索。这意味着二分搜索算法必须是最优的，因为不可能问出更少的问题。
希望这可以帮助！
于 2013-01-20T21:19:39.373 回答
1
以 2 为底的 1200 的对数，四舍五入为整数：即 11。基本上，每个问题都将可能范围减半，因此您只需继续进行二分搜索，直到可能范围的长度为 1。
于 2013-01-20T21:19:24.560 回答
0
这也是对抗性参数方法的经典示例，用于查找下限复杂度。在我们的例子中，知道号码的人就是对手。所以当你问一个新问题时，他会明智地改变他的真实答案。他如何确定每一步的答案？例如，数字在 1-100 之间。
你问：是n>=50吗？他可能会说“是”或“否”对他来说都一样好，因为间隔是相等的。假设他说是的。
然后你说一个介于 50<=N<=100 之间的数字，假设你问：is n>=80。那么即使他选择的数字大于 80，他也应该说 NO，因为 50<=n<=80 是更大的间隔。现在这个数字可能在 50 到 80 之间
保持这种方式，他将保证最大问题数，即 logn，因为间隔大小像二进制搜索一样减小
于 2013-01-20T22:49:53.713 回答
0
询问数字中的所有位。11个问题就足够了。编辑：我认为，由于二进制和十进制表示之间的双射性，不可能做得更好——至少在最坏的情况下是这样。
于 2013-01-20T21:20:25.327 回答