连分数

$$ \newcommand{\dplus}{\space\underset{+}{}\space} $$

简单连分数

连分数是如下的分数

$$ a_0+\cfrac{1}{a_1+\cfrac{1}{a_2 + \cfrac{1}{\ddots}}} $$

有无限连分数和有限连分数

有限连分数

$$ x=[a_0;a_1,a_2,a_3] $$

$$ x=a_0 + \cfrac{1}{a_1} \dplus \cfrac{1}{a_2} \dplus \cfrac{1}{a_3} $$

无限连分数

$$ x=[a_0;a_1,a_2,a_3,...] = \lim_{n \to \infty} [a_0;a_1,...,a_n] $$

收敛有理分数

$\frac{h_n}{k_n}$是第$n$个收敛分数其中有

$$ \begin{gather*} \frac{h_n}{k_n} = \frac{a_nh_{n-1} + h_{n - 2}}{ a_nk_{n - 1} + k_{n - 2} } \\\\ h_{-1} = 1 \quad h_{-2} = 0 \\ k_{-1} = 0 \quad k_{-2} = 1 \\ \end{gather*} $$

# 求有理分数的连分数

def get_coutinued_fraction(p: int, q: int) -> list[int]:

    res = []

    while q != 0:
        d = p // q      # 商
        r = p - q * d   # 余数

        res.append(d)

        p = q
        q = r

    return res

get_coutinued_fraction(67, 29)

[2, 3, 4, 2]

# 求连分数前n个收敛子

def get_convergent(a: list[int], n: int):

    h = [0 for _ in range(n)]
    k = [0 for _ in range(n)]

    x = [0 for _ in range(n)]

    for i in range(n):

        if i == 0:
            h[i] = a[i]
            k[i] = 1
        elif i == 1:
            h[i] = a[i] * h[i - 1] + 1
            k[i] = a[i] * k[i - 1]
        else:
            h[i] = a[i] * h[i - 1] + h[i - 2]
            k[i] = a[i] * k[i - 1] + k[i - 2]

        x[i] = h[i] / k[i]

    return (h, k, x)
    

# 根号2
import matplotlib.pyplot as plt
import math

a = [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 , 2, 2, 2, 2, 2, 2, 2, 2, 2]

n = len(a)

x = list(range(n))  # x 轴上的值为 0, 1, 2, ..., n-1
y = [math.sqrt(2)] * n         # y 轴上的值都是 2

l1 =plt.scatter(x, y, s=20)

(_, _, x1) = get_convergent(a, n)


l2 = plt.scatter(x, x1, s=10)

plt.title(r'$\sqrt{2}$')
plt.xlabel('n')
plt.ylabel('y')

plt.ylim(0, 3)
plt.legend((l1, l2), (r'$\sqrt{2}$', 'continued_fraction'))

plt.show()

# 自然对数的底数e
import matplotlib.pyplot as plt
import math

a = [2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8 , 1, 1, 10, 1, 1, 12, 1, 1, 14]

n = len(a)

x = list(range(n))  # x 轴上的值为 0, 1, 2, ..., n-1
y = [math.e] * n         # y 轴上的值都是 2

l1 =plt.scatter(x, y, s=20)

(_, _, x1) = get_convergent(a, n)


l2 = plt.scatter(x, x1, s=10)

plt.title(r'$e$')
plt.xlabel('n')
plt.ylabel('y')

plt.ylim(0, 5)
plt.legend((l1, l2), (r'$e$', 'continued_fraction'))

plt.show()