0

限られた精度のユーザー入力をおそらく反復する有理数に変換するために、Farey 分数近似を実装します。
http://mathworld.wolfram.com/FareySequence.html

シーケンス内で最も近いファレー分数を簡単に見つけることができ、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

ほとんどの場合、n = 10^m で m >1 のシーケンス Fn を定義します。

したがって、おそらくシーケンスを一度構築してキャッシュするのが最善かもしれません...しかし、それを導出するためのより良い方法があるはずです。

編集:
この論文には有望なアルゴリズムがあります:
http://www.math.harvard.edu/~corina/publications/farey.pdf

実装してみます。
問題は、彼らの「最も効率的な」アルゴリズムは、前の 2 つの要素を知る必要があることです。どのシーケンスの要素 1 も 1/n であることは知っていますが、2 番目の要素を見つけるのは難しいようです...

EDIT2:
どのようにこれを見落としたのかわかりません:
F0 = 1/nの
場合 x > 2 の場合
F1 = 1/(n-1)

したがって、すべての n > 2 について、最初の 2 つの分数は常に
1/n, 1/(n-1) になり、Patrascu のソリューションを実装できます。

したがって、この質問に対する答えは、ベンチマークを使用して、このソリューションが最適であるかどうかを証明する必要があります..

4

2 に答える 2

1

そもそも、Farey シリーズが必要な理由は何ですか? 連分数を使用すると、系列を事前に計算しなくてもオンラインで同じ近似値が得られます。

于 2011-11-13T12:00:54.187 に答える
0

ファレイ列の隣接分数については、セクション 2 で説明します。ファリー部分列の隣接分数の 3、http://arxiv.org/abs/0801.1981。

于 2011-11-07T11:38:11.063 に答える