Stern-Brocot树及法里级数分析

Stern-Brocot树
产生了所有分子分母互素的分数

从初始0/1 1/0 -> m/n m'/n'出发，不断往中间添加 (m+m')/(n+n')
容易推得 n * m' - m * n' = 1
证:
初始 0/1 1/0 那么1*1-0*0=1
那么假设前一次符合n * m' - m * n' = 1的性质
之后二叉树有两个方向行进，产生两种相邻 (m/n , (m+m')/(n+n')) ((m+m')/(n+n') , m'/n')
-> 左侧n*(m+m') - m*(n+n') = n*m'-m*n'=1
右侧(n+n')*m'-(m+m')*n' = n*m'-m*n = 1
所以总是不断的得到n * m' - m * n' = 1的性质

那么根据扩展欧几里得很容易得到 (n+n') , (m+m') 互质才有解，所以产生的数 (m+m')/(n+n') 必然是分子分母互素的

因为必然有整数解，很容易得知左右连接的两个数 n , n' 互质 , m m'互质 , n m 互质 , n' m'互质

同样因为(n+n')*m'-(m+m')*n' = 1
产生了所有分子分母互素的分数的证明：
m/n < (m+m')/(n+n') < m'/n' -> 这一点保证了Stern-Brocot树产生的分数是有序的
总是在两个合法分数之间产生一个合法分数，也就是说我们需要任何分数，只需要递归判断属于哪个区间，不断往树的那
一侧移动
而且每次往树底移动一步，必然会使分母变大至少1，所以求分母为n的合法分数，至多只需要往树上走n层即可

利用Stern-Brocot树思想求解阶为n的法里级数
法里级数就是表示分母不大于n的所有分数

下面是简单的求出法里级数序列的代码

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#include <queue>

using namespace std;

#define M 26

#define N 500000

#define ull unsigned long long

#define ll long long

const int MOD = ;

int n;

void dfs(int l1 , int l2 , int r1 , int r2) //l1/l2 , r1/r2

{

    if(l2+r2>n) return ;

    //Stern-Brocot树 左侧总是最小的，右侧最大的，那么总是优先输入左侧，再输入中间的，最后输入右侧的数

    dfs(l1 , l2 , l1+r1 , l2+r2);

    cout<<l1+r1<<"/"<<l2+r2<<" ";

    dfs(l1+r1 , l2+r2 , r1 , r2);

}

int main() {

    n = ;

    cout<<"0/1 ";

    dfs( ,  ,  , ); //会按从小到大的次序输出结果

    cout<<"1/1"<<endl;

    return ;

}

Farey series

Stern-Brocot树上节点的表示

我从单位一设为起始点

总是用一个长字符串表示从单位1 (1/1) 开始走的路径

L表示左走， R表示右走，当前位置为S

那么用M(S) = (n n'

　　　　　　　 m m') 的矩阵进行描述

值F(S) = (m+m')/(n+n')

往右走M(SR) = M(S) * M(R) = M(S)*(1 1

　　　　　　　　　　　　　　　　　　 0 1)

往左走M(SL) = M(S) * M(L) = M(S)*(1 0

　　　　　　　　　　　　　　　　　　 1 1)

对于连续的都可以用矩阵快速幂求解

如M(SRRRR) = M(S)*M(R)^4

另外求F(RS) 时可以发现规律是 F(RS) = F(S)+1, F(LS) = F(S)/(F(S)+1)

可以利用矩阵简单求证

Brocot树

Stern-Brocot树 及 法里级数分析

Stern-Brocot树及法里级数分析