我将实现一个 Farey 分数近似，用于将有限精度的用户输入转换为可能重复的有理数。
http://mathworld.wolfram.com/FareySequence.html
我可以很容易地找到序列中最接近的 Farey 分数，并且我可以通过构建 Stern-Brocot 树递归地搜索中位数分数来找到 Fn。
http://mathworld.wolfram.com/Stern-BrocotTree.html
但是，我想出的在序列 Fn 中查找分数的方法似乎效率很低：（
伪）
For int i = 0 to fractions.count -2
{
if fractions[i].denominator + fractions[i+1].denominator < n
{
insert new fraction(
numerator = fractions[i].numerator + fractions[i+1].numerator
,denominator = fractions[i].denominator + fractions[i+1].denominator)
//note that fraction will reduce itself
addedAnElement = true
}
}
if addedAnElement
repeat
我几乎总是定义序列 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 的解决方案。
所以现在，我们对这个问题的答案应该证明这个解决方案是或不是使用基准测试的最佳解决方案。