将分数转换为连分数

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]

将分数转换为连分数

Convert fraction to continued fraction

python

fractions

continued-fractions