python - 将分数转换为连分数

Question

如何在 Python 中将分数转换为连分数？我试着环顾四周，发现有人使用 Fraction 模块来做与我的问题类似的事情，但我没有设法修改它们。我发现的图像示例：

所以如果输入是181 101，那么输出应该是1 1 3 1 4 4。提前谢谢！

Answer 1

好的，让我们从一些数学开始。这背后的理由很简单。对于分数 n/d，欧几里得除法是 n = d * q + r 其中 r < d

我们只需 n/d = (d * q + r) / d = q + r/d 且 r < d

现在我们用 1/(r/d) = d/r 迭代得到你的连分数

这将导致q的完成序列，因为分数序列的分母构成一个严格递减的整数序列，最多在d次操作中将达到0。

一个可能的 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

类似于 Serge 的回答，我们可以编写一个迭代版本（Python3）：

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