Перевести дробь в непрерывную дробь

Question

Как мне преобразовать дробь в непрерывную дробь в Python? Я попытался осмотреться и обнаружил, что люди, использующие модуль Fraction, делают что-то похожее на мою проблему, но мне не удалось их изменить. Пример с изображением, которое я нашел:

Так что, если вход 181 101тогда вывод должен быть 1 1 3 1 4 4, Спасибо вперед!

Answer 1

Хорошо, давайте начнем с математики. Смысл этого прост. Для дроби n / d евклидово деление равно n = d * q + r с r

У нас просто n/d = (d * q + r) / d = q + r/d с r

Теперь мы итерируем с 1/(r/d) = d/r, чтобы получить вашу продолженную дробь

Это приведет к завершенной последовательности q, потому что знаменатель последовательности дробей представляет собой строго убывающую целочисленную последовательность, которая достигнет 0 в большинстве d операций.

Возможная реализация Python может быть:

def cf(n, d):
    """Return the terms of the continued fraction when n is the numerator
and d the divisor as a list"""
    if d == 0: return []         # Ok it is finished
    q = n//d                     # compute the integer quotient
    r = n - q*d                  # the rest
    return [q] + cf(d, r)        # and recurse...

Получаем как и ожидалось:

>>> cf(181, 101)
[1, 1, 3, 1, 4, 4]

Answer 2

Подобно ответу Сержа, мы можем написать итеративную версию (Python3):

def cf(n, d):
    res = []
    q, r = divmod(n, d)
    while r != 0:
        res = res + [q]
        q, r = divmod(d, r)
        d = (d-r)//q
    return res + [q]