← 完整题目索引

PROJECT EULER · #0887

有界二分查找

Bounded Binary Search

仅题目 · 待解原题 ↗

考虑通过重复选择数字 y 并询问"该秘密数字是否大于 y?"来从集合 {1,...,N} 中确定秘密数字的问题。

如果 N=1 则无需提出任何问题。如果N=2,那么只需要问一个问题。如果N=64,那么需要问六个问题。然而,在后一种情况下,如果秘密数字是 1,那么仍然需要问六个问题。我们希望限制针对小值提出的问题数量。

Q(N,d) 为能够从集合 {1,...,N} 中找到任何秘密数字的策略所需的最少问题数,其中找到秘密值 x 所需的问题不超过 x+d

可以证明Q(N,0)=N1。您还获得 Q(7,1)=3Q(777,2)=10

d=07N=1710Q(N,d)

题解待补充

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