Tag: 有理数

任意有理数的“猜数”游戏？

我曾经有过面试的问题： 我正在考虑一个正整数n。 提出一个可以在O（lg n）查询中猜测的algorithm。 每个查询都是您select的数字，我会回答“低”，“高”或“正确”。 这个问题可以通过一个修改的二进制search来解决，在这个search中列出两个幂，直到find一个超过n的值，然后在该范围内运行一个标准的二进制search。 我认为对此非常酷的是，你可以search一个特定的数字无限的空间比蛮力更快。 但是，我有这个问题的一个小的修改。 假设我select了一个0到1之间的任意有理数 ，而不是select一个正整数。 我的问题是：什么algorithm可以用来最有效地确定我select了哪个有理数？ 现在，我所拥有的最好的解决scheme可以通过隐式地步行斯特恩 – 布罗科特树 （ Stern-Brocot tree ）来find最多O（q）时间的p / q，二叉search树覆盖所有的合理性。 然而，我希望得到一个更接近运行时的运行时，我们得到的整数情况下，可能是像O（lg（p + q））或O（lg pq）。 有谁知道一种方法来获得这种types的运行时间？ 我最初考虑使用区间[0，1]的标准二进制search，但是这只能find有重复二进制表示的有理数，这几乎是所有的有理数。 我也想过用一些其他的方法来列举理性，但是我似乎无法find一种比较大/相等/较less比较的方法来search这个空间。