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

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

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

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

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

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

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

Вот предложение: предположим, что ваша начальная фракция равна p/q.

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

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

3. Вычислить НОД (наибольший общий знаменатель) x и 10000: s = НОД(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) и принятие его, если одно из них является однозначным значением, прежде чем переходить к этому методу)

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

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)

удачи!