Учитывая десятичное число, найдите наименьший целочисленный множитель, который дает целочисленный результат

Question

Лучше всего использовать пример для описания проблемы. Допустим, у меня есть десятичное значение 100.227273.

100.227273 * X = Y

Мне нужно найти наименьшее положительное целое число X, которое дает целое число Y.

Answer 1

Если 100.227273 - это только приближение, и вы хотите получить наилучшее рациональное приближение, используйте непрерывные дроби .

В качестве примера возьмите 100,227273.

1. Уберите целую часть (100). Теперь вы получите 100,227273 = 100 + 0,227273.
2. Инвертируйте 0.227273, чтобы получить 4.39999 (4.4?).
3. Повторяйте шаг 1, пока не будете удовлетворены ошибкой.

Итак, вы получите

                       1
100.227273 = 100 + —————————
                         1
                   4 + —————
                           1
                       2 + —
                           2

Упростите это выражение, чтобы получить 2205 / 22.

[Примечание редактора: пример кода см. в этом ответе .]

Answer 2

1000000/gcd(1000000,227273). Также известный как lcm(1000000,227273)/227273. В этом случае 1 млн.

То, что вы хотите сделать, это превратить 0.227273 в дробь в простейшей форме. Число, которое вы ищете, является знаменателем этой дроби. Поскольку 227273/1000000 уже в простейшей форме, все готово. Но если ваш ввод был 100.075, то 75/1000 не в простейшей форме. Самая простая форма - 3/40, поэтому решение для X - 40.

В качестве оптимизации вы можете упростить вычисление, поскольку знаете, что начальный знаменатель является степенью 10, поэтому его единственные простые множители равны 2 и 5. Поэтому все, что вам нужно искать в числителе, - это делимость на 2 и 5, что проще, чем алгоритм Евклида. Конечно, если у вас уже есть реализация gcd и / или lcm, то это больше усилий с вашей стороны, а не меньше.

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

Если у вас есть число как частное во-первых, то вам нужно найти знаменатель его простейшей формы напрямую, а не преобразовывать его в десятичную форму и усекать ее. Например, чтобы решить эту проблему для числа «6 и одна треть», ответ равен 3, а не любой степени 10. Если на входе «квадратный корень из 2», то для X нет решения.

Ну, на самом деле, наименьшее целое число X с требуемым свойством равно 0, но я предполагаю, что вы не это имеете ввиду; -)

Answer 3

У меня такое ощущение, что вы на самом деле имеете в виду это:
Как преобразовать числа с плавающей точкой в ​​читаемые человеком фракции?

Answer 4

Я предполагаю, что входное десятичное число r является положительным рациональным числом r с завершающим десятичным представлением.

Пусть d будет количеством цифр после десятичной точки (предположим, что мы обрезали все посторонние нули из десятичного представления r). Затем обратите внимание, что 10^d * r является целым числом m. Пусть g = gcd(10^d, m). Тогда 10^d / g * r = m / g является целым числом p. Пусть q = 10^d / g. Я утверждаю, что q является наименьшим таким положительным целым числом.

Answer 5

Если положительное десятичное значение D имеет n цифр справа от десятичной точки, то D * 10 ^ n является целым числом и X = 10 ^ n / gcf (10 ^ n, D * 10 ^ n) = lcm (10 ^ n, D * 10 ^ n) - наименьшее положительное целое число X.