RU
EN
ES
ZH
FR
DE
PT
AR
HI
question@mail.ru
·
Период десятичной дроби
📁 метод, python, пример
Задача : на вход в функцию подается два целых числа (int(a), int(b)). Вернуть нужно частное a/b , причем повторяющиеся числа (период) нужно взять в скобки.
Примеры:
1/3 = > 0.(3)29/12 = > 2.41(6)5/3 = > 1.(6)Подошел к решению задачи методом брутфорса. Перебирал дробную часть , искал совпадения. Но в случае 1/117 в период входит более 90 чисел и перебор чисел занимает больше времени, чем позволено в задаче.
Как по-другому решить эту задачу? Может есть более элегантное решение?
answer@mail.ru
·
Для поиска периода рационального числа существует отдельный алгоритм. Перебираем одну за другой степени числа 10: 10, 100, 1000, 10000 и т.д. Смотрим на остаток от деления этого числа на знаменатель. Если остаток от деления равняется 1, значит степень числа 10, это длина периода. Например, если в знаменателе стоит 13, то:
10 % 13 = 10100 % 13 = 91000 % 13 = 1210000 % 13 = 3100000 % 13 = 41000000 % 13 = 1Получается, период равен 6. Этот период не зависит от того, что стоит в числителе (если дробь сокращена).
Метод не работает, если знаменатель делится на 5 или 2. В таком случае его нужно делить на 2, или 5, пока получится число, которое не делится на 2, 5.
В общем случае (как для вашего примера 1/117), придется использовать длинную арифметику.
Алгоритм ищет только длину периода, что бы получить сам период, нужно делить самому.
Войдите чтобы оставить ответ
