找到任意大数的算法
发布时间：2020-12-14 05:10:33 所属栏目：大数据 来源：网络整理
导读：这是我一直在考虑的事情：假设你有一个数字,x,可以是无限大,你必须找出它是什么.所有你知道的是,如果另一个数字y大于或小于x.找到x的最快/最好的方法是什么？ 一个邪恶的对手选择了一个非常大的数字……说： int x = 9^9^9^9^9^9^9^9^9^9^9^9^9^9^9 并提供is
|
这是我一直在考虑的事情：假设你有一个数字,x,可以是无限大,你必须找出它是什么.所有你知道的是,如果另一个数字y大于或小于x.找到x的最快/最好的方法是什么？
一个邪恶的对手选择了一个非常大的数字……说： int x = 9^9^9^9^9^9^9^9^9^9^9^9^9^9^9 并提供isX,isBiggerThanX和isSmallerThanx函数.示例代码可能如下所示： int c = 2
int y = 2
while(true)
if isX(y) return true
if(isBiggerThanX(y)) fn()
else y = y^c
其中fn()是一个函数,一旦找到数字y(大于x)就会确定x(比如将数字除以一半并进行比较,然后重复).问题是,因为x是任意大的,所以使用常数来增加y似乎是个坏主意. 这只是我一直想知道的事情,我想听听其他人的想法 解决方法
使用二进制搜索,就像通常的“尝试猜测我的号码”游戏一样.但由于没有有限的上限点,我们会在第一阶段找到合适的上端点：
>最初任意设置上端点(例如1000000,虽然1或1 ^ 100也可以工作 – 给定无限空间工作,所有有限值同样不成比例). 第一阶段本身类似于二元搜索.不同之处在于,不是每一步都将搜索空间减半,而是将其翻倍！每个阶段的成本是O(log X).一个小的改进是在每个倍增步骤设置低端点：我们知道X至少与前一个高端点一样高,所以我们可以将它重用为低端点.搜索空间的大小在每一步仍然翻倍,但最终它将是原来的一半.二进制搜索的成本将仅减少一步,因此其总体复杂性保持不变. 一些笔记 回应其他评论的几点说明： 这是一个有趣的问题,计算机科学不只是关于在物理机器上可以做什么.只要问题可以正确定义,就值得提出并思考. 数字范围是无限的,但任何可能的神秘数字都是有限的.所以上面的方法最终会找到它.最终定义为,对于任何可能的有限输入,算法将在有限数量的步骤内终止.然而,由于输入是无限制的,步骤的数量也是无限的(只是在每种特定情况下,它将“最终”终止.) （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |