问题标签 [rational-numbers]

我曾经收到以下面试问题：

我在想一个正整数n。想出一个可以在 O(lg n) 查询中猜测它的算法。每个查询都是您选择的数字，我将回答“较低”、“较高”或“正确”。

这个问题可以通过修改后的二分搜索来解决，其中列出 2 的幂，直到找到一个超过 n 的幂，然后在该范围内运行标准二分搜索。我认为这很酷的是，您可以比蛮力更快地搜索无限空间中的特定数字。

不过，我的问题是对这个问题的轻微修改。假设我选择了一个介于 0 和 1 之间的任意有理数，而不是选择一个正整数。我的问题是：你可以使用什么算法来最有效地确定我选择的有理数？

现在，我拥有的最佳解决方案最多可以在 O(q) 时间内找到 p/q，方法是隐式遍历Stern-Brocot 树，这是一种在所有有理数上的二叉搜索树。但是，我希望运行时更接近整数情况下的运行时，可能类似于 O(lg (p + q)) 或 O(lg pq)。有谁知道获得这种运行时的方法？

我最初考虑使用区间 [0, 1] 的标准二进制搜索，但这只会找到具有非重复二进制表示的有理数，它几乎遗漏了所有有理数。我还考虑过使用其他一些方法来枚举有理数，但我似乎无法找到一种方法来搜索这个空间，只需要更大/相等/更少的比较。

我需要在我的 Verilog 代码中使用有理数。我寻找任何资源，但我找不到有关此问题的任何信息。如何在 Verilog 中定义有理数。

我还没有听说过，大多数语言似乎只是整数除法或浮点数。是否发现它是方案中的问题，因此未在其他语言中使用？

我必须编写一个程序来找到具有属性的有理数。我编写了代码来检查属性，但现在我不知道如何检查所有有理数。我试过了

但它永远不会结束！它错过了太多。所以我尝试了这个

但这仅在某些时候有效。我该如何解决这个问题？

我的任务是发展一个理性的班级。如果 500 和 1000 是我的输入，那么 (½) 必须是我的输出。我自己编写了一个程序来找到它。

是否有另一种找到解决方案的最佳方法，或者我的程序已经是最好的？

我一直在参加一个编程竞赛，其中一个问题是输入数据包括十进制格式的小数：0.75就是一个例子。

将其解析Double为微不足道的（我可以使用read它），但是精度的损失是痛苦的。比较时需要非常小心Double（我不是），这似乎是多余的，因为Rational在 Haskell 中有数据类型。

在尝试使用它时，我发现必须read提供Rational以下格式的字符串：numerator % denominator，显然我没有。

所以，问题是：

将分数的十进制表示解析为 的最简单方法是什么Rational？

外部依赖的数量也应该考虑在内，因为我无法在在线判断中安装额外的库。

在Haskell 98 报告中说

浮动文字必须包含小数点前后的数字；这确保了小数点不会被误认为是点字符的另一种用法。

这可能还有什么用处？我无法想象任何这样的法律表达。

（澄清动机：我知道很多人不需要9.0写数字或0.7一直写数字，但我不能很好地与自己交朋友。我同意而不是更紧凑，但没有更好，但是写出来的尾随零对我来说是错误的，除非它们表达的某个数量精确到十分之一，这在 Haskell 让我写 - 数字的情况下很少见。） 0.7.79.0

没有表达式要求整数文字直接位于 a 旁边.，没有空格？

我将实现一个 Farey 分数近似，用于将有限精度的用户输入转换为可能重复的有理数。
http://mathworld.wolfram.com/FareySequence.html

我可以很容易地找到序列中最接近的 Farey 分数，并且我可以通过构建 Stern-Brocot 树递归地搜索中位数分数来找到 Fn。
http://mathworld.wolfram.com/Stern-BrocotTree.html

但是，我想出的在序列 Fn 中查找分数的方法似乎效率很低：（
伪）

我几乎总是定义序列 Fn 其中 n = 10^m 其中 m >1

所以也许最好一次构建序列并缓存它......但似乎仍然应该有一种更好的方法来派生它。

编辑：
本文有一个有前途的算法： http:
//www.math.harvard.edu/~corina/publications/farey.pdf

我将尝试实施。
问题是他们的“最有效”算法需要知道前两个元素。我知道任何序列的第一个元素是 1/n 但找到第二个元素似乎是一个挑战......

EDIT2：
我不确定我是如何忽略这一点的：
给定 F0 = 1/n
If x > 2 then
F1 = 1/(n-1)

因此，对于所有 n > 2，前两个分数将始终为
1/n、1/(n-1)，我可以实现来自 Patrascu 的解决方案。

所以现在，我们对这个问题的答案应该证明这个解决方案是或不是使用基准测试的最佳解决方案。

你知道如何在 C 中对十进制数进行有理逼近（类似于鼠Matlab 函数）吗？

更新

如果我们想要一个双数number的 P/Q 近似值，快速解决方法可能是：

误差小于（数量/因子），可以忽略不计。

给定一个浮点数，我希望得到一个String近似小数的有理数的表示（在给定的容差 ε 内很好）。我目前的做法如下：

如果您不熟悉它，ApintMath.pow甚至可以使用任意长的数字，这很好，因为我正在尝试转换具有数千个小数位的小数。我的算法的性能很糟糕。

我将此归因于两件事，但可能还有更多：

1. 我获得分数的方法非常幼稚。我确信有更好的方法。
2. 该分数是未简化的，因此使用该分数的任何后续计算都可能会浪费大量时间。

你会怎么做？还有其他我没有谈到的领域让我慢下来吗？