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 with r < d

1/(r/d) = d/r で反復して、連分数を取得します。

分数列の分母は、最大 d 回の操作で 0 に達する厳密に減少する整数列を構成するため、これは q の完成した列につながります。

可能な 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]