3

O（N）の下でこの問題を解決するためのアルゴリズムを探しています。

2つの実数aとbが与えられた場合（一般性を失うことなく、両方とも0と1の間であると見なすことができます）式を最小化する-NとNの間の整数nを見つけます。

| an --b --round（an --b）|

ユークリッドの互除法はこれにはうまくいくかもしれないと私たちは考えましたが、それを理解することはできません。整数nを徹底的に検索するよりも、これを行うにははるかに高速な方法があるはずです。

注：この状況では、aとbが頻繁に変更される可能性があるため、ルックアップテーブルのaとbを修正することは可能ですが、Nも変更される可能性があるため、少し見苦しくなります。ルックアップテーブルをまだ詳細に調べていないので、Nの関数としてルックアップテーブルをどれだけ小さくできるかを確認します。

4

4 に答える 4

1

比率a/bの連分数を計算できます。分母が、より大きい場合N、または近似が十分に良い場合は、停止できます。

// Initialize:
double ratio = a / b;
int ak = (int)(ratio);
double remainder = ratio - ak;

int n0 = 1;
int d0 = 0;

int n1 = ak;
int d1 = 1;

do {
    ratio = 1 / remainder;
    ak = (int)ratio;
    int n2 = ak * n1 + n0;
    int d2 = ak * d1 + d0;
    n0 = n1;
    d0 = d1;
    n1 = n2;
    d1 = d2;
    remainder = ratio - ak;
} while (d1 < N);

nあなたが探している値はですd0（またはd1それがまだ小さい場合N）。

これは必ずしも最小の解を与えるわけではありませんが、非常に良い近似になる可能性があります。

于 2012-01-25T23:47:08.127 に答える
1

aN - b式を整数にできるだけ近づける整数Nを効果的に検索しています。修正されaていますか？bはいの場合、ルックアップテーブルを事前に計算して、O（1）を使用できます:-)

そうでない場合は、すべての整数aNに近いNを探すことを検討してください。I + bI

于 2012-01-25T22:43:27.647 に答える
1

連分数のようなものを探しているようです...

それらはどのように関連していますか？bを有理数b1/b2に置き換えることができると仮定します。ここで、an-b1/b2が約mになるような整数nとmを探しています。言い換えると、（m +（b1 / b2））/ n =（mb2 + b1）/ nb1、有理数がおよそaになるようなnとmを探しています。a1 = mb2+b1およびa2=nb1に設定します。連分数近似からa1とa2の値を見つけ、nとmを解きます。

別のアプローチはこれである可能性があります：

  1. aとbの適切な合理的近似を見つけます：a〜a1 / a2およびb〜b1/b2。
  2. nとmについてn（a1 / a2）-（b1 / b2）=mを解きます。

しかし、それがうまくいくかどうかはわかりません。aに必要な精度は、nとbによって異なります。

于 2012-01-25T23:07:51.170 に答える
0

まず、b=0かつ0<a<1である、より単純なケースを考えてみましょう。F（a、n）= | an-round（an）|

step_size=1とします

Step 1. Let v=a
Step 2. Let period size p = upper_round( 1/v ).
Step 3. Now, for n=1..p, there must be a number i such that F(v,i) < v.
Step 4. v = F(v,i), step_size = stepsize * i
Step 5. Go to step 2

ご覧のとおり、F（v、*）を任意のレベルに減らすことができます。最終的な解n=step_size。

于 2012-01-25T23:10:21.890 に答える