、我々はダブルス<em>の</em>のセットを持って、このようなものと仮定ダブルス

Question

の集合から全体数の10分の1内の各番号を取得するために、最小のスケールファクタを見つける：私たちは今、検索したい

1.11, 1.60, 5.30, 4.10, 4.05, 4.90, 4.89 

をxのいずれかの要素がsにxを乗じたものが整数の10分の1以内にある最小の正の整数スケール係数です。

ご迷惑をおかけして申し訳ございませんが、必要に応じてご確認ください。

Cスタイルの言語またはアルゴリズムの擬似コードへの回答を制限してください。

ありがとうございます！

Answer 1

あなたはと同時にディオファンチン近似と呼ばれるものを探しています。通常の声明では、実数a_1, ..., a_nと正の実数epsilonが与えられ、整数P_1, ..., P_nとQが見つかるように、|Q*a_j - P_j| < epsilon、可能であればQと小さくしてください。

これは、既知のアルゴリズムと非常によく研究問題です。しかし、あなたはqは仕様の別の部分であるQ < qと最高近似を見つけるために、NP困難であることを知っている必要があります。私が理解している限りでは、これはあなたの問題には関係ありません。なぜなら、固定されたepsilonを持っていて、最小のQが必要なのです。問題の

1つのアルゴリズムは、（Lenstra-Lenstra）-Lovászの格子縮小アルゴリズムです。私はあなたのための良い参照を見つけることができるかと思います。 These class notesには問題とアルゴリズムが記載されていますが、おそらく直接的なヘルプではありません。 Wikipediaには、実装上のかなり大きなリストを含むfairly detailed pageというアルゴリズムがあります。

Answer 2

Vladの修正された質問に答えるには（乗算後に正確な整数を求めたい場合）、その答えがわかります。あなたの数がであり、端数が減っている場合（aiとbiが互いに素である場合）、乗算する必要がある数値は、最小公倍数のb1, ..., bNです。

Answer 3

これは完全な答えではありませんが、いくつかの提案：

注：私はダブルスのスケールファクタのための「S」、および「x」を使用しています。

まず、無理な力が働かないかどうか尋ねてください。例えば。次に、s = 1、s = 2、s = 3などとなる。

x [i]のリストと許容値t = 1/10がある。各x [i]に対して、| s * x [i] -q [i] |となるような整数q [i]が存在するように、最小の正の整数sを見つけたいと思う。 <

まず、各x [i]に対して順序付きリストを作成できる場合は、それらをマージしてそれらのすべてで機能する最小のものを見つけるだけで十分です。第2に、答えはx [i]の小数部分のみに依存することに注意してください。

上記のテストを再整理すると、| x - q/s | < t/s。つまり、近似はt/sよりも良いはずであるという意味で、xに対して「良い」合理的な近似を見つけたいと考えています。数学者はこれの変種を研究しました。ここで、「良い」の基準は、より小さい「s」の値を持つものより優れていなければならず、これらを見つけるのに最も良い方法はcontinued fraction expansionの切捨てです。

残念ながら、これはあなたが必要とするものではありません。一度あなたの許容範囲に入ると、必ずしもますます良くなる必要はありません。同じ耐性が働きます。次の明白なことは、これを使って最初の数字にスキップし、そこから無理な力を加えることです。残念なことに、最初のsができる最大の数は5であるので、それはすべてあなたをそれほど購入しません。しかし、この方法では、動作するものが見つかるでしょう。最小のものではありません。存在する場合、これを使用してより小さいものを見つけることができますか？私は分かりませんが、ブルートフォースの上限を設定します。

また、各xの許容値を< tにする必要がある場合、これはすべてのxの製品の許容差が< t^nであることを意味します。これは、あなたが大いに前方にスキップし、暴力強制の合理的な下限を設定するかもしれません。