Учитывая десятичное число, найдите самый маленький целочисленный множитель, который дает целочисленный результат
Лучше всего использовать пример для описания проблемы. Позволяет говорят, что у меня есть десятичное значение 100.227273.
100.227273 * X = Y
Я должен найти самое маленькое положительное целое число X, который дает целое число Y.
5 ответов
Если 100.227273 - это просто приближение, и вы хотите получить лучшее рациональное приближение, используйте продолженные дроби.
Возьмем в качестве примера 100.227273.
- Отнимите целую часть (100). Теперь вы получите 100.227273 = 100 + 0.227273.
- Инвертируйте 0,227273, чтобы получить 4,39999 (4,4?).
- Повторяйте шаг 1, пока вас не устроит ошибка.
Таким образом, вы получите
1
100.227273 = 100 + —————————
1
4 + —————
1
2 + —
2
Упростите это выражение, чтобы получить 2205/22.
[Примечание редактора: пример кода см. в этом ответе.]
Я предполагаю, что входное десятичное число 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 - наименьшее такое положительное целое число.
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, но я полагаю, вы не это имеете в виду ;-)
Если ваше положительное десятичное значение D имеет n цифр справа от десятичной точки, то D * 10^n - целое число, а X = 10^n / gcf(10^n, D * 10^n) = lcm(10^n, D * 10^n) - наименьшее положительное целое число X.
У меня такое ощущение, что вы на самом деле имеете в виду следующее:
Как преобразовать числа с плавающей запятой в удобочитаемые дроби?