Stern-Brocot 树与 Farey 序列
Stern-Brocot 树¶
Stern-Brocot 树是一种维护分数的优雅的结构。它分别由 Moritz Stern 在 1858 年和 Achille Brocot 在 1861 年发现这个结构。
概述¶
Stern-Borcot 树从两个简单的分数开始:
这个
每次我们在相邻的两个分数
既然我们称它为 Stern-Brocot 树,那么它总得有一个树的样子对吧。来一张图:
你可以把第
性质¶
接下来讨论一下 Stern-Brocot 树的性质。
单调性¶
在每一层的序列中,真分数是单调递增的。
略证:只需要在
就行了。这个很容易,直接做一下代数变换即可
另一边同理可证。
最简性¶
序列中的分数(除了
略证:为证明最简性,我们首先证明对于序列中连续的两个分数
显然,我们只需要在
后半部分同理。证明了这个,利用扩展欧几里德定理,如果上述方程有解,显然
有了上面的证明,我们可以证明
有了这两个性质,你就可以把它当成一棵平衡树来做了。建立和查询就向平衡树一样做就行了。
实现¶
构建实现
1 2 3 4 5 6 7 | void build(int a = 0, int b = 1, int c = 1, int d = 0, int level = 1) {
int x = a + c, y = b + d;
// ... output the current fraction x/y
// at the current level in the tree
build(a, b, x, y, level + 1);
build(x, y, c, d, level + 1);
}
|
查询实现
1 2 3 4 5 6 7 8 | string find(int x, int y, int a = 0, int b = 1, int c = 1, int d = 0) {
int m = a + c, n = b + d;
if (x == m && y == n) return "";
if (x * n < y * m)
return 'L' + find(x, y, a, b, m, n);
else
return 'R' + find(x, y, m, n, c, d);
}
|
Farey 序列¶
Stern-Brocot 树与 Farey 序列有着极其相似的特征。第
显然,上述构建 Stern-Brocot 树的算法同样适用于构建 Farey 序列。因为 Stern-Brocot 树中的数是最简分数,因此在边界条件(分母)稍微修改一下就可以形成构造 Farey 序列的代码。你可以认为 Farey 序列
Farey 序列同样满足最简性和单调性,并且满足一个与 Stern-Brocot 树相似的性质:对于序列中连续的三个数
由 Farey 序列的定义,我们可以得到
本页面主要译自博文 Дерево Штерна-Броко. Ряд Фарея 与其英文翻译版 The Stern-Brocot Tree and Farey Sequences。其中俄文版版权协议为 Public Domain + Leave a Link;英文版版权协议为 CC-BY-SA 4.0。
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用