3

たとえば、私の関数が呼び出された場合getlowestfraction()、これは私が期待することです:

getlowestfraction(0.5) // returns 1, 2 or something along the lines of that

もう一つの例：

getlowestfraction(0.125) // returns 1, 8 or something along the lines of that
4

6 に答える 6

13

連分数を使用すると、与えられた実数xの任意の適切な近似である分数h n /k nの (有限または無限) シーケンスを効率的に作成できます。

xが有理数の場合、プロセスはh n /k n == xのある時点で停止します。xが有理数でない場合、数列h n /k n , n = 0, 1, 2, ... は非常に迅速にxに収束します。

連分数アルゴリズムは簡約された分数 (分子と分母が互いに素) のみを生成し、分数はある意味で、与えられた実数の "最良の有理近似" です。

私は JavaScript の人ではありません (通常は C でプログラミングします) が、次の JavaScript 関数でアルゴリズムを実装しようとしました。愚かなエラーがある場合は、ご容赦ください。しかし、機能を確認したところ、正しく動作しているようです。

function getlowestfraction(x0) {
    var eps = 1.0E-15;
    var h, h1, h2, k, k1, k2, a, x;

    x = x0;
    a = Math.floor(x);
    h1 = 1;
    k1 = 0;
    h = a;
    k = 1;

    while (x-a > eps*k*k) {
        x = 1/(x-a);
        a = Math.floor(x);
        h2 = h1; h1 = h;
        k2 = k1; k1 = k;
        h = h2 + a*h1;
        k = k2 + a*k1;
    }

    return h + "/" + k;
}

有理近似が正確であるか、指定された精度を持っている場合、ループは停止しますeps = 1.0E-15。もちろん、必要に応じて精度を調整できます。(このwhile条件は、連分数の理論から導き出されます。)

例 (while ループの反復回数):

getlowestfraction(0.5)     = 1/2               (1 iteration)
getlowestfraction(0.125)   = 1/8               (1 iteration)
getlowestfraction(0.1+0.2) = 3/10              (2 iterations)
getlowestfraction(1.0/3.0) = 1/3               (1 iteration)
getlowestfraction(Math.PI) = 80143857/25510582 (12 iterations)

このアルゴリズムは1/3の近似として与えることに注意してくださいx = 1.0/3.0。を 10のべき乗で繰り返し乗算し、公約x数をキャンセルすると、 のような結果が得られます3333333333/10000000000。

さまざまな精度の例を次に示します。

  • eps = 1.0E-15あなたと一緒に取得しますgetlowestfraction(0.142857) = 142857/1000000。
  • eps = 1.0E-6あなたと一緒に取得しますgetlowestfraction(0.142857) = 1/7。
于 2012-12-23T13:23:10.350 に答える
1

代わりにこのプログラムを試してください：

function toFrac(number) {
    var fractional = number % 1;

    if (fractional) {
        var real = number - fractional;
        var exponent = String(fractional).length - 2;
        var denominator = Math.pow(10, exponent);
        var mantissa = fractional * denominator;
        var numerator = real * denominator + mantissa;
        var gcd = GCD(numerator, denominator);
        denominator /= gcd;
        numerator /= gcd;
        return [numerator, denominator];
    } else return [number, 1];
}

function gcd(numerator, denominator) {
    do {
        var modulus = numerator % denominator;
        numerator = denominator;
        denominator = modulus;
    } while (modulus);

    return numerator;
}

次に、次のように使用できます。

var start = new Date;
var PI = toFrac(Math.PI);
var end = new Date;

alert(PI);
alert(PI[0] / PI[1]);
alert(end - start + " ms");

ここでデモを見ることができます：http：//jsfiddle.net/MZaK9/1/

于 2012-12-22T11:40:18.817 に答える
1

分子と分母の整数値が得られるまで 10 を掛け続け、この質問の答えを使用して分数を最も単純な項に減らすことができます。

于 2012-12-22T11:01:11.123 に答える
0

数字はx = 0 . ( a_1 a_2 ... a_k ) ( a_1 a_2 ... a_k ) ....簡単にするためのものだとします (最初の数桁は繰り返しパターンに適合しない可能性があり、何が何であるかを把握する方法が必要であることを覚えておいてkください)。bがベースなら、

b ^ k * x - x = ( b ^ k - 1 ) * x

一方で、しかし

b ^ k * x - x = ( a_1 a_2 ... a_k )

（正確、つまりこれは整数です）一方。

そう

x = ( a_1 ... a_k ) / ( b ^ k - 1 )

これで、ユークリッドのアルゴリズムを使用して gcd を取得し、それを除算して簡約分数を取得できます。

繰り返しシーケンスを決定する方法を理解する必要があります。その問いには答えがあるはずです。\1編集 - 1 つの答え:パターンに一致する場合の長さです/([0-9]+)\1+$/(丸めの bc に一致する前に最後の桁を破棄することをお勧めします)。一致するものがない場合、「単純な」表現 (x*base^precision/base^precision) より優れた「答え」はありません。

NBこの回答は、回答に期待するものについていくつかの仮定を立てており、ニーズに合わない可能性があります。しかし、それは繰り返し小数表現から分数を再現する「教科書」の方法です-例えばここを参照してください

于 2012-12-23T07:37:37.557 に答える