6

任意の小数を正確な分数 (323527/4362363 のようなもの) に変換するのではなく、1/2、1/4、1/8 などの一般的な (人間が読みやすいという点で) 簡単に識別できる量に変換しようとしています。等

一連のif-then、以下/等しいなどの比較を使用する以外に、これを行うためのより最適化された手法はありますか?

編集: 私の特定のケースでは、概算は許容されます。アイデアは、0.251243 ~ 0.25 = 1/4 です - 私の使用例では、それは「十分」であり、後者は迅速な指標 (計算には使用されず、表示数値としてのみ使用されます) の観点から、人間の可読性にとってより好ましいです。

4

5 に答える 5

7

「連分数近似」を調べてください。ウィキペディアの「連分数」の記事に基本的な紹介がありますが、分数を生成しながら近似値を生成する最適化されたアルゴリズムがあります。

次に、「十分に近い」場合に備えて、分母のサイズと近似の近さの組み合わせである停止ヒューリスティックを選択します。

于 2011-01-13T03:32:16.113 に答える
3

ユークリッドの互除法を使用して、列挙子と分母の間の最大公約数を取得し、それで除算することができます。

于 2011-01-13T03:25:49.883 に答える
0

以下では、小数が0から1の間にあると仮定します。これをより大きな数と負の数に適応させるのは簡単なはずです。

おそらく最も簡単な方法は、許容できる最大の分母を選択し、その分母が0から1までの分数以下の分数のリストを作成することです。簡略化できる分数は避けてください。明らかに、1/2をリストしたら、2/4は必要ありません。分子と分母のGCDがユークリッドのアルゴリズムを使用して1であることを確認することにより、単純化できる分数を回避できます。リストができたら。これらを浮動小数点数として評価します（おそらく2倍になりますが、データ型は明らかにプログラミング言語の選択によって異なります）。次に、元の分数と分数の浮動小数点評価の両方を格納する平衡二分探索ツリーにそれらを挿入します。

次に、番号を取得するたびに、ツリーを検索して、検索ツリーにあるそれに最も近い番号を見つけます。探しているノードがリーフノードではない可能性があるため、これは完全一致を検索するよりも少し複雑であることに注意してください。したがって、ツリーをトラバースするときに、アクセスした最も近い値のノードの記録を保持します。リーフノードに到達し、それをアクセスした最も近い値のノードと比較すると、完了です。あなたの最も近いものがどちらであっても、それはあなたの答えです。

于 2011-01-13T03:34:58.270 に答える
0

一部を「プレビュー」するためだけに、かなりばかげたソリューション：

係数 = 1/10 進数
結果 = 1/ラウンド (係数)
マルチ = 1

while (結果 = 1) {
  マルチ = マルチ * 10
  結果 = (1 * マルチ)/(ラウンド (マルチ * ファクター))
}

結果 = simple_with_GCD(結果)

幸運を！

于 2011-01-14T12:34:44.753 に答える
0

ここに提案があります：開始分数がp / qであると仮定します

  1. r = p/q を有理 (浮動小数点) 値として計算します (例: r = float(p)/float(q))

  2. 丸め小数を計算します x = int(10000*r)

  3. x と 10000 の GCD (最大公約数) を計算: s = GCD(x, 10000)

  4. 結果を m / n として表します。ここで、m = x/s および n = y/s (この例では 371 / 5000 に計算されます)

通常、1000 のすべての分母はかなり人間が読めるものです。

値が 1/3 などの単純なケースに近い場合、これは最良の結果を提供しない可能性があります。ただし、個人的には、379/1000 は 47/62 (最も短い分数表現) よりもはるかに読みやすいと思います。ただし、そのようなプロセスを微調整するためにいくつかの例外を追加できます（たとえば、 p/GCD(p,q) 、 q/GCD(p,q) を計算し、これらのいずれかが1桁の値である場合はそれを受け入れてから、このメソッドに進みます）

于 2011-01-13T04:21:06.153 に答える