如何将小数点简化为最小可能的分数？ [英] How to simplify a decimal into the smallest possible fraction?

问题描述

例如，如果我的函数被称为 getlowestfraction（），这就是我所期望的：

  getlowestfraction（0.5）//沿着
  

的行返回1或2

另外一个例子：

  getlowestfraction（0.125）//返回1,8或类似的东西那
  

解决方案

使用 Continued Fractions 可以有效地创建一个（有限的或无限的）分数序列 h _{/ k n 如果 x 是 x ，那么它就是任意好的近似值。一个有理数，这个过程在某一时刻停止于 h n / k n == x 。如果 x 不是有理数，则序列 h n / k n ，n = 0,1,2 ... 。} 非常快速地收敛到 x 。连续分数算法只产生缩减分数（提名者和分母都是质数），并且分数是
，这对某个给定的实数是最合理的近似值。

我不是一个JavaScript人（通常用C语言编程） ，但我试图用下面的JavaScript函数实现算法。请原谅我是否有愚蠢的错误。但是我已经检查过该函数，它似乎正常工作。

pre $函数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;
}

当有理逼近确切或给定精度<$时，循环停止c $ c> eps = 1.0E-15 。当然，您可以根据需要调整精度。 （，同时条件是从连续分数的理论中推导出来的。）



示例（迭代次数



  getlowestfraction（0.5）= 1/2（1次迭代）
 getlowestfraction（0.125） = 1/8（1次迭代）
 getlowestfraction（0.1 + 0.2）= 3/10（2次迭代）
 getlowestfraction（1.0 / 3.0）= 1/3（1次迭代）
 getlowestfraction Math.PI）= 80143857/25510582（12次迭代）
  

请注意，该算法给出 1/3 作为 x = 1.0 / 3.0 的近似值。通过乘以10的幂和消除公因式重复乘以 x 会得到类似于 3333333333/10000000000 的内容。

$ b

以下是不同精度的示例：

• 使用 eps = 1.0E-15 您得到 getlowestfraction（0.142857）= 142857/1000000 。
eps = 1.0E-6 您得到 getlowestfraction（0.142857）= 1/7 。 ul>


For example, if my function was called getlowestfraction(), this is what I expect it to do:

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

Another example:

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

解决方案

Using Continued Fractions one can efficiently create a (finite or infinite) sequence of fractions h_n/k_n that are arbitrary good approximations to a given real number x.

If x is a rational number, the process stops at some point with h_n/k_n == x. If x is not a rational number, the sequence h_n/k_n, n = 0, 1, 2, ... converges to x very quickly.

The continued fraction algorithm produces only reduced fractions (nominator and denominator are relatively prime), and the fractions are in some sense the "best rational approximations" to a given real number.

I am not a JavaScript person (programming in C normally), but I have tried to implement the algorithm with the following JavaScript function. Please forgive me if there are stupid errors. But I have checked the function and it seems to work correctly.

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;
}

The loop stops when the rational approximation is exact or has the given precision eps = 1.0E-15. Of course, you can adjust the precision to your needs. (The while condition is derived from the theory of continued fractions.)

Examples (with the number of iterations of the while-loop):

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)

Note that this algorithm gives 1/3 as approximation for x = 1.0/3.0. Repeated multiplication of x by powers of 10 and canceling common factors would give something like 3333333333/10000000000.

Here is an example of different precisions:

• With eps = 1.0E-15 you get getlowestfraction(0.142857) = 142857/1000000.
• With eps = 1.0E-6 you get getlowestfraction(0.142857) = 1/7.

这篇关于如何将小数点简化为最小可能的分数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！