Я пытаюсь найти эффективный алгоритм в Java, чтобы найти повторяющуюся десятичную часть двух целых чисел a
и b
где a/b
.
например. 5/7 = 0,714258 714258 ....
В настоящее время я знаю только метод длинного деления.
algorithms
math
Июнь хао
источник
источник
Ответы:
Я полагаю, что здесь есть два основных подхода: вы можете «грубой силой» искать самую длинную повторяющуюся строку или решить ее как проблему теории чисел.
Прошло много времени с тех пор, как я сталкивался с этой проблемой, но особый случай (1 / n) - это проблема № 26 в Project Euler, поэтому вы можете найти больше информации, найдя эффективные решения для этого конкретного имени. Один поиск приводит нас к веб-сайту Эли Бендерски, где он объясняет свое решение . Вот некоторые из теории на странице десятичных расширений Mathworld :
Моя теория чисел в настоящее время немного заржавела, поэтому лучшее, что я могу сделать, это указать вам в этом направлении.
источник
Давай
n < d
, а ты пытаешься выяснить повторяющуюся частьn/d
. Позвольтеp
быть количество цифр в повторяющейся части: затемn/d = R * 10^(-p) + R * 10^(-2p) + ... = R * ((10^-p)^1 + (10^-p)^2 + ...)
. Часть в скобках представляет собой геометрический ряд, равный1/(10^p - 1)
.Так
n / d = R / (10^p - 1)
. Переставь, чтобы получитьR = n * (10^p - 1) / d
. Чтобы найти R, сделайте циклp
от 1 до бесконечности и остановитесь, как толькоd
делится равномерноn * (10^p - 1)
.Вот реализация в Python:
(
k
отслеживает длину повторяющейся последовательности, чтобы вы могли различать, например, от 1/9 до 1/99)Обратите внимание, что эта реализация (по иронии судьбы) зацикливается навсегда, если десятичное расширение конечно, но завершается, если оно бесконечно! Вы можете проверить этот случай, хотя, потому что
n/d
будет иметь конечное десятичное представление, только если все основные факторыd
этого не 2 или 5 присутствуют вn
.источник
0.123123... = 123/999
0.714258714258... = 714258/999999 (=5/7)
и т. Д.Длинное деление? : /
Превратите результат в строку, а затем примените этот алгоритм к нему. Используйте BigDecimal, если ваша строка недостаточно длинна для обычных типов.
источник