← 完整题目索引

PROJECT EULER · #0527

随机二分查找

Randomized Binary Search

仅题目 · 待解原题 ↗

1tn 范围内随机选择一个秘密整数 t

目标是通过整数 g 进行重复猜测来猜测 t 的值。做出猜测后,有​​三种可能的结果,其中将显示 g<tg=tg>t。然后可以根据需要重复该过程。

通常,可以通过二分搜索最小化平均所需的猜测次数:给定下限 L 和上限 H(初始化为 L=1H=n),令 g=(L+H)/2 其中 是整数下取整函数。如果g=t,则过程结束。否则,如果 g<t,则设置 L=g+1,但如果 g>t,则设置 H=g1。设置新边界后,搜索过程会重复,并最终在找到 t 后结束。即使无需搜索即可推导出 t,也假设无论如何都需要搜索来确认该值。

你的朋友 Bob 认为标准二分搜索并不比他的随机变体好多少:不要设置 g=(L+H)/2,只需让 gLH 之间的随机整数(含)。该算法的其余部分与标准二分搜索相同。这个新的搜索例程将被称为随机二分搜索

假设随机 t1tn,令 B(n) 为使用标准二分搜索找到 t 所需的预期猜测次数,并令 R(n) 为使用随机二分搜索找到 t 所需的预期猜测次数。例如,四舍五入到小数点后 8 位时,B(6)=2.33333333R(6)=2.71666667

R(1010)B(1010) 四舍五入到 8 小数位。

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。