一、 基础：
如图即为一棵Stern-Brocot树。
Stern-Brocot树第N排的真分数部分即为N阶Farey序。
1.对于每次在m1/n1,m2/n2中插入(m1+m2)/(n1+n2)构成下一排。
2.对于任意一个Farey序中连续的分数m1/n1,m2/n2，必有m1/n1<m2/n2。
3.Stern-Brocot树可以构成所有有理数。
4.Stern-Brocot树构成的所有分数均为最简分数，即gcd(m,n)==1。
5.任意两个构造时相邻的两个分数都满足m1n2-m2n1==1。
二．N阶Farey序列的构造。 1.递归构造。 依靠m1/n1, (m1+m2)/(n1+n2),m2/n2的法则递归构造。具体构造法如下：
|
1 2 3 4 5 6 7 8 9 10 |
void build(int m1,int n1,int m2,int n2) { if(m1+m2>n||n1+n2>n) return; build(m1,n1,m1+m2,n1+n2); top++; stack[top].a=m1+m2; stack[top].b=n1+n2; //如果是指定第k小的不可约分数，可以加上这一句小小优化一下 if(top>k) return; build(m1+m2,n1+n2,m2,n2); } |
时间复杂度O(N^2)，空间复杂度O(N)
2.非递归构造。
对于任意N阶Farey序列中连续的三个分数m1/n1,m2/n2,m3/n3,必有：
m3=[(n1+N)/n2]m2-m1
n3=[(n1+N)/n2]n2-n1;
注：[a]表示a向下取整。
证明：
由于这三个分数在该序列中连续存在，所以n1+n2>N,m1+m2>N。
N=((n1+N)/n2)n2-n1>=n3>N-n2=((n1+N)/n2-1)n2-n1n3=[(n1+N)/n2]n2-n
又n2m3-m2n3=1，
得 m3=(m2n3+1)/n2=(([(n1+N)/n2]n2-n1)m2+1)/n2
所以m3=[(n1+N)/n2]m2-(n1m2-1)/n2=[(n1+N)/n2]m2-m1
得证。
三． 求N阶Farey序列的第k个最小分数。
1. 按照递归构造方法，构造Stern-Brocot树，适用于要求求出1阶2阶…N阶。
注意，当N过大时，需要手写模拟栈完成。
2.按照非递归构造方法，第一项是0/1,第二项是1/N,然后递推构造，适用于单求第N阶Farey序列。
.jpg)
.jpg)