【Farely序列与Stern-Brocot树】

一、 基础:

如图即为一棵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的法则递归构造。具体构造法如下:

时间复杂度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序列。

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*