如果我们被告知最接近的小于或等于我们告诉的数字，则找到一组整数的有效算法
想象一下我们有一组整数。我们不知道，我们唯一知道的是每个数字都位于区间 [0, MAX) 内，并且显然，数字不会重复。然后，我们需要找到一个集合。我们可以命名一个整数，然后我们被告知集合中的一个数字，该数字小于或等于我们选择的数字并且最接近它。我们的目的是找到一个尝试次数最少的集合。
例如，让我们有一个集合 [0, 7, 8, 1000]，并且 MAX==10000。让 TRY 成为我们可以使用的函数。然后 TRY(4)==0、TRY(7)==7、TRY(8)==8、TRY(555)==8 和 TRY(7777)==1000。然后我们必须确保我们没有错过任何一个号码，因此我们必须尝试许多其他号码。
问题是：找到集合最有效的算法是什么？尝试间隔中的每个数字显然是不好的。也许我们应该尝试一种类似二分搜索的算法，它排除集合，保证没有数字（TRY(7777)==1000，所以 (1000, 7777]) 中没有数字。尝试次数最少的算法是答案。
Imagine that we have a set of integers. We don't know it, the only thing we know is that every number lies in interval [0, MAX), and, obviously, numbers do not repeat. Then, we need to find a set. We are allowed to name an integer, and then we are told a number in set, which is less or equal than number we've chosen and is closest to it. Our purpose is to find a set with minimal number of tries.
For example, let us have a set [0, 7, 8, 1000], and MAX==10000. Let TRY be the function we can use. Then TRY(4)==0, TRY(7)==7, TRY(8)==8, TRY(555)==8 and TRY(7777)==1000. We then must get sure that we didn't miss a number, so we must try many other numbers.
The question is: what is the most efficient algorithm to find the set? Trying every number in interval is obviously bad. Maybe we should try a binary-search-like algorithm which excludes sets, which are guaranteed to have no numbers (TRY(7777)==1000, so no numbers in (1000, 7777]). Algorithm with minimal number of tries would be the answer.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我可能会误解这里的一些内容，但在我看来，您将从
MAX开始，从而收到集合中最大的数字。然后继续猜测收到的数字 - 1，直到没有更多数字剩余，或者达到 0。这需要对每个数字进行一次猜测。正确的？
I might be misunderstanding something here, but it seems to me you'll just start at
MAX, thus recieving the largest number in the set. Then just continue guessing at the recieved number - 1 until no more numbers remain, or 0 is reached. This would require one guess per number.Right?