Период десятичной дроби

#python #алгоритм #оптимизация

Задача : на вход в функцию подается два целых числа (int(a), int(b)). Вернуть нужно
частное a/b , причем повторяющиеся числа (период) нужно взять в скобки.

Примеры:

1/3  = >   0.(3)
29/12 = >  2.41(6)
5/3  = >  1.(6)


Подошел к решению задачи методом брутфорса. Перебирал дробную часть , искал совпадения.
Но в случае 1/117 в период входит более 90 чисел и перебор чисел занимает больше времени,
чем позволено в задаче.

Как по-другому решить эту задачу? Может есть более элегантное решение?
    

Ответы

Ответ 1

Для поиска периода рационального числа существует отдельный алгоритм. Перебираем
одну за другой степени числа 10: 10, 100, 1000, 10000 и т.д. Смотрим на остаток от
деления этого числа на знаменатель. Если остаток от деления равняется 1, значит степень
числа 10, это длина периода. Например, если в знаменателе стоит 13, то:

10 % 13 = 10
100 % 13 = 9
1000 % 13 = 12
10000 % 13 = 3
100000 % 13 = 4
1000000 % 13 = 1


Получается, период равен 6. Этот период не зависит от того, что стоит в числителе
(если дробь сокращена).

Метод не работает, если знаменатель делится на 5 или 2. В таком случае его нужно
делить на 2, или 5, пока получится число, которое не делится на 2, 5.

В общем случае (как для вашего примера 1/117), придется использовать длинную арифметику.

Алгоритм ищет только длину периода, что бы получить сам период, нужно делить самому.


Ответ 2

Я реализовывал в свое время деление в столбик и как только получал ту же пару делимое-делитель
что уже была - считал что нашел период.


Ответ 3

Решение через деление в столбик . Огромное спасибо всем отписавшимся :)

def convert(numerator, denominator):
    ans= str(numerator//denominator)+ "."
    l={}
    index=0
    numerator = numerator%denominator
    l[numerator]=index
    t=False
    while t==False:
        if numerator==0:
            break
        digit = numerator*10//denominator
        numerator=numerator*10-(numerator*10//denominator)*denominator
        if numerator not in l:
            ans+=str(digit) 
            index+=1
            l[numerator]=index
            t=False
        else:
            ans+=str(digit)+")"
            ans=ans[:l.get(numerator)+len(ans[:ans.index(".")+1])]+"("+ ans[l.get(numerator)+len(ans[:ans.index(".")+1]):]
            t=True
    return ans