5

次の問題に適したアルゴリズムは何ですか？

厳密に0と1の間の有理数a / bが与えられた場合、 |を最小化する自然なnを見つけます。a / b --1 / n |。

私が考えることができる最も単純なアルゴリズムは、 m = b、b -1、…についてa/bと1/mを比較し、a/b≤1/ mで停止してから、 |を比較することです。a / b -1 / m | および| a / b -1 / （m + 1） |。それはO（b）です。もっと上手くできますか？

4

3 に答える 3

7

k = floor(b/a) とすると、n は k または k+1 のいずれかに等しくなければなりません。2 つの候補を試して、どちらが勝つか見てみましょう。これは O(1) です。

これが真であることは、1/(k+1) <= a/b <= 1/k という事実から導かれ、これは不等式 k <= b/a <= k+1 から導かれます。

于 2011-08-21T18:39:41.803 に答える
1

連分数を使用することで、O(1) でこれを実行できると思います。(0, 1] の範囲の任意の有理数は、次の形式で記述できます。

1 / (a0 + 1 / (a1 + 1 / (a2 + 1 / (... an))))

さらに、この表現にはいくつかの注目すべき特性があります。手始めに、任意の時点で表現を切り捨てると、有理数の非常に優れた近似値が得られます。特に、この表現を単に切り捨てると、

1 / a0

その場合、分数 a/b は 1/a0 と 1/(a0+1) の間になります。したがって、a0 の値を取得できれば、上記の 2 つの数値を調べてどちらが近いかを確認できます。

2 番目の重要な特性は、a0 の値を取得する優れた方法があることです。これは、b/a の商によって与えられます。つまり、次のように最も近い分数を見つけることができます。

  1. 整数除算を使用して x = b / a を計算します。
  2. 1/x または 1/(x+1) が a/b に近いかどうかを調べ、その結果を出力します。

a と b が機械語に収まる場合、これは O(1) 時間で実行されます。

于 2011-08-21T18:41:34.057 に答える
0

コメントで示唆されているように、最善の策は Ceiling 関数と Floor 関数を使用することです。

あなたの合理性a / bが次のように与えられている場合0 <= x <= 1、あなたは簡単にこれを行うことができます：

int Rationalize(double x)
{
    int n1 = floor(1 / x);
    int n2 = ceiling(1 / x);

    double e1 = abs(x - 1.0 / n1);
    double e2 = abs(x - 1.0 / n2);

    if (e1 < e2) return n1;
    else return n2;
}

（abs、floor、およびceilingが事前に定義されていると想定されている場合）

于 2011-08-21T18:41:34.250 に答える