Как преобразовать поплавки в читаемые человеком фракции?

Question

Допустим, у нас есть 0.33, нам нужно вывести «1/3».
Если у нас есть «0,4», нам нужно вывести «2/5».

Идея состоит в том, чтобы сделать его читаемым человеком, чтобы пользователь понимал "x частей из y" как лучший способ понимания данных.

Я знаю, что проценты - хорошая замена, но мне было интересно, есть ли простой способ сделать это?

Answer 1

Я обнаружил, что Дэвида Эппштейна находит рациональное приближение к заданному действительному коду C именно тем, о чем вы просите. Он основан на теории непрерывных дробей и очень быстрый и довольно компактный.

Я использовал версии этой программы для определенных пределов числителя и знаменателя.

/*
** find rational approximation to given real number
** David Eppstein / UC Irvine / 8 Aug 1993
**
** With corrections from Arno Formella, May 2008
**
** usage: a.out r d
**   r is real number to approx
**   d is the maximum denominator allowed
**
** based on the theory of continued fractions
** if x = a1 + 1/(a2 + 1/(a3 + 1/(a4 + ...)))
** then best approximation is found by truncating this series
** (with some adjustments in the last term).
**
** Note the fraction can be recovered as the first column of the matrix
**  ( a1 1 ) ( a2 1 ) ( a3 1 ) ...
**  ( 1  0 ) ( 1  0 ) ( 1  0 )
** Instead of keeping the sequence of continued fraction terms,
** we just keep the last partial product of these matrices.
*/

#include <stdio.h>

main(ac, av)
int ac;
char ** av;
{
    double atof();
    int atoi();
    void exit();

    long m[2][2];
    double x, startx;
    long maxden;
    long ai;

    /* read command line arguments */
    if (ac != 3) {
        fprintf(stderr, "usage: %s r d\n",av[0]);  // AF: argument missing
        exit(1);
    }
    startx = x = atof(av[1]);
    maxden = atoi(av[2]);

    /* initialize matrix */
    m[0][0] = m[1][1] = 1;
    m[0][1] = m[1][0] = 0;

    /* loop finding terms until denom gets too big */
    while (m[1][0] *  ( ai = (long)x ) + m[1][1] <= maxden) {
        long t;
        t = m[0][0] * ai + m[0][1];
        m[0][1] = m[0][0];
        m[0][0] = t;
        t = m[1][0] * ai + m[1][1];
        m[1][1] = m[1][0];
        m[1][0] = t;
        if(x==(double)ai) break;     // AF: division by zero
        x = 1/(x - (double) ai);
        if(x>(double)0x7FFFFFFF) break;  // AF: representation failure
    } 

    /* now remaining x is between 0 and 1/ai */
    /* approx as either 0 or 1/m where m is max that will fit in maxden */
    /* first try zero */
    printf("%ld/%ld, error = %e\n", m[0][0], m[1][0],
           startx - ((double) m[0][0] / (double) m[1][0]));

    /* now try other possibility */
    ai = (maxden - m[1][1]) / m[1][0];
    m[0][0] = m[0][0] * ai + m[0][1];
    m[1][0] = m[1][0] * ai + m[1][1];
    printf("%ld/%ld, error = %e\n", m[0][0], m[1][0],
           startx - ((double) m[0][0] / (double) m[1][0]));
}

Answer 2

Начиная с версии Python 2.6 имеется модуль fractions.

(Цитата из документации.)

>>> from fractions import Fraction
>>> Fraction('3.1415926535897932').limit_denominator(1000)
Fraction(355, 113)

>>> from math import pi, cos
>>> Fraction.from_float(cos(pi/3))
Fraction(4503599627370497, 9007199254740992)
>>> Fraction.from_float(cos(pi/3)).limit_denominator()
Fraction(1, 2)

Answer 3

Если выходные данные предназначены для быстрого ознакомления читателя с порядком результата, нет смысла возвращать что-то вроде «113/211», поэтому выходные данные должны ограничиваться использованием однозначных чисел (и возможно 1/10 и 9/10). Если это так, вы можете заметить, что есть только 27 различных дробей.

Поскольку основная математика для генерации выходных данных никогда не изменится, решение может заключаться в том, чтобы просто жестко закодировать двоичное дерево поиска, чтобы функция выполняла не более log (27) ~ = 4 3/4 сравнений. Вот проверенная C версия кода

char *userTextForDouble(double d, char *rval)
{
    if (d == 0.0)
        return "0";

    // TODO: negative numbers:if (d < 0.0)...
    if (d >= 1.0)
        sprintf(rval, "%.0f ", floor(d));
    d = d-floor(d); // now only the fractional part is left

    if (d == 0.0)
        return rval;

    if( d < 0.47 )
    {
        if( d < 0.25 )
        {
            if( d < 0.16 )
            {
                if( d < 0.12 ) // Note: fixed from .13
                {
                    if( d < 0.11 )
                        strcat(rval, "1/10"); // .1
                    else
                        strcat(rval, "1/9"); // .1111....
                }
                else // d >= .12
                {
                    if( d < 0.14 )
                        strcat(rval, "1/8"); // .125
                    else
                        strcat(rval, "1/7"); // .1428...
                }
            }
            else // d >= .16
            {
                if( d < 0.19 )
                {
                    strcat(rval, "1/6"); // .1666...
                }
                else // d > .19
                {
                    if( d < 0.22 )
                        strcat(rval, "1/5"); // .2
                    else
                        strcat(rval, "2/9"); // .2222...
                }
            }
        }
        else // d >= .25
        {
            if( d < 0.37 ) // Note: fixed from .38
            {
                if( d < 0.28 ) // Note: fixed from .29
                {
                    strcat(rval, "1/4"); // .25
                }
                else // d >=.28
                {
                    if( d < 0.31 )
                        strcat(rval, "2/7"); // .2857...
                    else
                        strcat(rval, "1/3"); // .3333...
                }
            }
            else // d >= .37
            {
                if( d < 0.42 ) // Note: fixed from .43
                {
                    if( d < 0.40 )
                        strcat(rval, "3/8"); // .375
                    else
                        strcat(rval, "2/5"); // .4
                }
                else // d >= .42
                {
                    if( d < 0.44 )
                        strcat(rval, "3/7"); // .4285...
                    else
                        strcat(rval, "4/9"); // .4444...
                }
            }
        }
    }
    else
    {
        if( d < 0.71 )
        {
            if( d < 0.60 )
            {
                if( d < 0.55 ) // Note: fixed from .56
                {
                    strcat(rval, "1/2"); // .5
                }
                else // d >= .55
                {
                    if( d < 0.57 )
                        strcat(rval, "5/9"); // .5555...
                    else
                        strcat(rval, "4/7"); // .5714
                }
            }
            else // d >= .6
            {
                if( d < 0.62 ) // Note: Fixed from .63
                {
                    strcat(rval, "3/5"); // .6
                }
                else // d >= .62
                {
                    if( d < 0.66 )
                        strcat(rval, "5/8"); // .625
                    else
                        strcat(rval, "2/3"); // .6666...
                }
            }
        }
        else
        {
            if( d < 0.80 )
            {
                if( d < 0.74 )
                {
                    strcat(rval, "5/7"); // .7142...
                }
                else // d >= .74
                {
                    if(d < 0.77 ) // Note: fixed from .78
                        strcat(rval, "3/4"); // .75
                    else
                        strcat(rval, "7/9"); // .7777...
                }
            }
            else // d >= .8
            {
                if( d < 0.85 ) // Note: fixed from .86
                {
                    if( d < 0.83 )
                        strcat(rval, "4/5"); // .8
                    else
                        strcat(rval, "5/6"); // .8333...
                }
                else // d >= .85
                {
                    if( d < 0.87 ) // Note: fixed from .88
                    {
                        strcat(rval, "6/7"); // .8571
                    }
                    else // d >= .87
                    {
                        if( d < 0.88 ) // Note: fixed from .89
                        {
                            strcat(rval, "7/8"); // .875
                        }
                        else // d >= .88
                        {
                            if( d < 0.90 )
                                strcat(rval, "8/9"); // .8888...
                            else
                                strcat(rval, "9/10"); // .9
                        }
                    }
                }
            }
        }
    }

    return rval;
}

Answer 4

Вот ссылка, объясняющая математику преобразования десятичной дроби в дробную:

http://www.webmath.com/dec2fract.html

А вот пример функции для того, как на самом деле сделать это с помощью VB (от www.freevbcode.com/ShowCode.asp?ID=582):

Public Function Dec2Frac(ByVal f As Double) As String

   Dim df As Double
   Dim lUpperPart As Long
   Dim lLowerPart As Long

   lUpperPart = 1
   lLowerPart = 1

   df = lUpperPart / lLowerPart
   While (df <> f)
      If (df < f) Then
         lUpperPart = lUpperPart + 1
      Else
         lLowerPart = lLowerPart + 1
         lUpperPart = f * lLowerPart
      End If
      df = lUpperPart / lLowerPart
   Wend
Dec2Frac = CStr(lUpperPart) & "/" & CStr(lLowerPart)
End Function

(из поиска Google: преобразовать десятичную дробь в код, преобразовать десятичную дробь в код дроби)

Answer 5

Вот версии Perl и Javascript кода VB, предложенного devinmoore:

Perl:

sub dec2frac {
    my $d = shift;

    my $df  = 1;
    my $top = 1;
    my $bot = 1;

    while ($df != $d) {
      if ($df < $d) {
        $top += 1;
      }
      else {
         $bot += 1;
         $top = int($d * $bot);
      }
      $df = $top / $bot;
   }
   return "$top/$bot";
}

И почти идентичный JavaScript:

function dec2frac(d) {

    var df = 1;
    var top = 1;
    var bot = 1;

    while (df != d) {
        if (df < d) {
            top += 1;
        }
        else {
            bot += 1;
            top = parseInt(d * bot);
        }
        df = top / bot;
    }
    return top + '/' + bot;
}

Answer 6

A C # реализация

/// <summary>
/// Represents a rational number
/// </summary>
public struct Fraction
{
    public int Numerator;
    public int Denominator;

    /// <summary>
    /// Constructor
    /// </summary>
    public Fraction(int numerator, int denominator)
    {
        this.Numerator = numerator;
        this.Denominator = denominator;
    }

    /// <summary>
    /// Approximates a fraction from the provided double
    /// </summary>
    public static Fraction Parse(double d)
    {
        return ApproximateFraction(d);
    }

    /// <summary>
    /// Returns this fraction expressed as a double, rounded to the specified number of decimal places.
    /// Returns double.NaN if denominator is zero
    /// </summary>
    public double ToDouble(int decimalPlaces)
    {
        if (this.Denominator == 0)
            return double.NaN;

        return System.Math.Round(
            Numerator / (double)Denominator,
            decimalPlaces
        );
    }


    /// <summary>
    /// Approximates the provided value to a fraction.
    /// /39272/kak-preobrazovat-poplavki-v-chitaemye-chelovekom-fraktsii
    /// </summary>
    private static Fraction ApproximateFraction(double value)
    {
        const double EPSILON = .000001d;

        int n = 1;  // numerator
        int d = 1;  // denominator
        double fraction = n / d;

        while (System.Math.Abs(fraction - value) > EPSILON)
        {
            if (fraction < value)
            {
                n++;
            }
            else
            {
                d++;
                n = (int)System.Math.Round(value * d);
            }

            fraction = n / (double)d;
        }

        return new Fraction(n, d);
    }
}

Answer 7

Возможно, вы захотите прочитать Что должен знать каждый учёный об арифметике с плавающей запятой .

Вам нужно будет указать некоторую точность путем умножения на большое число:

3.141592 * 1000000 = 3141592

тогда вы можете сделать дробь:

3 + (141592 / 1000000)

и уменьшить через GCD ...

3 + (17699 / 125000)

но нет способа вывести предназначенную дробь. Возможно, вы захотите всегда вместо этого использовать дроби по всему коду - просто не забывайте сокращать дроби, когда вы можете избежать переполнения!

Answer 8

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

.

Answer 9

Отчасти проблема в том, что так много дробей на самом деле не так просто интерпретировать как дроби. Например. 0,33 это не 1/3, это 33/100. Но если вы помните свое обучение в начальной школе, то происходит процесс преобразования десятичных значений в дробные, однако вряд ли вы получите то, что вам нужно, поскольку большую часть времени десятичные числа хранятся не в 0,33, а в 0,329999999999998 или чем-то подобном.

Сделайте себе одолжение и не беспокойтесь об этом, но если вам нужно, вы можете сделать следующее:

Умножайте исходное значение на 10, пока не удалите дробную часть. Сохраните это число и используйте его как делитель. Затем выполните серию упрощений в поисках общих знаменателей.

Так что 0,4 будет 4/10. Затем вы будете искать общие делители, начиная с низких значений, возможно, простых чисел. Начиная с 2, вы увидите, если 2 делит числитель и знаменатель равномерно, проверяя, совпадает ли пол деления с самим делением.

floor(5/2) = 2
5/2 = 2.5

Таким образом, 5 не делит 2 равномерно. Затем вы проверяете следующее число, скажем 3. Вы делаете это до тех пор, пока не достигнете квадратного корня меньшего числа или не превысите его.

После того, как вы это сделаете, вам нужно

Answer 10

Это не «алгоритм», а просто решение Python: http://docs.python.org/library/fractions.html

>>> from fractions import Fraction
>>> Fraction('3.1415926535897932').limit_denominator(1000)
Fraction(355, 113)