我在脑海中随机选择了一个 1 到 1200 之间的数字。如果你只能问我只会回答“是”或“否”的问题，你需要问多少问题才能得到我在脑海中选择的数字的答案？
问问题
148 次
2 回答
5
于 2013-01-20T08:42:22.640 回答
1
已经指出，这在http://en.wikipedia.org/wiki/Binary_search_algorithm的维基百科页面中进行了讨论。
让我们更详细地看一下，看看答案是否真的是 ceil(log(1200)/log(2)=11。要做到这一点，我们必须证明两件事：
- 可以在 11 个问题中识别数字
- 在少于 11 个问题中无法确定数字
对于（1）：
正如大家所说，给出二分搜索算法就足够了。例如：
- 小于 1024
- 如果是，是否小于 512，
等等。
给出一个直觉：假设数字是 3，那么我们有 < 1024 (1 个问题), < 512 (2), < 256 (3), < 128 (4), < 64 (5), < 32 (6) , < 16 (7), < 8 (8), < 4 (9), (not) < 2 (10), < 3 (11)。
这行得通吗？我不会严格展示这一点，但假设您正在考虑的数字是 x = a[10]*1+...a[0]*2^10 （二进制表示）。观察你开始问它是否小于 2^10，然后对于 nth，你问它是否小于 sum(a[j]*2^(10-j)+2^(10-n), j=0. ..n-1)。观察对于每个第 i 个问题，如果答案是肯定的，那么 a[i-1] = 0（否则 a[i-1]=1）。在 11 个问题 (i=0,...10) 之后，您将发现所有 a[0]...a[10]。
对于（2），[再次，不严格]
假设你问了 N 个问题。从这 N 个问题中，你只能推断出 2^N 个数字，因为只有 2^N 种可能的方法可以得出答案。假设 N < 11，则 2^N <= 1024 < 1200。所以根据鸽子洞原理，您不能唯一标识 N<11 的所有 1200 个数字。
事实上，这行论点（#2）是用来说明比较排序不能比 O(n log n) 快的。
现在，如果有人可以使这个严格：p 也可以推广到 M 而不是 1200，那就太好了。
好的，这很容易，如果您可以问：由复杂公式构造的数字 y 是否小于、等于或大于由复杂公式构造的数字 z？（答案可以小于、等于或大于）您需要多少个问题？
于 2013-01-20T09:16:37.667 回答