Как преобразовать числа с плавающей запятой в удобочитаемые дроби?

105

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

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

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

Swaroop CH
источник
В .33=> "1/3"пример касается меня; Я ожидал .33=> "33/100". Я полагаю, вы имели .33...в виду, конечно, но это выявляет проблему с вопросом - прежде чем мы сможем выбрать алгоритм, нам нужно определиться с ожидаемым поведением. В ответе Python @ Debilski используется .limit_denominator()максимальный знаменатель по умолчанию 10 ^ 7; вероятно, это хорошее значение по умолчанию на практике, но это все равно может привести к ошибкам, если вы не будете осторожны, и в случае возврата действительно вернется . "33/100".33
dimo414
С любыми доступными функциями для конкретного языка . Непонятно, о чем вы спрашиваете, если это действительно не противоречие.
Маркиз Лорн,

Ответы:

70

Я обнаружил, что рациональное приближение Дэвида Эппштейна к заданному реальному числовому коду 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]));
}
Эпсилон
источник
6
Тем из вас, кто ищет решение на Ruby, нам повезло! Кристофер Лорд реализовал вышеупомянутый алгоритм в геме Ruby. См. Christopher.lord.ac/fractions-in-ruby и rubygems.org/gems/fraction
shedd
6
Имейте в виду, что есть некоторые крайние случаи, которые этот код не обрабатывает очень хорошо: когда задано -1,3333333 с максимальным знаменателем 4, он возвращает 4 / -3 с ошибкой 3,333333e-08 и -5/4 с ошибкой = -8.333330e-02, что правильно. Но когда дано -1,33333337 с тем же максимальным знаменателем, получается 12121211 / -9090908 с ошибкой error = 4.218847e-15 и -4/3 с ошибкой -3.666667e-08, что неверно. Это проблема, в частности, при представлении алгоритма с вычисленными числами с плавающей запятой, такими как -4/3, что дает такие неверные результаты.
edsko 01
27

Начиная с 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)
Дебильски
источник
6
Примечания по реализации и алгоритму на hg.python.org/cpython/file/822c7c0d27d1/Lib/fractions.py#l211
piro
2
@Debilski, какой из OP language agnosticи algorithmтегов удовлетворяет ваш ответ?
vladr 06
2
@vladr Что ж, учитывая, что я написал этот ответ почти 6 лет назад (и более чем через год после того, как вопрос был задан), думаю, я больше не знаю, каковы были мои рассуждения тогда. Скорее всего, я имел в виду этот комментарий: stackoverflow.com/questions/95727/… OTOH Возможно также, что этот ответ был объединен с другим вопросом. Кто может сказать после
стольких
Вы можете добавить несколько предложений об алгоритме, используемом модулем дробей (и, возможно, обновить свой ответ для Python3).
einpoklum
21

Если вывод должен дать читателю быстрое представление о порядке результата, нет смысла возвращать что-то вроде «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;
}
JP
источник
3
Это тот вид нестандартного мышления, которого нам нужно больше! Отличное предложение.
edsko 01
1
Немного уродливый, но очень быстрый и практичный способ
Bosak
1
Это интересный и удивительно простой подход. Чтобы сэкономить место, вы можете вместо этого выполнить двоичный поиск в массиве или создать двоичное дерево, но ваш подход, вероятно, немного быстрее (вы можете сэкономить место, используя один вызов strcat перед возвратом и назначив var, где он сейчас вызывается). Также я бы включил 3/10 и 7/10, но, может быть, это только я.
jimhark
1
Вдохновленный этим решением, я создал короткий (но совершенно неоптимизированный) код. Его можно легко расширить, чтобы охватить более широкий диапазон фракций. jsfiddle.net/PdL23/1
Deepak Joy
1
Обратите внимание, что 1/1000он также очень удобочитаем, но приведенный выше алгоритм дает только очень грубое 1/10приближение; Я считаю , что можно улучшить с точки зрения которых по- человечески читаемых знаменатели можно выбрать из, и / или добавление <, >, <<, >>префиксы , чтобы дать представление о грубости приближения.
vladr 06
16

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

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: преобразование десятичного числа в дробное, преобразование десятичного в дробный код)

Девинмур
источник
2
Обратите внимание, что этот алгоритм занимает время Ω (m), когда f = n / m. И это может быть много, даже если вы этого не собирались (рассмотрим 0,66666666667).
einpoklum
10

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

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

3.141592 * 1000000 = 3141592

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

3 + (141592 / 1000000)

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

3 + (17699 / 125000)

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

Nlucaroni
источник
9

Вот версии 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;
}
мивк
источник
9

Реализация AC #

/// <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.
    /// http://stackoverflow.com/questions/95727/how-to-convert-floats-to-human-readable-fractions
    /// </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);
    }
}
Том
источник
7

Штерна-Броко Дерево вызывает довольно естественным образом аппроксимировать действительные числа дробями с простыми знаменателями.

Дуг МакКлин
источник
6

Отчасти проблема в том, что такое количество дробей на самом деле нелегко интерпретировать как дроби. Например, 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. Вы делаете это до тех пор, пока не достигнете квадратного корня меньшего числа или больше.

После того, как вы это сделаете, вам понадобится

Орион Адриан
источник
1
Я бы предложил использовать алгоритм Евклида для этого последнего шага
Graphics Noob
4

«Допустим, у нас есть 0,33, нам нужно вывести« 1/3 ».»

Какую точность вы ожидаете от "решения"? 0,33 не равно 1/3. Как распознать «хороший» (легко читаемый) ответ?

Несмотря ни на что, возможный алгоритм может быть:

Если вы ожидаете найти ближайшую дробь в форме X / Y, где Y меньше 10, то вы можете выполнить цикл по всем 9 возможным Y, для каждого Y вычислить X, а затем выбрать наиболее точную.

Suma
источник
3

Я думаю, что лучший способ сделать это - сначала преобразовать значение с плавающей запятой в представление ascii. В C ++ вы можете использовать ostringstream или в C, вы можете использовать sprintf. Вот как это будет выглядеть на C ++:

ostringstream oss;
float num;
cin >> num;
oss << num;
string numStr = oss.str();
int i = numStr.length(), pow_ten = 0;
while (i > 0) {
    if (numStr[i] == '.')
        break;
    pow_ten++;
    i--;
}
for (int j = 1; j < pow_ten; j++) {
    num *= 10.0;
}
cout << static_cast<int>(num) << "/" << pow(10, pow_ten - 1) << endl;

Аналогичный подход можно было бы применить в прямом C.

После этого вам нужно будет проверить, является ли дробь наименьшей величиной. Этот алгоритм даст точный ответ, т.е. 0,33 выдаст «33/100», а не «1/3». Однако 0,4 даст «4/10», что при сокращении до наименьшего значения будет «2/5». Возможно, это не так мощно, как решение EppStein, но я считаю, что это более просто.

уд / мин
источник
8 лет спустя я познакомился с вашим решением, я протестировал, и до сих пор оно работает отлично, но вы сказали, что оно не так мощно, как решение EppStein, и мне интересно, почему. Поскольку ваше решение намного проще, разве это не должно быть предпочтительным решением, разве мы не должны делать максимально простой код, если он работает и безопасен?
HBatalha
3

Встроенное решение на R:

library(MASS)
fractions(0.666666666)
## [1] 2/3

При этом используется метод непрерывного дроби и имеет факультативный cyclesи max.denominatorаргументы для регулировки точности.

Бен Болкер
источник
Также library(numbers)и contFrac(0.6666); чтобы получить желаемую строку:paste(contFrac(0.666, tol=1e-03)$rat, collapse="/")
rbatt,
2

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

Марк Бесси
источник
2

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

  1. Умножить и разделить на 10 ^ x, где x - степень 10, необходимая для того, чтобы в числе не осталось десятичных знаков. Пример: умножьте 0,33 на 10 ^ 2 = 100, чтобы получилось 33, и разделите на то же самое, чтобы получить 33/100.
  2. Уменьшите числитель и знаменатель полученной дроби путем факторизации, пока вы больше не сможете получать целые числа из результата.
  3. Полученная уменьшенная дробь должна быть вашим ответом.

Пример: 0,2 = 0,2 x 10 ^ 1/10 ^ 1 = 2/10 = 1/5.

Итак, это можно прочитать как «1 часть из 5».

Паскаль
источник
2

Одно из решений - просто хранить все числа как рациональные числа. Существуют библиотеки для арифметики рациональных чисел (например, GMP ). При использовании объектно-ориентированного языка вы можете просто использовать библиотеку классов рациональных чисел, чтобы заменить свой числовой класс.

Финансовые программы, среди прочего, будут использовать такое решение, чтобы иметь возможность производить точные вычисления и сохранять точность, которая может быть потеряна при использовании простого поплавка.

Конечно, это будет намного медленнее, поэтому это может оказаться непрактичным для вас. Зависит от того, сколько вычислений вам нужно сделать, и насколько важна для вас точность.

a = rational(1);
b = rational(3);
c = a / b;

print (c.asFraction)  --->  "1/3"
print (c.asFloat) ----> "0.333333"
робот
источник
2

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

В общем случае это неправильно, потому что 1/3 = 0,3333333 = 0. (3) Более того, из предложенных выше решений невозможно выяснить, можно ли десятичное число преобразовать в дробь с определенной точностью, потому что вывод всегда дробный.

НО, я предлагаю свою комплексную функцию с множеством опций, основанных на идее бесконечных геометрических рядов , в частности, на формуле:

введите описание изображения здесь

Сначала эта функция пытается найти период дроби в строковом представлении. После этого применяется описанная выше формула.

Код рациональных чисел заимствован из реализации рациональных чисел Стивена М. МакКейми на C #. Надеюсь, перенести мой код на другие языки не так уж и сложно.

/// <summary>
/// Convert decimal to fraction
/// </summary>
/// <param name="value">decimal value to convert</param>
/// <param name="result">result fraction if conversation is succsess</param>
/// <param name="decimalPlaces">precision of considereation frac part of value</param>
/// <param name="trimZeroes">trim zeroes on the right part of the value or not</param>
/// <param name="minPeriodRepeat">minimum period repeating</param>
/// <param name="digitsForReal">precision for determination value to real if period has not been founded</param>
/// <returns></returns>
public static bool FromDecimal(decimal value, out Rational<T> result, 
    int decimalPlaces = 28, bool trimZeroes = false, decimal minPeriodRepeat = 2, int digitsForReal = 9)
{
    var valueStr = value.ToString("0.0000000000000000000000000000", CultureInfo.InvariantCulture);
    var strs = valueStr.Split('.');

    long intPart = long.Parse(strs[0]);
    string fracPartTrimEnd = strs[1].TrimEnd(new char[] { '0' });
    string fracPart;

    if (trimZeroes)
    {
        fracPart = fracPartTrimEnd;
        decimalPlaces = Math.Min(decimalPlaces, fracPart.Length);
    }
    else
        fracPart = strs[1];

    result = new Rational<T>();
    try
    {
        string periodPart;
        bool periodFound = false;

        int i;
        for (i = 0; i < fracPart.Length; i++)
        {
            if (fracPart[i] == '0' && i != 0)
                continue;

            for (int j = i + 1; j < fracPart.Length; j++)
            {
                periodPart = fracPart.Substring(i, j - i);
                periodFound = true;
                decimal periodRepeat = 1;
                decimal periodStep = 1.0m / periodPart.Length;
                var upperBound = Math.Min(fracPart.Length, decimalPlaces);
                int k;
                for (k = i + periodPart.Length; k < upperBound; k += 1)
                {
                    if (periodPart[(k - i) % periodPart.Length] != fracPart[k])
                    {
                        periodFound = false;
                        break;
                    }
                    periodRepeat += periodStep;
                }

                if (!periodFound && upperBound - k <= periodPart.Length && periodPart[(upperBound - i) % periodPart.Length] > '5')
                {
                    var ind = (k - i) % periodPart.Length;
                    var regroupedPeriod = (periodPart.Substring(ind) + periodPart.Remove(ind)).Substring(0, upperBound - k);
                    ulong periodTailPlusOne = ulong.Parse(regroupedPeriod) + 1;
                    ulong fracTail = ulong.Parse(fracPart.Substring(k, regroupedPeriod.Length));
                    if (periodTailPlusOne == fracTail)
                        periodFound = true;
                }

                if (periodFound && periodRepeat >= minPeriodRepeat)
                {
                    result = FromDecimal(strs[0], fracPart.Substring(0, i), periodPart);
                    break;
                }
                else
                    periodFound = false;
            }

            if (periodFound)
                break;
        }

        if (!periodFound)
        {
            if (fracPartTrimEnd.Length >= digitsForReal)
                return false;
            else
            {
                result = new Rational<T>(long.Parse(strs[0]), 1, false);
                if (fracPartTrimEnd.Length != 0)
                    result = new Rational<T>(ulong.Parse(fracPartTrimEnd), TenInPower(fracPartTrimEnd.Length));
                return true;
            }
        }

        return true;
    }
    catch
    {
        return false;
    }
}

public static Rational<T> FromDecimal(string intPart, string fracPart, string periodPart)
{
    Rational<T> firstFracPart;
    if (fracPart != null && fracPart.Length != 0)
    {
        ulong denominator = TenInPower(fracPart.Length);
        firstFracPart = new Rational<T>(ulong.Parse(fracPart), denominator);
    }
    else
        firstFracPart = new Rational<T>(0, 1, false);

    Rational<T> secondFracPart;
    if (periodPart != null && periodPart.Length != 0)
        secondFracPart =
            new Rational<T>(ulong.Parse(periodPart), TenInPower(fracPart.Length)) *
            new Rational<T>(1, Nines((ulong)periodPart.Length), false);
    else
        secondFracPart = new Rational<T>(0, 1, false);

    var result = firstFracPart + secondFracPart;
    if (intPart != null && intPart.Length != 0)
    {
        long intPartLong = long.Parse(intPart);
        result = new Rational<T>(intPartLong, 1, false) + (intPartLong == 0 ? 1 : Math.Sign(intPartLong)) * result;
    }

    return result;
}

private static ulong TenInPower(int power)
{
    ulong result = 1;
    for (int l = 0; l < power; l++)
        result *= 10;
    return result;
}

private static decimal TenInNegPower(int power)
{
    decimal result = 1;
    for (int l = 0; l > power; l--)
        result /= 10.0m;
    return result;
}

private static ulong Nines(ulong power)
{
    ulong result = 9;
    if (power >= 0)
        for (ulong l = 0; l < power - 1; l++)
            result = result * 10 + 9;
    return result;
}

Вот несколько примеров использования:

Rational<long>.FromDecimal(0.33333333m, out r, 8, false);
// then r == 1 / 3;

Rational<long>.FromDecimal(0.33333333m, out r, 9, false);
// then r == 33333333 / 100000000;

Ваш случай с обрезкой нулевой части правой части:

Rational<long>.FromDecimal(0.33m, out r, 28, true);
// then r == 1 / 3;

Rational<long>.FromDecimal(0.33m, out r, 28, true);
// then r == 33 / 100;

Мин. Период демонстрации:

Rational<long>.FromDecimal(0.123412m, out r, 28, true, 1.5m));
// then r == 1234 / 9999;
Rational<long>.FromDecimal(0.123412m, out r, 28, true, 1.6m));
// then r == 123412 / 1000000; because of minimu repeating of period is 0.1234123 in this case.

Округление в конце:

Rational<long>.FromDecimal(0.8888888888888888888888888889m, out r));
// then r == 8 == 9;

Самый интересный случай:

Rational<long>.FromDecimal(0.12345678m, out r, 28, true, 2, 9);
// then r == 12345678 / 100000000;

Rational<long>.FromDecimal(0.12345678m, out r, 28, true, 2, 8);
// Conversation failed, because of period has not been founded and there are too many digits in fraction part of input value.

Rational<long>.FromDecimal(0.12121212121212121m, out r, 28, true, 2, 9));
// then r == 4 / 33; Despite of too many digits in input value, period has been founded. Thus it's possible to convert value to fraction.

Остальные тесты и код каждый может найти в моей библиотеке MathFunctions на github .

Иван Кочуркин
источник
2

У Ruby уже есть встроенное решение:

0.33.rationalize.to_s # => "33/100"
0.4.rationalize.to_s # => "2/5"

В Rails числовые атрибуты ActiveRecord также могут быть преобразованы:

product.size = 0.33
product.size.to_r.to_s # => "33/100"
Джош В. Льюис
источник
2

Ответьте на C ++, предполагая, что у вас есть класс BigInt, который может хранить целые числа неограниченного размера.

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

void GetRational(double val)
{
    if (val == val+1) // Inf
        throw "Infinite Value";
    if (val != val) // NaN
        throw "Undefined Value";

    bool sign = false;
    BigInt enumerator = 0;
    BigInt denominator = 1;

    if (val < 0)
    {
        val = -val;
        sign = true;
    }

    while (val > 0)
    {
        unsigned int intVal = (unsigned int)val;
        val -= intVal;
        enumerator += intVal;
        val *= 2;
        enumerator *= 2;
        denominator *= 2;
    }

    BigInt gcd = GCD(enumerator,denominator);
    enumerator /= gcd;
    denominator /= gcd;

    Print(sign? "-":"+");
    Print(enumerator);
    Print("/");
    Print(denominator);

    // Or simply return {sign,enumerator,denominator} as you wish
}

Кстати, GetRational (0.0) вернет «+0/1», так что вы можете захотеть обработать этот случай отдельно.

PS: Я использую этот код в своем собственном классе RationalNum в течение нескольких лет, и он был тщательно протестирован.

Барак Манос
источник
Ваш пример, похоже, разбивается на такие значения, как 1,333333 ... он входит в очень длинный цикл, пытаясь найти значение, и, похоже, не работает ... отлично работает с другими простыми значениями, такими как 1,25
Адамски
@ Адамски: Спасибо. Период «сходимости» whileцикла ограничен размером double, который обычно составляет 64 бита. Таким образом, это не зависит от начального значения input ( val). Однако GCDфункция действительно зависит от этого значения, хотя обычно довольно быстро сходится к решению. Возможно ли, что вы неправильно реализовали эту функцию?
barak manos
@Adamski: Кроме того, как я упоминал в начале ответа, если вы используете unsigned long longвместо BigInt, то это не обязательно даст правильный результат для каждого входного значения ... Но даже в этом сценарии код не предполагается «зайти в очень длинный цикл».
барак манос
Ах, да, это вполне возможно, функция GCD, которую я использовал, является частью класса BigInteger библиотеки Juce. Спасибо за информацию!
Adamski
@ Адамски: Значит , не имеет смысла, что GCDфункция не реализована должным образом. Вы проверяли, работает ли код долго во время whileцикла или после него? Я проверю значение 1,33333, чтобы увидеть, что за этим стоит. Спасибо.
barak manos
2

Этот алгоритм Иэна Ричардса / Джона Кеннеди не только возвращает хорошие дроби, но и очень хорошо работает с точки зрения скорости. Это код C #, взятый из этого ответа .

Он может обрабатывать все doubleзначения, кроме специальных значений, таких как NaN и +/- бесконечность, которые вам придется добавить при необходимости.

Он возвращает new Fraction(numerator, denominator) . Замените на свой собственный.

Дополнительные примеры значений и сравнение с другими алгоритмами см. Здесь

public Fraction RealToFraction(double value, double accuracy)
{
    if (accuracy <= 0.0 || accuracy >= 1.0)
    {
        throw new ArgumentOutOfRangeException("accuracy", "Must be > 0 and < 1.");
    }

    int sign = Math.Sign(value);

    if (sign == -1)
    {
        value = Math.Abs(value);
    }

    // Accuracy is the maximum relative error; convert to absolute maxError
    double maxError = sign == 0 ? accuracy : value * accuracy;

    int n = (int) Math.Floor(value);
    value -= n;

    if (value < maxError)
    {
        return new Fraction(sign * n, 1);
    }

    if (1 - maxError < value)
    {
        return new Fraction(sign * (n + 1), 1);
    }

    double z = value;
    int previousDenominator = 0;
    int denominator = 1;
    int numerator;

    do
    {
        z = 1.0 / (z - (int) z);
        int temp = denominator;
        denominator = denominator * (int) z + previousDenominator;
        previousDenominator = temp;
        numerator = Convert.ToInt32(value * denominator);
    }
    while (Math.Abs(value - (double) numerator / denominator) > maxError && z != (int) z);

    return new Fraction((n * denominator + numerator) * sign, denominator);
}

Примеры значений, возвращаемых этим алгоритмом:

Accuracy: 1.0E-3      | Richards                     
Input                 | Result           Error       
======================| =============================
   3                  |       3/1          0         
   0.999999           |       1/1         1.0E-6     
   1.000001           |       1/1        -1.0E-6     
   0.50 (1/2)         |       1/2          0         
   0.33... (1/3)      |       1/3          0         
   0.67... (2/3)      |       2/3          0         
   0.25 (1/4)         |       1/4          0         
   0.11... (1/9)      |       1/9          0         
   0.09... (1/11)     |       1/11         0         
   0.62... (307/499)  |       8/13        2.5E-4     
   0.14... (33/229)   |      16/111       2.7E-4     
   0.05... (33/683)   |      10/207      -1.5E-4     
   0.18... (100/541)  |      17/92       -3.3E-4     
   0.06... (33/541)   |       5/82       -3.7E-4     
   0.1                |       1/10         0         
   0.2                |       1/5          0         
   0.3                |       3/10         0         
   0.4                |       2/5          0         
   0.5                |       1/2          0         
   0.6                |       3/5          0         
   0.7                |       7/10         0         
   0.8                |       4/5          0         
   0.9                |       9/10         0         
   0.01               |       1/100        0         
   0.001              |       1/1000       0         
   0.0001             |       1/10000      0         
   0.33333333333      |       1/3         1.0E-11    
   0.333              |     333/1000       0         
   0.7777             |       7/9         1.0E-4     
   0.11               |      10/91       -1.0E-3     
   0.1111             |       1/9         1.0E-4     
   3.14               |      22/7         9.1E-4     
   3.14... (pi)       |      22/7         4.0E-4     
   2.72... (e)        |      87/32        1.7E-4     
   0.7454545454545    |      38/51       -4.8E-4     
   0.01024801004      |       2/195       8.2E-4     
   0.99011            |     100/101      -1.1E-5     
   0.26... (5/19)     |       5/19         0         
   0.61... (37/61)    |      17/28        9.7E-4     
                      | 
Accuracy: 1.0E-4      | Richards                     
Input                 | Result           Error       
======================| =============================
   0.62... (307/499)  |     299/486      -6.7E-6     
   0.05... (33/683)   |      23/476       6.4E-5     
   0.06... (33/541)   |      33/541        0         
   1E-05              |       1/99999     1.0E-5     
   0.7777             |    1109/1426     -1.8E-7     
   3.14... (pi)       |     333/106      -2.6E-5     
   2.72... (e)        |     193/71        1.0E-5     
   0.61... (37/61)    |      37/61         0         
Кей Зед
источник
1

У вас будут две основные проблемы, которые сделают это трудным:

1) Плавающая точка не является точным представлением, что означает, что если у вас есть дробная часть «x / y», которая дает значение «z», ваш алгоритм дроби может вернуть результат, отличный от «x / y».

2) В бесконечности иррациональных чисел намного больше, чем рациональных. Рациональное число - это число, которое можно представить в виде дроби. Нерациональные существа, которые не могут.

Однако дешевым способом, поскольку точность с плавающей запятой ограничена, вы всегда можете представить ее как некую форму фракции. (Думаю...)

Торлак
источник
4
Поплавок (или двойной) - это дробь. Его знаменатель - степень 2. Вот почему они не могут точно представлять некоторые рациональные числа.
erickson
1

Завершил приведенный выше код и преобразовал его в as3

public static function toFrac(f:Number) : String
    {
        if (f>1)
        {
            var parte1:int;
            var parte2:Number;
            var resultado:String;
            var loc:int = String(f).indexOf(".");
            parte2 = Number(String(f).slice(loc, String(f).length));
            parte1 = int(String(f).slice(0,loc));
            resultado = toFrac(parte2);
            parte1 *= int(resultado.slice(resultado.indexOf("/") + 1, resultado.length)) + int(resultado.slice(0, resultado.indexOf("/")));
            resultado = String(parte1) +  resultado.slice(resultado.indexOf("/"), resultado.length)
            return resultado;
        }
        if( f < 0.47 )
            if( f < 0.25 )
                if( f < 0.16 )
                    if( f < 0.13 )
                        if( f < 0.11 )
                            return "1/10";
                        else
                            return "1/9";
                    else
                        if( f < 0.14 )
                            return "1/8";
                        else
                            return "1/7";
                else
                    if( f < 0.19 )
                        return "1/6";
                    else
                        if( f < 0.22 )
                            return "1/5";
                        else
                            return "2/9";
            else
                if( f < 0.38 )
                    if( f < 0.29 )
                        return "1/4";
                    else
                        if( f < 0.31 )
                            return "2/7";
                        else
                            return "1/3";
                else
                    if( f < 0.43 )
                        if( f < 0.40 )
                            return "3/8";
                        else
                            return "2/5";
                    else
                        if( f < 0.44 )
                            return "3/7";
                        else
                            return "4/9";
        else
            if( f < 0.71 )
                if( f < 0.60 )
                    if( f < 0.56 )
                        return "1/2";
                    else
                        if( f < 0.57 )
                            return "5/9";
                        else
                            return "4/7";
                else
                    if( f < 0.63 )
                        return "3/5";
                    else
                        if( f < 0.66 )
                            return "5/8";
                        else
                            return "2/3";
            else
                if( f < 0.80 )
                    if( f < 0.74 )
                        return "5/7";
                    else
                        if(f < 0.78 )
                            return "3/4";
                        else
                            return "7/9";
                else
                    if( f < 0.86 )
                        if( f < 0.83 )
                            return "4/5";
                        else
                            return "5/6";
                    else
                        if( f < 0.88 )
                            return "6/7";
                        else
                            if( f < 0.89 )
                                return "7/8";
                            else
                                if( f < 0.90 )
                                    return "8/9";
                                else
                                    return "9/10";
    }
Жоао Лопес
источник
Спасибо, я использовал это для Delphi, проще переносить, чем все эти фигурные вещи
Питер Тернер
1

Вот быстрая и грязная реализация на javascript, которая использует подход грубой силы. Совсем не оптимизирован, он работает с заранее определенным диапазоном фракций: http://jsfiddle.net/PdL23/1/

/* This should convert any decimals to a simplified fraction within the range specified by the two for loops. Haven't done any thorough testing, but it seems to work fine.

I have set the bounds for numerator and denominator to 20, 20... but you can increase this if you want in the two for loops.

Disclaimer: Its not at all optimized. (Feel free to create an improved version.)
*/

decimalToSimplifiedFraction = function(n) {

    for(num = 1; num < 20; num++) {  // "num" is the potential numerator
        for(den = 1; den < 20; den++) {  // "den" is the potential denominator
            var multiplyByInverse = (n * den ) / num;

            var roundingError = Math.round(multiplyByInverse) - multiplyByInverse;

            // Checking if we have found the inverse of the number, 
            if((Math.round(multiplyByInverse) == 1) && (Math.abs(roundingError) < 0.01)) {
                return num + "/" + den;
            }
        }
    }
};

//Put in your test number here.
var floatNumber = 2.56;

alert(floatNumber + " = " + decimalToSimplifiedFraction(floatNumber));

Это вдохновлено подходом, используемым JPS.

Дипак Джой
источник
0

Как утверждали многие люди, вы действительно не можете преобразовать числа с плавающей запятой обратно в дробь (если только она не очень точна, например, 0,25). Конечно, вы можете создать какой-то поиск для большого массива дробей и использовать какую-то нечеткую логику для получения желаемого результата. Опять же, это не будет точно, и вам нужно будет определить нижнюю границу того, насколько большим должен быть знаменатель.

.32 <x <.34 = 1/3 или что-то в этом роде.

Тим
источник
0

Я наткнулся на особенно элегантное решение Haskell, использующее анаморфизм. Это зависит от пакета рекурсивных схем .

{-# LANGUAGE AllowAmbiguousTypes #-}
{-# LANGUAGE FlexibleContexts    #-}

import           Control.Applicative   (liftA2)
import           Control.Monad         (ap)
import           Data.Functor.Foldable
import           Data.Ratio            (Ratio, (%))

isInteger :: (RealFrac a) => a -> Bool
isInteger = ((==) <*>) (realToFrac . floor)

continuedFraction :: (RealFrac a) => a -> [Int]
continuedFraction = liftA2 (:) floor (ana coalgebra)
    where coalgebra x
              | isInteger x = Nil
              | otherwise = Cons (floor alpha) alpha
                  where alpha = 1 / (x - realToFrac (floor x))

collapseFraction :: (Integral a) => [Int] -> Ratio a
collapseFraction [x]    = fromIntegral x % 1
collapseFraction (x:xs) = (fromIntegral x % 1) + 1 / collapseFraction xs

-- | Use the nth convergent to approximate x
approximate :: (RealFrac a, Integral b) => a -> Int -> Ratio b
approximate x n = collapseFraction $ take n (continuedFraction x)

Если вы попробуете это в ghci, это действительно сработает!

λ:> approximate pi 2
22 % 7

источник