Допустим, у нас есть 0.33
, нам нужно вывести 1/3
.
Если есть 0.4
, нам нужно вывести 2/5
.
Идея состоит в том, чтобы сделать его удобочитаемым, чтобы пользователь понимал « x частей из y » как лучший способ понимания данных.
Я знаю, что проценты - хорошая замена, но мне было интересно, есть ли простой способ сделать это?
algorithm
language-agnostic
numbers
Swaroop CH
источник
источник
.33
=>"1/3"
пример касается меня; Я ожидал.33
=>"33/100"
. Я полагаю, вы имели.33...
в виду, конечно, но это выявляет проблему с вопросом - прежде чем мы сможем выбрать алгоритм, нам нужно определиться с ожидаемым поведением. В ответе Python @ Debilski используется.limit_denominator()
максимальный знаменатель по умолчанию 10 ^ 7; вероятно, это хорошее значение по умолчанию на практике, но это все равно может привести к ошибкам, если вы не будете осторожны, и в случае возврата действительно вернется ."33/100"
.33
Ответы:
Я обнаружил, что рациональное приближение Дэвида Эппштейна к заданному реальному числовому коду C - это именно то, что вы просите. Он основан на теории непрерывных дробей и очень быстрый и довольно компактный.
Я использовал версии, настроенные для определенных ограничений числителя и знаменателя.
источник
Начиная с Python 2.6 есть
fractions
модуль.(Цитата из документов.)
источник
language agnostic
иalgorithm
тегов удовлетворяет ваш ответ?Если вывод должен дать читателю быстрое представление о порядке результата, нет смысла возвращать что-то вроде «113/211», поэтому вывод должен ограничиваться использованием однозначных чисел (и, возможно, 1 / 10 и 9/10). Если это так, вы можете заметить, что существует всего 27 различных фракций.
Поскольку лежащая в основе математика для генерации вывода никогда не изменится, решением может быть просто жестко закодировать двоичное дерево поиска, чтобы функция выполняла не более log (27) ~ = 4 3/4 сравнений. Вот протестированная версия кода на C
источник
1/1000
он также очень удобочитаем, но приведенный выше алгоритм дает только очень грубое1/10
приближение; Я считаю , что можно улучшить с точки зрения которых по- человечески читаемых знаменатели можно выбрать из, и / или добавление<
,>
,<<
,>>
префиксы , чтобы дать представление о грубости приближения.Вот ссылка, объясняющая математику преобразования десятичной дроби в дробь:
http://www.webmath.com/dec2fract.html
А вот пример функции, как это сделать с помощью VB (с www.freevbcode.com/ShowCode.asp?ID=582):
(Из результатов поиска Google: преобразование десятичного числа в дробное, преобразование десятичного в дробный код)
источник
Возможно, вы захотите прочитать « Что должен знать каждый компьютерный ученый об арифметике с плавающей запятой» .
Вам нужно будет указать некоторую точность, умножив на большое число:
тогда вы можете сделать дробь:
и уменьшить через GCD ...
но нет никакого способа получить намеченную фракцию. Вместо этого вы можете всегда использовать дроби во всем коде - просто не забывайте сокращать дроби, когда это возможно, чтобы избежать переполнения!
источник
Вот версии Perl и Javascript кода VB, предложенные devinmoore:
Perl:
И почти идентичный javascript:
источник
Реализация AC #
источник
Штерна-Броко Дерево вызывает довольно естественным образом аппроксимировать действительные числа дробями с простыми знаменателями.
источник
Отчасти проблема в том, что такое количество дробей на самом деле нелегко интерпретировать как дроби. Например, 0,33 - это не 1/3, а 33/100. Но если вы помните свое обучение в начальной школе, то есть процесс преобразования десятичных значений в дроби, однако он вряд ли даст вам то, что вы хотите, поскольку в большинстве случаев десятичные числа хранятся не как 0,33, а как 0,329999999999998 или что-то в этом роде.
Сделайте себе одолжение и не беспокойтесь об этом, но если вам нужно, вы можете сделать следующее:
Умножьте исходное значение на 10, пока не удалите дробную часть. Сохраните это число и используйте его как делитель. Затем выполните ряд упрощений, ища общие знаменатели.
Таким образом, 0,4 будет 4/10. Затем вы должны искать общие делители, начиная с малых значений, возможно, простых чисел. Начиная с 2, вы увидите, делит ли 2 и числитель, и знаменатель равномерно, проверив, совпадает ли нижний предел деления с самим делением.
Таким образом, 5 не делит 2 равномерно. Затем вы проверяете следующее число, скажем 3. Вы делаете это до тех пор, пока не достигнете квадратного корня меньшего числа или больше.
После того, как вы это сделаете, вам понадобится
источник
Это не «алгоритм», а просто решение Python: http://docs.python.org/library/fractions.html
источник
«Допустим, у нас есть 0,33, нам нужно вывести« 1/3 ».»
Какую точность вы ожидаете от "решения"? 0,33 не равно 1/3. Как распознать «хороший» (легко читаемый) ответ?
Несмотря ни на что, возможный алгоритм может быть:
Если вы ожидаете найти ближайшую дробь в форме X / Y, где Y меньше 10, то вы можете выполнить цикл по всем 9 возможным Y, для каждого Y вычислить X, а затем выбрать наиболее точную.
источник
Я думаю, что лучший способ сделать это - сначала преобразовать значение с плавающей запятой в представление ascii. В C ++ вы можете использовать ostringstream или в C, вы можете использовать sprintf. Вот как это будет выглядеть на C ++:
Аналогичный подход можно было бы применить в прямом C.
После этого вам нужно будет проверить, является ли дробь наименьшей величиной. Этот алгоритм даст точный ответ, т.е. 0,33 выдаст «33/100», а не «1/3». Однако 0,4 даст «4/10», что при сокращении до наименьшего значения будет «2/5». Возможно, это не так мощно, как решение EppStein, но я считаю, что это более просто.
источник
Встроенное решение на R:
При этом используется метод непрерывного дроби и имеет факультативный
cycles
иmax.denominator
аргументы для регулировки точности.источник
library(numbers)
иcontFrac(0.6666)
; чтобы получить желаемую строку:paste(contFrac(0.666, tol=1e-03)$rat, collapse="/")
Вам нужно будет выяснить, какой уровень ошибки вы готовы принять. Не все десятичные дроби сводятся к простой дроби. Я бы, вероятно, выбрал легко делимое число, например 60, и выяснил, сколько 60-х ближе всего к значению, а затем упростил дробь.
источник
Вы можете сделать это на любом языке программирования, выполнив следующие действия:
Пример: 0,2 = 0,2 x 10 ^ 1/10 ^ 1 = 2/10 = 1/5.
Итак, это можно прочитать как «1 часть из 5».
источник
Одно из решений - просто хранить все числа как рациональные числа. Существуют библиотеки для арифметики рациональных чисел (например, GMP ). При использовании объектно-ориентированного языка вы можете просто использовать библиотеку классов рациональных чисел, чтобы заменить свой числовой класс.
Финансовые программы, среди прочего, будут использовать такое решение, чтобы иметь возможность производить точные вычисления и сохранять точность, которая может быть потеряна при использовании простого поплавка.
Конечно, это будет намного медленнее, поэтому это может оказаться непрактичным для вас. Зависит от того, сколько вычислений вам нужно сделать, и насколько важна для вас точность.
источник
В общем случае это неправильно, потому что 1/3 = 0,3333333 = 0. (3) Более того, из предложенных выше решений невозможно выяснить, можно ли десятичное число преобразовать в дробь с определенной точностью, потому что вывод всегда дробный.
НО, я предлагаю свою комплексную функцию с множеством опций, основанных на идее бесконечных геометрических рядов , в частности, на формуле:
Сначала эта функция пытается найти период дроби в строковом представлении. После этого применяется описанная выше формула.
Код рациональных чисел заимствован из реализации рациональных чисел Стивена М. МакКейми на C #. Надеюсь, перенести мой код на другие языки не так уж и сложно.
Вот несколько примеров использования:
Ваш случай с обрезкой нулевой части правой части:
Мин. Период демонстрации:
Округление в конце:
Самый интересный случай:
Остальные тесты и код каждый может найти в моей библиотеке MathFunctions на github .
источник
У Ruby уже есть встроенное решение:
В Rails числовые атрибуты ActiveRecord также могут быть преобразованы:
источник
Ответьте на C ++, предполагая, что у вас есть класс BigInt, который может хранить целые числа неограниченного размера.
Вместо этого вы можете использовать unsigned long long, но это будет работать только для определенных значений.
Кстати, GetRational (0.0) вернет «+0/1», так что вы можете захотеть обработать этот случай отдельно.
PS: Я использую этот код в своем собственном классе RationalNum в течение нескольких лет, и он был тщательно протестирован.
источник
while
цикла ограничен размеромdouble
, который обычно составляет 64 бита. Таким образом, это не зависит от начального значения input (val
). ОднакоGCD
функция действительно зависит от этого значения, хотя обычно довольно быстро сходится к решению. Возможно ли, что вы неправильно реализовали эту функцию?unsigned long long
вместоBigInt
, то это не обязательно даст правильный результат для каждого входного значения ... Но даже в этом сценарии код не предполагается «зайти в очень длинный цикл».GCD
функция не реализована должным образом. Вы проверяли, работает ли код долго во времяwhile
цикла или после него? Я проверю значение 1,33333, чтобы увидеть, что за этим стоит. Спасибо.Этот алгоритм Иэна Ричардса / Джона Кеннеди не только возвращает хорошие дроби, но и очень хорошо работает с точки зрения скорости. Это код C #, взятый из этого ответа .
Он может обрабатывать все
double
значения, кроме специальных значений, таких как NaN и +/- бесконечность, которые вам придется добавить при необходимости.Он возвращает
new Fraction(numerator, denominator)
. Замените на свой собственный.Дополнительные примеры значений и сравнение с другими алгоритмами см. Здесь
Примеры значений, возвращаемых этим алгоритмом:
источник
У вас будут две основные проблемы, которые сделают это трудным:
1) Плавающая точка не является точным представлением, что означает, что если у вас есть дробная часть «x / y», которая дает значение «z», ваш алгоритм дроби может вернуть результат, отличный от «x / y».
2) В бесконечности иррациональных чисел намного больше, чем рациональных. Рациональное число - это число, которое можно представить в виде дроби. Нерациональные существа, которые не могут.
Однако дешевым способом, поскольку точность с плавающей запятой ограничена, вы всегда можете представить ее как некую форму фракции. (Думаю...)
источник
Завершил приведенный выше код и преобразовал его в as3
источник
Вот быстрая и грязная реализация на javascript, которая использует подход грубой силы. Совсем не оптимизирован, он работает с заранее определенным диапазоном фракций: http://jsfiddle.net/PdL23/1/
Это вдохновлено подходом, используемым JPS.
источник
Как утверждали многие люди, вы действительно не можете преобразовать числа с плавающей запятой обратно в дробь (если только она не очень точна, например, 0,25). Конечно, вы можете создать какой-то поиск для большого массива дробей и использовать какую-то нечеткую логику для получения желаемого результата. Опять же, это не будет точно, и вам нужно будет определить нижнюю границу того, насколько большим должен быть знаменатель.
.32 <x <.34 = 1/3 или что-то в этом роде.
источник
Вот реализация для рубина http://github.com/valodzka/frac
источник
Я наткнулся на особенно элегантное решение Haskell, использующее анаморфизм. Это зависит от пакета рекурсивных схем .
Если вы попробуете это в ghci, это действительно сработает!
источник