Алгоритм упрощения десятичной дроби

Question

Я попытался написать алгоритм, упрощающий десятичную дробь, и понял, что это не слишком просто. Удивительно, но я посмотрел в Интернете и все коды, которые я нашел, где либо слишком долго, либо не работал бы в некоторых случаях. Что еще более раздражало, так это то, что они не работали на повторяющиеся десятичные дроби. Мне было интересно, однако, будет ли здесь математик / программист, который понимает все вовлеченные процессы в упрощении десятичной дроби до дроби. Кто-нибудь?

Answer 1

Наиболее популярными решениями этой проблемы являются алгоритм Ричардса и алгоритм Штерна-Брокота , реализованный с помощью btilly с оптимизацией скорости с помощью btilly и Jay Zed,Алгоритм Ричардса является самым быстрым, но он не гарантирует возврата лучшей дроби.

У меня есть решение этой проблемы, которое всегда дает лучшую дробь, а также работает быстрее, чем все вышеперечисленные алгоритмы.Вот алгоритм на C # (объяснение и тест скорости ниже).

Это короткий алгоритм без комментариев.Полная версия приведена в исходном коде в конце.

public static Fraction DoubleToFractionSjaak(double value, double accuracy)
{
    int sign = value < 0 ? -1 : 1;
    value = value < 0 ? -value : value;
    int integerpart = (int)value;
    value -=  integerpart;
    double minimalvalue = value - accuracy;
    if (minimalvalue < 0.0) return new Fraction(sign * integerpart, 1);
    double maximumvalue = value + accuracy;
    if (maximumvalue > 1.0) return new Fraction(sign * (integerpart + 1), 1);
    int a = 0;
    int b = 1;
    int c = 1;
    int d = (int)(1 / maximumvalue);
    while (true)
    {
        int n = (int)((b * minimalvalue - a) / (c - d * minimalvalue));
        if (n == 0) break;
        a += n * c;
        b += n * d;
        n = (int)((c - d * maximumvalue) / (b * maximumvalue - a));
        if (n == 0) break;
        c += n * a;
        d += n * b;
    }
    int denominator = b + d;
    return new Fraction(sign * (integerpart * denominator + (a + c)), denominator);
}

Где Fraction - простой класс для хранения дроби, например:

public class Fraction
{
    public int Numerator { get; private set; }
    public int Denominator { get; private set; }

    public Fraction(int numerator, int denominator)
    {
        Numerator = numerator;
        Denominator = denominator;
    }     
}

Howэто работает

Как и другие упомянутые решения, мое решение основано на непрерывной дроби.Другие решения, такие как решение Eppstein или решения, основанные на повторяющихся десятичных числах, оказались медленнее и / или дают субоптимальные результаты.

Продолжение дроби
Решения на основенепрерывная дробь в основном основана на двух алгоритмах, оба описаны в статье Иана Ричардса, опубликованной здесь в 1981 году. Он назвал их «алгоритм медленной непрерывной дроби» и «алгоритм быстрой непрерывной дроби».Первый известен как алгоритм Штерна-Броко, а второй известен как алгоритм Ричардса.

Мой алгоритм (краткое объяснение)
Чтобы полностью понять мой алгоритм, вам нужночтобы прочитать статью Яна Ричардса или хотя бы понять, что такое пара Фэри.Кроме того, прочитайте алгоритм с комментариями в конце этой статьи.

Алгоритм использует пару Фари, содержащую левую и правую дроби.Повторно принимая посредник, он приближается к целевому значению.Это подобно медленному алгоритму, но есть два основных различия:

1. Несколько итераций выполняются одновременно, пока посредник остается на одной стороне от целевого значения.
2. Левая и правая дроби не могут быть ближе к целевому значению, чем заданная точность.

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

Тест скорости

Я провел несколько тестов скорости на своем ноутбуке с использованием следующих алгоритмов:

1. Улучшен алгоритм замедления с помощью Kay Zed и btilly
2. Реализация алгоритма Fast Джона Кеннеди, преобразованная в C # с помощью Kay Zed
3. Моя реализация алгоритма Fast (близко коригинал Иана Ричардса)
4. Реализация алгоритма быстрого алгоритма Джереми Херрмана
5. Мой алгоритм выше

Я опустил исходный алгоритм медленного алгоритма с помощью btilly из-за его плохой производительности в худшем случае.

Набор тестов
Я выбираю набор целевых значений (очень произвольно) и вычисляю дробь 100000 разс 5 разными точностями.Поскольку некоторые (будущие) алгоритмы не могли обрабатывать неправильные дроби, были протестированы только целевые значения от 0,0 до 1,0.Точность была взята из диапазона от 2 до 6 знаков после запятой (от 0,005 до 0,0000005).Использовался следующий набор:

0.999999, 0.000001, 0.25
0.33, 0.333, 0.3333, 0.33333, 0.333333, 0.333333333333, 
0.666666666666, 0.777777777777, 0.090909090909, 0.263157894737,
0.606557377049, 0.745454545454, 0.000050183168565,
pi - 3, e - 2.0, sqrt(2) - 1

Результаты

Я сделал 13 тестовых прогонов.Результат в миллисекундах, необходимых для всего набора данных.

    Run 1   Run 2   Run 3   Run 4   Run 5   Run 6   Run 7   Run 8   Run 9   Run 10  Run 11  Run 12  Run 13
1.  9091    9222    9070    9111    9091    9108    9293    9118    9115    9113    9102    9143    9121
2.  7071    7125    7077    6987    7126    6985    7037    6964    7023    6980    7053    7050    6999
3.  6903    7059    7062    6891    6942    6880    6882    6918    6853    6918    6893    6993    6966
4.  7546    7554    7564    7504    7483    7529    7510    7512    7517    7719    7513    7520    7514
5.  6839    6951    6882    6836    6854    6880    6846    7017    6874    6867    6828    6848    6864

Заключение (пропуская анализ)
Даже без статистического анализа легко увидеть, что мой алгоритмбыстрее, чем другие проверенные алгоритмы.Однако разница с самым быстрым вариантом «быстрого алгоритма» составляет менее 1%.Улучшенный медленный алгоритм на 30-35% медленнее, чем самый быстрый алгоритм ».

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

• Дает ли алгоритм лучший результат?
• Является ли алгоритмдоступно на моем любимом языке?
• Каков размер кода алгоритма?
• Является ли алгоритм читабельным, понятным?

Исходный код

Исходный код ниже содержит все используемые алгоритмы.Он включает в себя:

• Мой оригинальный алгоритм (с комментариями)
• Еще более быстрая версия моего алгоритма (но менее читаемая)
• Оригинальный медленный алгоритм
• Все проверенные алгоритмы

public class DoubleToFraction
{
    // ===================================================
    // Sjaak algorithm - original version
    //

    public static Fraction SjaakOriginal(double value, double accuracy)
    {
        // Split value in a sign, an integer part, a fractional part
        int sign = value < 0 ? -1 : 1;
        value = value < 0 ? -value : value;
        int integerpart = (int)value;
        value -= integerpart;

        // check if the fractional part is near 0
        double minimalvalue = value - accuracy;
        if (minimalvalue < 0.0) return new Fraction(sign * integerpart, 1);

        // check if the fractional part is near 1
        double maximumvalue = value + accuracy;
        if (maximumvalue > 1.0) return new Fraction(sign * (integerpart + 1), 1);

        // The left fraction (a/b) is initially (0/1), the right fraction (c/d) is initially (1/1)
        // Together they form a Farey pair.
        // We will keep the left fraction below the minimumvalue and the right fraction above the maximumvalue
        int a = 0;
        int b = 1;
        int c = 1;
        int d = (int)(1 / maximumvalue);

        // The first interation is performed above. Calculate maximum n where (n*a+c)/(n*b+d) >= maximumvalue 
        // This is the same as n <= 1/maximumvalue - 1, d will become n+1 = floor(1/maximumvalue)

        // repeat forever (at least until we cannot close in anymore)
        while (true)
        {
            // Close in from the left n times. 
            // Calculate maximum n where (a+n*c)/(b+n*d) <= minimalvalue
            // This is the same as n <= (b * minimalvalue - a) / (c-d*minimalvalue)
            int n = (int)((b * minimalvalue - a) / (c - d * minimalvalue));

            // If we cannot close in from the left (and also not from the right anymore) the loop ends
            if (n == 0) break;

            // Update left fraction
            a += n * c;
            b += n * d;

            // Close in from the right n times.
            // Calculate maximum n where (n*a+c)/(n*b+d) >= maximumvalue
            // This is the same as n <= (c - d * maximumvalue) / (b * maximumvalue - a)
            n = (int)((c - d * maximumvalue) / (b * maximumvalue - a));

            // If we cannot close in from the right (and also not from the left anymore) the loop ends
            if (n == 0) break;

            // Update right fraction
            c += n * a;
            d += n * b;
        }

        // We cannot close in anymore
        // The best fraction will be the mediant of the left and right fraction = (a+c)/(b+d)
        int denominator = b + d;
        return new Fraction(sign * (integerpart * denominator + (a + c)), denominator);

    }

    // ===================================================
    // Sjaak algorithm - faster version
    //

    public static Fraction SjaakFaster(double value, double accuracy)
    {
        int sign = value < 0 ? -1 : 1;
        value = value < 0 ? -value : value;
        int integerpart = (int)value;
        value -= integerpart;
        double minimalvalue = value - accuracy;
        if (minimalvalue < 0.0) return new Fraction(sign * integerpart, 1);
        double maximumvalue = value + accuracy;
        if (maximumvalue > 1.0) return new Fraction(sign * (integerpart + 1), 1);
        //int a = 0;
        int b = 1;
        //int c = 1;
        int d = (int)(1 / maximumvalue);
        double left_n = minimalvalue; // b * minimalvalue - a
        double left_d = 1.0 - d * minimalvalue; // c - d * minimalvalue
        double right_n = 1.0 - d * maximumvalue; // c - d * maximumvalue
        double right_d = maximumvalue; // b * maximumvalue - a            
        while (true)
        {
            if (left_n < left_d) break;
            int n = (int)(left_n / left_d);
            //a += n * c;
            b += n * d;
            left_n -= n * left_d;
            right_d -= n * right_n;
            if (right_n < right_d) break;
            n = (int)(right_n / right_d);
            //c += n * a;
            d += n * b;
            left_d -= n * left_n;
            right_n -= n * right_d;
        }


        int denominator = b + d;
        int numerator = (int)(value * denominator + 0.5);
        return new Fraction(sign * (integerpart * denominator + numerator), denominator);
    }

    // ===================================================
    // Original Farley - Implemented by btilly
    //

    public static Fraction OriginalFarley(double value, double accuracy)
    {
        // Split value in a sign, an integer part, a fractional part
        int sign = value < 0 ? -1 : 1;
        value = value < 0 ? -value : value;
        int integerpart = (int)value;
        value -= integerpart;

        // check if the fractional part is near 0
        double minimalvalue = value - accuracy;
        if (minimalvalue < 0.0) return new Fraction(sign * integerpart, 1);

        // check if the fractional part is near 1
        double maximumvalue = value + accuracy;
        if (maximumvalue > 1.0) return new Fraction(sign * (integerpart + 1), 1);

        // The lower fraction is 0/1
        int lower_numerator = 0;
        int lower_denominator = 1;

        // The upper fraction is 1/1
        int upper_numerator = 1;
        int upper_denominator = 1;

        while (true)
        {
            // The middle fraction is (lower_numerator + upper_numerator) / (lower_denominator + upper_denominator)
            int middle_numerator = lower_numerator + upper_numerator;
            int middle_denominator = lower_denominator + upper_denominator;

            if (middle_denominator * maximumvalue < middle_numerator)
            {
                // real + error < middle : middle is our new upper
                upper_numerator = middle_numerator;
                upper_denominator = middle_denominator;
            }
            else if (middle_numerator < minimalvalue * middle_denominator)
            {
                // middle < real - error : middle is our new lower
                lower_numerator = middle_numerator;
                lower_denominator = middle_denominator;
            }
            else
            {
                return new Fraction(sign * (integerpart * middle_denominator + middle_numerator), middle_denominator);
            }
        }
    }

    // ===================================================
    // Modified Farley - Implemented by btilly, Kay Zed
    //

    public static Fraction ModifiedFarley(double value, double accuracy)
    {
        // Split value in a sign, an integer part, a fractional part
        int sign = value < 0 ? -1 : 1;
        value = value < 0 ? -value : value;
        int integerpart = (int)value;
        value -= integerpart;

        // check if the fractional part is near 0
        double minimalvalue = value - accuracy;
        if (minimalvalue < 0.0) return new Fraction(sign * integerpart, 1);

        // check if the fractional part is near 1
        double maximumvalue = value + accuracy;
        if (maximumvalue > 1.0) return new Fraction(sign * (integerpart + 1), 1);

        // The lower fraction is 0/1
        int lower_numerator = 0;
        int lower_denominator = 1;

        // The upper fraction is 1/1
        int upper_numerator = 1;
        int upper_denominator = 1;

        while (true)
        {
            // The middle fraction is (lower_numerator + upper_numerator) / (lower_denominator + upper_denominator)
            int middle_numerator = lower_numerator + upper_numerator;
            int middle_denominator = lower_denominator + upper_denominator;

            if (middle_denominator * maximumvalue < middle_numerator)
            {
                // real + error < middle : middle is our new upper
                ModifiedFarleySeek(ref upper_numerator, ref upper_denominator, lower_numerator, lower_denominator, (un, ud) => (lower_denominator + ud) * maximumvalue < (lower_numerator + un));
            }
            else if (middle_numerator < minimalvalue * middle_denominator)
            {
                // middle < real - error : middle is our new lower
                ModifiedFarleySeek(ref lower_numerator, ref lower_denominator, upper_numerator, upper_denominator, (ln, ld) => (ln + upper_numerator) < minimalvalue * (ld + upper_denominator));
            }
            else
            {
                return new Fraction(sign * (integerpart * middle_denominator + middle_numerator), middle_denominator);
            }
        }
    }

    private static void ModifiedFarleySeek(ref int a, ref int b, int ainc, int binc, Func<int, int, bool> f)
    {
        // Binary seek for the value where f() becomes false
        a += ainc;
        b += binc;

        if (f(a, b))
        {
            int weight = 1;

            do
            {
                weight *= 2;
                a += ainc * weight;
                b += binc * weight;
            }
            while (f(a, b));

            do
            {
                weight /= 2;

                int adec = ainc * weight;
                int bdec = binc * weight;

                if (!f(a - adec, b - bdec))
                {
                    a -= adec;
                    b -= bdec;
                }
            }
            while (weight > 1);
        }
    }

    // ===================================================
    // Richards implementation by Jemery Hermann
    //

    public static Fraction RichardsJemeryHermann(double value, double accuracy, int maxIterations = 20)
    {

        // Split value in a sign, an integer part, a fractional part
        int sign = value < 0 ? -1 : 1;
        value = value < 0 ? -value : value;
        int integerpart = (int)value;
        value -= integerpart;

        // check if the fractional part is near 0
        double minimalvalue = value - accuracy;
        if (minimalvalue < 0.0) return new Fraction(sign * integerpart, 1);

        // check if the fractional part is near 1
        double maximumvalue = value + accuracy;
        if (maximumvalue > 1.0) return new Fraction(sign * (integerpart + 1), 1);

        // Richards - Implemented by Jemery Hermann
        double[] d = new double[maxIterations + 2];
        d[1] = 1;
        double z = value;
        double n = 1;
        int t = 1;

        while (t < maxIterations && Math.Abs(n / d[t] - value) > accuracy)
        {
            t++;
            z = 1 / (z - (int)z);
            d[t] = d[t - 1] * (int)z + d[t - 2];
            n = (int)(value * d[t] + 0.5);
        }

        return new Fraction(sign * (integerpart * (int)d[t] + (int)n), (int)d[t]);
    }

    // ===================================================
    // Richards implementation by Kennedy
    //

    public static Fraction RichardsKennedy(double value, double accuracy)
    {
        // Split value in a sign, an integer part, a fractional part
        int sign = value < 0 ? -1 : 1;
        value = value < 0 ? -value : value;
        int integerpart = (int)value;
        value -= integerpart;

        // check if the fractional part is near 0
        double minimalvalue = value - accuracy;
        if (minimalvalue < 0.0) return new Fraction(sign * integerpart, 1);

        // check if the fractional part is near 1
        double maximumvalue = value + accuracy;
        if (maximumvalue > 1.0) return new Fraction(sign * (integerpart + 1), 1);

        // Richards
        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 = (int)(value * denominator + 0.5);
        }
        while (Math.Abs(value - (double)numerator / denominator) > accuracy && z != (int)z);

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

    // ===================================================
    // Richards implementation by Sjaak
    //

    public static Fraction RichardsOriginal(double value, double accuracy)
    {
        // Split value in a sign, an integer part, a fractional part
        int sign = value < 0 ? -1 : 1;
        value = value < 0 ? -value : value;
        int integerpart = (int)value;
        value -= integerpart;

        // check if the fractional part is near 0
        double minimalvalue = value - accuracy;
        if (minimalvalue < 0.0) return new Fraction(sign * integerpart, 1);

        // check if the fractional part is near 1
        double maximumvalue = value + accuracy;
        if (maximumvalue > 1.0) return new Fraction(sign * (integerpart + 1), 1);

        // Richards
        double z = value;
        int denominator0 = 0;
        int denominator1 = 1;
        int numerator0 = 1;
        int numerator1 = 0;
        int n = (int)z;
        while (true)
        {
            z = 1.0 / (z - n);
            n = (int)z;

            int temp = denominator1;
            denominator1 = denominator1 * n + denominator0;
            denominator0 = temp;

            temp = numerator1;
            numerator1 = numerator1 * n + numerator0;
            numerator0 = temp;

            double d = (double)numerator1 / denominator1;
            if (d > minimalvalue && d < maximumvalue) break;
        }
        return new Fraction(sign * (integerpart * denominator1 + numerator1), denominator1);
    }

}

Answer 2

Повторяющийся десятичный знак может быть представлен двумя конечными десятичными знаками: левая часть перед повторением и повторяющаяся часть. Например. 1.6181818... = 1.6 + 0.1*(0.18...). Думайте об этом как a + b * sum(c * 10**-(d*k) for k in range(1, infinity)) (в нотации Python здесь). В моем примере a=1.6, b=0.1, c=18, d=2 (количество цифр в c). Бесконечную сумму можно упростить (sum(r**k for r in range(1, infinity)) == r / (1 - r), если я правильно помню), получив a + b * (c * 10**-d) / (1 - c * 10**-d)), конечное отношение. То есть начните с a, b, c и d как рациональных чисел, и вы получите другое.

(Это уточняет ответ Кирка Бродхерста, который является правильным, но не охватывает повторяющиеся десятичные дроби. Я не обещаю, что не допустил ошибок выше, хотя уверен, что общий подход работает.) 1016 *

Answer 3

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

Вот как это работает:

1. Найтивыяснить, является ли данное десятичное число отрицательным
2. Преобразовать десятичное число в абсолютное значение
3. Получить целую часть указанного десятичного числа
4. Получить десятичную часть
5. Проверить, повторяется ли десятичное число,Если десятичное число повторяется, мы затем возвращаем точное повторяющееся десятичное число
6. Если десятичное число не повторяется, начните уменьшение, изменив числитель на 10 ^ нет.десятичного числа, иначе мы вычитаем 1 из числителя
7. Затем уменьшаем дробь

Предварительный просмотр кода:

    private static string dec2frac(double dbl)
    {
        char neg = ' ';
        double dblDecimal = dbl;
        if (dblDecimal == (int) dblDecimal) return dblDecimal.ToString(); //return no if it's not a decimal
        if (dblDecimal < 0)
        {
            dblDecimal = Math.Abs(dblDecimal);
            neg = '-';
        }
        var whole = (int) Math.Truncate(dblDecimal);
        string decpart = dblDecimal.ToString().Replace(Math.Truncate(dblDecimal) + ".", "");
        double rN = Convert.ToDouble(decpart);
        double rD = Math.Pow(10, decpart.Length);

        string rd = recur(decpart);
        int rel = Convert.ToInt32(rd);
        if (rel != 0)
        {
            rN = rel;
            rD = (int) Math.Pow(10, rd.Length) - 1;
        }
        //just a few prime factors for testing purposes
        var primes = new[] {41, 43, 37, 31, 29, 23, 19, 17, 13, 11, 7, 5, 3, 2};
        foreach (int i in primes) reduceNo(i, ref rD, ref rN);

        rN = rN + (whole*rD);
        return string.Format("{0}{1}/{2}", neg, rN, rD);
    }

Спасибо @ Darius за предоставленную мне идею о том, какрешить повторяющиеся десятичные дроби:)

Answer 4

Мои 2 цента.Вот VB.NET-версия отличного алгоритма btilly:

   Public Shared Sub float_to_fraction(x As Decimal, ByRef Numerator As Long, ByRef Denom As Long, Optional ErrMargin As Decimal = 0.001)
    Dim n As Long = Int(Math.Floor(x))
    x -= n

    If x < ErrMargin Then
        Numerator = n
        Denom = 1
        Return
    ElseIf x >= 1 - ErrMargin Then
        Numerator = n + 1
        Denom = 1
        Return
    End If

    ' The lower fraction is 0/1
    Dim lower_n As Integer = 0
    Dim lower_d As Integer = 1
    ' The upper fraction is 1/1
    Dim upper_n As Integer = 1
    Dim upper_d As Integer = 1

    Dim middle_n, middle_d As Decimal
    While True
        ' The middle fraction is (lower_n + upper_n) / (lower_d + upper_d)
        middle_n = lower_n + upper_n
        middle_d = lower_d + upper_d
        ' If x + error < middle
        If middle_d * (x + ErrMargin) < middle_n Then
            ' middle is our new upper
            upper_n = middle_n
            upper_d = middle_d
            ' Else If middle < x - error
        ElseIf middle_n < (x - ErrMargin) * middle_d Then
            ' middle is our new lower
            lower_n = middle_n
            lower_d = middle_d
            ' Else middle is our best fraction
        Else
            Numerator = n * middle_d + middle_n
            Denom = middle_d
            Return
        End If
    End While
End Sub

Answer 5

Недавно мне пришлось выполнить эту задачу работы с десятичным типом данных, который хранится в нашей базе данных SQL Server.На уровне представления это значение было отредактировано как дробное значение в TextBox.Сложность здесь заключалась в работе с десятичным типом данных, который содержит довольно большие значения по сравнению с int или long.Таким образом, чтобы уменьшить вероятность переполнения данных, я придерживался десятичного типа данных на протяжении всего преобразования.

Прежде чем я начну, я хочу прокомментировать предыдущий ответ Кирка.Он абсолютно прав, пока не сделано никаких предположений.Однако, если разработчик ищет только повторяющиеся шаблоны в пределах десятичного типа данных, 3333333 ... можно представить как 1/3.Пример алгоритма можно найти по адресу basic-matmatics.com .Опять же, это означает, что вы должны делать предположения на основе доступной информации, и при использовании этого метода фиксируется только очень небольшое подмножество повторяющихся десятичных знаков.Однако для небольших чисел должно быть все в порядке.

Двигаясь вперед, позвольте мне сделать снимок моего решения.Если вы хотите прочитать полный пример с дополнительным кодом, я создал пост в блоге с гораздо более подробной информацией.

Преобразование десятичного типа данных в дробную строку

public static void DecimalToFraction(decimal value, ref decimal sign, ref decimal numerator, ref decimal denominator)
{
    const decimal maxValue = decimal.MaxValue / 10.0M;

    // e.g. .25/1 = (.25 * 100)/(1 * 100) = 25/100 = 1/4
    var tmpSign = value < decimal.Zero ? -1 : 1;
    var tmpNumerator = Math.Abs(value);
    var tmpDenominator = decimal.One;

    // While numerator has a decimal value
    while ((tmpNumerator - Math.Truncate(tmpNumerator)) > 0 && 
        tmpNumerator < maxValue && tmpDenominator < maxValue)
    {
        tmpNumerator = tmpNumerator * 10;
        tmpDenominator = tmpDenominator * 10;
    }

    tmpNumerator = Math.Truncate(tmpNumerator); // Just in case maxValue boundary was reached.
    ReduceFraction(ref tmpNumerator, ref tmpDenominator);
    sign = tmpSign;
    numerator = tmpNumerator;
    denominator = tmpDenominator;
}

public static string DecimalToFraction(decimal value)
{
    var sign = decimal.One;
    var numerator = decimal.One;
    var denominator = decimal.One;
    DecimalToFraction(value, ref sign, ref numerator, ref denominator);
    return string.Format("{0}/{1}", (sign * numerator).ToString().TruncateDecimal(), 
        denominator.ToString().TruncateDecimal());
}

Это довольно просто, когда DecimalToFraction (десятичное значение) - не более чем упрощенная точка входа для первого метода, который обеспечивает доступ ко всем компонентам, составляющим дробь.Если у вас есть десятичное число .325, то разделите его на 10 в степени числа десятичных знаков.Наконец уменьшить фракцию.И в этом примере .325 = 325/10 ^ 3 = 325/1000 = 13/40.

Далее, в другом направлении.

Преобразование дробной строки в десятичные данныеВведите

static readonly Regex FractionalExpression = new Regex(@"^(?<sign>[-])?(?<numerator>\d+)(/(?<denominator>\d+))?$");
public static decimal? FractionToDecimal(string fraction)
{
    var match = FractionalExpression.Match(fraction);
    if (match.Success)
    {
        // var sign = Int32.Parse(match.Groups["sign"].Value + "1");
        var numerator = Int32.Parse(match.Groups["sign"].Value + match.Groups["numerator"].Value);
        int denominator;
        if (Int32.TryParse(match.Groups["denominator"].Value, out denominator))
            return denominator == 0 ? (decimal?)null : (decimal)numerator / denominator;
        if (numerator == 0 || numerator == 1)
            return numerator;
    }
    return null;
}

Преобразование в десятичное число также довольно просто.Здесь мы анализируем дробные компоненты, сохраняем их во что-то, с чем мы можем работать (здесь десятичные значения) и выполняем наше деление.

Answer 6

первая функция получает формат строки fration "1/2" , вторая функция поиска gcd (наибольший общий делитель) для верхних и нижних частей.

public static string DoubleToFraction(double num)
    {            
        if (Math.Round(num, 6) == Math.Round(num, 0))
            return Math.Round(num, 0).ToString();
        bool minus = (num < 0) ? true : false;
        int up;
        if (minus)
            up = (int)((Math.Round(num, 6) - 0.000001) * 362880);
        else
            up = (int)((Math.Round(num, 6) + 0.000001) * 362880);
        int down = 362880;
        int div = gcd(up, down);
        up /= div;
        down /= div;
        return up + "/" + down;
    }
    public static int gcd(int a, int b)
    {
        if (b == 0)
            return Math.Abs(a);
        return gcd(b, a % b);
    }

Answer 7

Вот два Swift 4 преобразования популярных ответов на эту проблему:

public func decimalToFraction(_ d: Double) -> (Int, Int) {
    var df: Double = 1
    var top: Int = 1
    var bot: Int = 1

    while df != d {
        if df < d {
            top += 1
        } else {
            bot += 1
            top = Int(d * bot)
        }
        df = top / bot
    }
    return (top, bot)
}

public func realToFraction(_ value: Double, accuracy: Double = 0.00005) -> (Int, Int)? {
    var value = value
    guard accuracy >= 0 && accuracy <= 1 else {
        Swift.print(accuracy, "Must be > 0 and < 1.")
        return nil
    }
    let theSign = sign(value)
    if theSign == -1 {
        value = abs(value)
    }

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

    let n = floor(value)
    value -= n

    if value < maxError {
        return (Int(theSign * n), 1)
    }

    if 1 - maxError < value {
        return (Int(theSign * (n + 1)), 1)
    }

    // The lower fraction is 0/1
    var lowerN: Double = 0
    var lowerD: Double = 1

    // The upper fraction is 1/1
    var upperN: Double = 1
    var upperD: Double = 1

    while true {
        // The middle fraction is (lowerN + upperN) / (lowerD + upperD)
        let middleN = lowerN + upperN
        let middleD = lowerD + upperD

        if middleD * (value + maxError) < middleN {
            // real + error < middle : middle is our new upper
            upperN = middleN
            upperD = middleD
        } else if middleN < (value - maxError) * middleD {
            // middle < real - error : middle is our new lower
            lowerN = middleN
            lowerD = middleD
        } else {
            // Middle is our best fraction
            return (Int(n * middleD + middleN * theSign), Int(middleD))
        }
    }
}

Answer 8

Простое решение / разбивка повторяющихся десятичных.

Я понял, что числа 1-9, разделенные на 9, повторяются. АКА 7/9 = .77777

Мое решение состоит в том, чтобы умножить все число на 9, добавить повторяющееся число, а затем снова разделить на 9.

    Ex: 28.66666
    28*9=252
    252+6=258
    258/9=28.66666

Этот метод довольно прост в программировании. Сократить десятичную цифру, умножить на 9, добавить сначала десятичную, а затем разделить на 9.

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

Answer 9

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

    public static string toFraction(string exp) {
        double x = Convert.ToDouble(exp);
        int sign = (Math.Abs(x) == x) ? 1 : -1;
        x = Math.Abs(x);
        int n = (int)x; // integer part
        x -= n; // fractional part
        int mult, nm, dm;
        int decCount = 0;

        Match m = Regex.Match(Convert.ToString(x), @"([0-9]+?)\1+.?$");
        // repeating fraction
        if (m.Success) {
            m = Regex.Match(m.Value, @"([0-9]+?)(?=\1)");
            mult = (int)Math.Pow(10, m.Length);

            // We have our basic fraction
            nm = (int)Math.Round(((x * mult) - x));
            dm = mult - 1;
        }
        // get the number of decimal places
        else {
            double t = x;
            while (t != 0) {
                decCount++;
                t *= 10;
                t -= (int)t;
            }
            mult = (int)Math.Pow(10, decCount);

            // We have our basic fraction
            nm = (int)((x * mult));
            dm = mult;
        }
        // can't be simplified
        if (nm < 0 || dm < 0) return exp;

        //Simplify
        Stack factors = new Stack();
        for (int i = 2; i < nm + 1; i++) {
            if (nm % i == 0) factors.Push(i);  // i is a factor of the numerator
        }
        // check against the denominator, stopping at the highest match
        while(factors.Count != 0) {
            // we have a common factor
            if (dm % (int)factors.Peek() == 0) {
                int f = (int)factors.Pop();
                nm /= f;
                dm /= f;
                break;
            }
            else factors.Pop();
        }
        nm += (n * dm);
        nm *= sign;
        if (dm == 1) return Convert.ToString(nm);
        else return Convert.ToString(nm) + "/" + Convert.ToString(dm);
    }

Answer 10

Здесь вы можете использовать метод для преобразования десятичной дроби в дробные:

/// <summary>
    /// Converts Decimals into Fractions.
    /// </summary>
    /// <param name="value">Decimal value</param>
    /// <returns>Fraction in string type</returns>
    public string DecimalToFraction(double value)
    {
        string result;
        double numerator, realValue = value;
        int num, den, decimals, length;
        num = (int)value;
        value = value - num;
        value = Math.Round(value, 5);
        length = value.ToString().Length;
        decimals = length - 2;
        numerator = value;
        for (int i = 0; i < decimals; i++)
        {
            if (realValue < 1)
            {
                numerator = numerator * 10;
            }
            else
            {
                realValue = realValue * 10;
                numerator = realValue;
            }
        }
        den = length - 2;
        string ten = "1";
        for (int i = 0; i < den; i++)
        {
            ten = ten + "0";
        }
        den = int.Parse(ten);
        num = (int)numerator;
        result = SimplifiedFractions(num, den);
        return result;
    }

    /// <summary>
    /// Converts Fractions into Simplest form.
    /// </summary>
    /// <param name="num">Numerator</param>
    /// <param name="den">Denominator</param>
    /// <returns>Simplest Fractions in string type</returns>
    string SimplifiedFractions(int num, int den)
    {
        int remNum, remDen, counter;
        if (num > den)
        {
            counter = den;
        }
        else
        {
            counter = num;
        }
        for (int i = 2; i <= counter; i++)
        {
            remNum = num % i;
            if (remNum == 0)
            {
                remDen = den % i;
                if (remDen == 0)
                {
                    num = num / i;
                    den = den / i;
                    i--;
                }
            }
        }
        return num.ToString() + "/" + den.ToString();
    }
}