Оптимизированный алгоритм преобразования десятичной дроби в «красивую» дробь - PullRequest
Новая
       20

Оптимизированный алгоритм преобразования десятичной дроби в «красивую» дробь

5 голосов
/ 13 января 2011

Вместо того, чтобы преобразовывать произвольную десятичную дробь в точную дробь (что-то вроде 323527/4362363), я пытаюсь преобразовать в обычные легко различимые (с точки зрения восприятия человеком) величины, такие как 1/2, 1/4,1/8 и т. Д.

Кроме серии сравнений if-then, сравнений и т. Д., Есть ли более оптимизированные методы для этого?

Редактировать: в моем конкретном случае приближения приемлемы.Идея состоит в том, что 0,251243 ~ 0,25 = 1/4 - в моем случае это «достаточно хорошо», причем последний более предпочтителен для удобочитаемости человека с точки зрения быстрого индикатора (не используется для расчета, просто используется в качестве числового значения для отображения).

Ответы [ 5 ]

7 голосов
/ 13 января 2011

Посмотрите "продолжение приближения дроби". В Википедии есть базовое введение в статье «продолжение дроби», но есть оптимизированные алгоритмы, которые генерируют приближенное значение при создании дроби.

Затем выберите остановочную эвристику, комбинацию размера знаменателя и близости аппроксимации, когда вы «достаточно близки».

3 голосов
/ 13 января 2011

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

0 голосов
/ 14 января 2011

Довольно глупое решение, просто для «предварительного просмотра» дроби: 

factor = 1/decimal
result = 1/Round(factor)
mult = 1

while (result = 1) {
  mult = mult * 10
  result = (1 * mult)/(Round(mult * factor))
}

result = simplify_with_GCD(result)

удачи!

0 голосов
/ 13 января 2011

Вот предложение: если исходная доля равна p / q

  1. Рассчитайте r = p / q как рациональное значение (с плавающей запятой) (например, r = float (p) / float (q))

  2. Вычислить округленное десятичное число x = int (10000 * r)

  3. Рассчитать GCD (наибольший общий знаменатель) для x и 10000: s = GCD (x, 10000)

  4. Представьте результат в виде m / n, где m = x / s и n = y / s (ваш пример рассчитывается как 371/5000)

Как правило, все знаменатели из 1000 достаточно читабельны для человека.

Это может не дать наилучшего результата, когда значение ближе к более простым случаям, таким как 1/3. Тем не менее, я лично нахожу 379/1000 гораздо более читабельным, чем 47/62 (что является кратчайшим дробным представлением). Вы можете добавить несколько исключений для точной настройки такого процесса (например, вычисление p / GCD (p, q), q / GCD (p, q) и принятие его, если одно из них представляет собой однозначные значения, прежде чем перейти к этому методу)

0 голосов
/ 13 января 2011

В дальнейшем я собираюсь предположить, что наши десятичные дроби находятся в диапазоне от 0 до 1. Это должно быть просто адаптировать это к большим числам и отрицательным числам.

Вероятно, проще всего было бы выбрать наибольший знаменатель, который вы сочтете приемлемым, и затем создать список дробей от 0 до 1, у которых этот знаменатель меньше или равен им. Обязательно избегайте дробей, которые можно упростить. Очевидно, что после того, как вы перечислили 1/2, вам не нужно 2/4. Вы можете избежать дробей, которые можно упростить, проверив, что GCD числителя и знаменателя 1 соответствует алгоритму Евклида. Как только у вас есть свой список. Оцените их как числа с плавающей точкой (вероятно, удваивается, но тип данных, очевидно, зависит от вашего выбора языка программирования). Затем вставьте их в сбалансированное двоичное дерево поиска, хранящее как исходную дробь, так и оценку дроби с плавающей запятой. Вам нужно сделать это только один раз, чтобы изначально все настроить, чтобы время n * log (n) (где n - количество дробей) было не очень большим.

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

...