猜测x+y价值的最佳方法是什么？
当我们只想猜测一个数字时，问题就很简单了。例如，我们想猜测x，我们知道最高可能的值是n，我们可以进行二进制搜索，其复杂度是O(log )。
然而，我发现这个问题的不同之处：
给定0
假设猜测是z，我们可以要求发问者与其他值进行比较，他会告诉z和其他值之间的关系--即小于、等于或大于。可能的比较如下：
(1)比较x和z。
(2)比较y和z。
(3)比较x+y和z。
在我看来，我们只需在(x+y)上进行二进制搜索。因此，时间复杂度是O( log(m+n))。这比找到x要好，而y的复杂度是O(log m+ log n) = O(log mn)。
但是，我很好奇是否有比在x+y上进行二进制搜索更好的解决方案。
非常感谢你的帮助。
编辑:所以发问者首先考虑数字x和数字y，然后问回答者x+y的值是多少，答案者可以进行三次查询，如下所示。我的问题是，答案者如何在最少的查询次数下找到答案。
回答 1
Stack Overflow用户
发布于 2014-02-20 01:50:12
当每种可能性都有相同的概率时，二值搜索是最优的。x和y的情况都是这样，但x+y的情况并非如此。平均来说，获得最少猜测的策略可能类似于二进制搜索，但并不完全是二进制搜索。
使用二进制搜索，所有的可能性都是相同的。
probability | |
| [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] |
| [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] |
| [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] |
|_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16我们猜测中间部分，并放弃一半可能的答案：
probability | V X X X X X X X X X |
| [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] |
| [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] |
| [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] |
|_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16所有剩余的答案仍然是同样可能的，所以我们可以简单地回溯。
当在一个均匀概率范围内随机选取x和y的x+y时，每个x+y的概率并不相等。
probability | V |
| [] |
| [] [] [] |
| [] [] [] [] [] |
| [] [] [] [] [] [] [] |
| [] [] [] [] [] [] [] [] [] |
| [] [] [] [] [] [] [] [] [] [] [] |
| [] [] [] [] [] [] [] [] [] [] [] [] [] |
|____[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 显然，猜测中间部分仍然是最好的第一次猜测：
probability | V X X X X X X X |
| [] |
| [] [] [] |
| [] [] [] [] [] |
| [] [] [] [] [] [] [] |
| [] [] [] [] [] [] [] [] [] |
| [] [] [] [] [] [] [] [] [] [] [] |
| [] [] [] [] [] [] [] [] [] [] [] [] [] |
|____[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 但不直观的是，接下来要猜测的是哪里。在上图中，8之后的最佳猜测是5或6(不是4)，但我不知道如何准确计算。如果我搞清楚了我会告诉你的。
v = lower_bound
u = upper_bound
t = probability(v)
s = probability(u)
r = min(s,t)
p = guess
(p-v)r+(p-v)^2/2 = (u-p)r+(u-p)^2/2
pr-rv+(p^2-pv+v^2)/2 = ur-pr+(u^2-up+p^2)/2
2pr-2rv+p^2-pv+v^2 = 2ur-2pr+u^2-up+p^2
2pr-2rv+p^2-pv+v^2-2pr+up-p^2 = 2ur+u^2
2pr+p^2-pv-2pr+up-p^2 = 2ur+u^2+2rv-v^2
-pv+up = 2ur+u^2+2rv-v^2
(u-v)p = u^2+2ur+2rv-v^2
p = (u^2+2ur+2rv-v^2)/(u-v)不，这也是错误的。还在努力呢。
尼可拉斯B.观察到，这个答案中的所有东西都假定x和y都是从它们的范围内均匀挑选出来的。如果这不是一个安全的假设，那么是的，二进制搜索平均来说是最快的。
https://stackoverflow.com/questions/21895810
复制相似问题
腾讯云开发者
