连分数

连分数学习笔记

记号约定

连分数可以将实数通过有理数列的极限刻画，同时给出最佳逼近，它本身只是一个形式记号。

通常用记号 描述一个连分数，它就等于

在数论中，我们通常只考虑项都是整数的情况，更具体地，我们规定 而对于 均有 ，此时连分数叫做简单连分数，简称连分数。

下文中，我们默认连分数指“简单连分数”。

当然，当我们要刻画的不是有理数时，连分数必然会有无穷项，自然地，无穷项的连分数表示的是项数趋于无穷时，连分数的极限，即

连分数有意义当且仅当对应的极限有意义，可以证明，简单连分数必然有意义。

称作 的第 个渐进分数， 称为第 个余项。

有理数的连分数表示

有理数的连分数表示不唯一（有两种表示），区别在于是否强制规定最后一项为 ，例如

也即

其中末项为 的称为标准表示，否则为非标准表示。

求有理数的连分数表示

在求 的连分数表示时，我们尝试依次确定 ，显然 ，因此 是必须的，于是剩余部分 就应该是 的连分数表示，递归下去，直到 是整数。

更形式化地，设第 个余项 ，那么 ，，这是辗转相除的形式，直到 ，时间复杂度

def f(p, q): # 返回 p/q 的连分数的序列表示
    ans = []
    while q:
        ans.append(p // q)
        p, q = q, p % q
    return ans

求连分数的值

有了有理数到连分数的转换方式之后，我们还可能需要将连分数的值求出来。对于有理数，我们当然可以从末项开始倒推，但这种方法存在一个缺陷：当连分数对应值是无理数时，我们每多添一项，就要重新算整个连分数的值，于是我们转而寻求一个顺序递推求值的算法。

对于连分数 ，设其第 个渐进分数为 ，那么有递推公式

递推起点为两个形式分数

证明

设

其中多元函数 会给出第 个渐进分数既约形式的分子和分母，有显然的递归形式

为什么我们可以钦定同样的函数 总会给出既约后的分子呢？根据上面的表示归纳即可，更具体地：

显然， 与 既约。归纳，假设 与 既约，那么

直接对应地设

它们一定既约（否则 与 不既约），证毕。

注意，在证明的过程中，我们同时给出了 的递推关系：

可以写作行列式的形式：

上面的递推实际上就是将它按照第一列展开的结果。现在我们想要保留前面 项，因此按照最后一行展开，得到另一个递推：

这就是我们要的结果。

组合意义证明

回到上一个证明中关键的一个递推式

如何通过它得到“从前往后”的递推公式呢？给 指定一个组合意义：考虑一个 的棋盘，你可以在棋盘上放置 的砖块或者 的砖块，其中 的砖块可以叠放起来而 的砖块上下不能有任何其它砖块；限制为第 个位置的高度不超过 （下标从 开始），求棋盘的每个位置均不空的放置方案数，将它记作 。

考虑第 个位置放置哪种砖块，立即得到递推

这就是最开始的递推，显然还可以考虑最后一个位置的放置方案，得到递推

这就是我们要的递推。

def f(r): # 返回连分数序列 r 对应的既约渐进分数序列
    p = [0, 1]
    q = [1, 0]
    for a in r:
        p.append(a * p[-1] + p[-2])
        q.append(a * q[-1] + q[-2])
    return p, q

参考资料

OI-Wiki

Matrix67的博客