0

我将实现一个 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 的解决方案。

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

4

2 回答 2

1

为什么你需要 Farey 系列？使用连分数可以在线为您提供相同的近似值，而无需预先计算级数。

于 2011-11-13T12:00:54.187 回答
0

Farey 序列中的相邻分数在第 2 节中描述。Farey 子序列中的相邻分数 3，http: //arxiv.org/abs/0801.1981 。

于 2011-11-07T11:38:11.063 回答