给定两个整数 a, b, 其中 a<=b. 给定一个函数, bool is_greater(int c)
, 当 c>b 时返回 true. 告知 a, 要猜 b, 怎么做最有效?
brute force 的话, 就是让 c=a, 逐渐+1, 直到is_greater(c)==false
, 则 b=c-1
1
thedrwu 2019-04-23 12:46:19 +08:00 via Android
二分
|
2
lance6716 2019-04-23 12:49:41 +08:00 via Android 2
Exponential search
|
3
nanaw 2019-04-23 12:53:06 +08:00
得有个 b 最大的可能范围才能二分吧。这样无限大怎么猜。。
|
4
geelaw 2019-04-23 12:55:01 +08:00
如果你假设 int 是有限范围,可以直接二分,甚至不需要知道 a。
如果你假设 int 是无限范围且 a < 0,则先通过测试 -1、0 确定 b 的符号;如果 b 是负数,则你已经有上下界,用二分;如果 b 是 0,则结束;如果 b 是正数,则不断测试一个数是否是上界,直到找到上下界,再用二分。 你需要定义什么叫做“最有效”,才能决定如何询问“最有效” 。 |
5
Kirscheis 2019-04-23 13:07:05 +08:00 via Android 1
先指数前进,然后二分即可
|
6
rrfeng 2019-04-23 13:22:41 +08:00 via Android
如果我操作的话选指数前进,再二分定位。
但实际上感觉可以算出来期望次数 |
8
melonux OP @geelaw 好的. 更具体一些. b 就在 uint_32 的范围内. 最有效指的是调用 is_greater 函数的次数的期望值最小.
|
10
geelaw 2019-04-23 15:02:27 +08:00 1
|
11
melonux OP 嗯. 您这个考虑更加精细了. 那就给个指数分布吧. 用意是 b 更可能出现在离 a 较近的地方. pdf(b-a)=exp(-(b-a))
|
13
lance6716 2019-04-23 17:18:34 +08:00
@melonux 指数分布是无记忆的(不知道在这个离散程度和规模下能不能这么概括),给定搜索的区间[low, high],只跟区间长度有关
均匀分布的时候二分中点。不均匀就二分“累计概率达到一半”的那个点 |
14
melonux OP @lance6716 嗯. 您说的对. 给定范围和给定这个分布本身冲突了. 我的本意是均匀分布即可. 但看到那个可以动态规划的方法, 就很好奇. 想看到一个不平凡的解, 所以给了一个不均匀的分布.
|
15
geelaw 2019-04-23 22:31:31 +08:00 via iPhone 1
@melonux #12 如果是均匀分布显然二分法就是动态规划会给出的解。如果是几何分布,不妨设 a=0 (其他情况把各数虚拟地加上 -a 即可),用 f(x) 表示上界是 c 时(也就是范围是 (0, x])最小期望次数,那么
f(1) = 0 f(n) = 1 + min ( Pr[b>c] f(n-c) + Pr[b<=c] f(c) ) 对于初始无上界的情况,这是一个 Markov 链,因此有 f(infty) = 1 + inf ( Pr[b>c] f(infty) + Pr[b<=c] f(c) ) f(infty) = inf (1/Pr[b<=c] + f(c)) 利用有限值的 f 的情况算出最佳的 c。 |