use*_*893 1 algorithm search integer set
想象一下,我们有一组整数.我们不知道,我们唯一知道的是每个数字都在区间[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)中没有数字.)尝试次数最少的算法将是答案.
我可能在这里误解了一些东西,但在我看来你刚刚开始MAX,因此收到了集合中最大的数字.然后继续猜测收到的数字 - 1直到没有更多的数字,或达到0.这将需要每个数字一次猜测.
对？
| 归档时间： |
|
| 查看次数： |
140 次 |
| 最近记录： |