Stern-Brocot树
我们接着上节课讲到的Stern-Brocot树继续往下讲。
LR序列表示
对于任意分数 
，我们从 
开始走到它所在的结点。如果向左走就记为L，向右走记为R，最终可以得到一个L和R的序列。例如 
的表示就是LRRL。
这种表示产生了两个问题：
1. 给定满足正整数 m 和 n 互素的分数 
，它所对应的LR序列是什么？
2. 给定LR序列，它所表示的分数是什么？
第二个问题看起来更好解决一点，我们先解决第二个问题。
我们定义
例如
如果用代码实现的话，对于每个L或者R，如果是L，那么就把右边界设为中间值，如果是R，那么就把左边界设为中间值。
但是如何用数学式子来表达这一过程呢？
我们建立一个2阶方阵：
表示 
的两个祖先分数
那么初始状态就可以表示为
如果遇到了向左符号L，那么
如果遇到了向右符号R，那么
所以我们将L和R定义成2阶方阵就行了：
所以
所以LRRL表示的分数为
那么第一个问题如何解决呢？
同样可以用类似二叉搜索的方法来求出LR序列，也可以用矩阵的方法来求解，根据上面的L和R的方阵，可以发现：
对于L也有类似的性质，所以我们得到了如下的求解算法：
如果
，输出R，令
。
如果 
，输出L，令 
。
