来源

定义

性质

例程(pascal码 C++码)

来源

约翰·法雷 是英国一位多才多艺的“ 杂家” , 生活在拿破仑时代, 职业是土地丈量员, 却有着广泛的爱好, 喜欢搜集奇异的石头、矿物, 兴致来潮, 撰写小块科普文章在《哲学杂志》上发表, 题材广泛涉及到地质、音乐、钱币、车轮、慧星, 偶尔也涉及数学小品。1816年, 当他审读亨利 戈德温所编的“ 小数商表” 时,忽然有一个问题涌上心头， 既约最简真分数有多少呢能不能把它们按一定的顺序排列出来兴致所及, 急切难忍, 他立即推开戈氏冗繁的“商表” , 动手排列起来, 一遍又一遍, 没有头绪。这时他想到两点：一是真分数有无限多个, 要“ 全部” 排出, 必须限制分母的大小二是可按递增的顺序去排列, 容易发现规律 他终于排出来了, 还发现了若干性质。发表后, 立即被当时数学家们抓住, 后来数学家柯西发现这分数串在数学中很有用,并名之为法雷数列。 没成想早在14年前, 一位名叫哈罗斯的人, 就发现并公布了自己的研究结故。名之哈罗斯一法雷数列。

定义

对任意给定的一个自然数n，将分母小于等于n的不可约的真分数按升序排列，并且在第一个分数之前加上0/1，在最后一个分数之后加上1/1，这个序列称为n级法雷数列，以Fn表示。如F5为：1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5。

性质

1.除了1级法雷数列外，所有的法雷数列都有奇数个元素，其中居于正中间的那个元素一定是1/2.

2. 当n趋于正无穷时，n级法雷数列包含的元素的个数趋于3/(π*π) * n2 ≈ 0.30396355 * n2.

3. n级法雷数列中，若相邻两个元素是a/b 和c/d (a/b<c/d),则这两个数的差为1/bd, 这个差的最小值为1/(n*(n-1)), 最大值为1/n, 在法雷数列的第一个元素（0/1）与其后继以及最后一个元素（1/1）与前驱之间的差取到最大值，而正中间的那个元素1/2 与其前驱和后继元素之间的差取次大值1/(n*2).

实数化分数方法

对于有理数0，我们可以用0/1表示；对于有理数x<0, 总可以表示为–(p/q), 其中p>0,q>0；而对于所有大于等于1的正有理数，总可以表示为n + p/q ( n, p, q为非负整数，q!=1, p<q)的形式, 以分数形式可表示为(nq + p) /q。因此，转化小于1的正有理数为分数是实数转化为分数的基本问题。由于无理数不能用一个分数来准确的表示，因此，我们可用两个分数a/b, c/d 来逼近这个实数，使得无理数f >= a/b且f<=c/d，a/b称为实数f的下界，c/d称为实数f的上界，求这个下界和上界实际上是找出一个n级法雷数列中两个相邻的元素。下面是化一个小于1的正实数为分数的算法。

Step1: 置实数f 的下界为a/b=0/1, 上界为c/d =1/1。

Step2: 计算出下界和上界之间的数p/q = (a+c)/(b+d)

Step3: 若q>n(分母大于指定值），计算中止。

若p/q =f，a/b ßp/q , c/d ßp/q, 计算中止。

若p/q > f, 置下界a/b为p/q

若p/q< f, 置上界c/d为p/q

Step4, 重复step 2-3

当计算终止时，a/b为这个实数的下界，c/d为这个实数的上界。

如果要转化的实数f小于1/2, 用上述逐步求精的步骤，计算出上下界，迭代次数稍多。我们可用下面的步骤代替step1, 直接找出一个更精确的上下界。

若e= 1/x 的向下取整，则这个实数的下界和上界为1/(e+1)和1/e

误差分析，根据法雷数列性质3我们知道，n级法雷数列中相邻的两个元素可以表示一个区间[a/b, c/d]，前一个元素q/b为区间的下界，后一个元素c/d为区间的上界，这个区间的宽度h =c/d- a/b,满足1/n <= h <1/(n*n-1)。若运气好的话，一个实数正好落在一个宽度为1/n(n-1) 的区间，这个区间的下界或上界与这个实数的差不超过abs(1/(n*(n-1)))。若运气很差，一个实数恰好小于法雷序列的第2个元素或者最后一个元素。则这个元素的下界和上界与这个实数的差不超过1/n。

例程

pascal码

{

PROG: frac1

LANG: PASCAL

}

program frac1;

type node=record

x,y:longint;

d:double;

end;

var n,i,j,len:longint;

sn:array[1..8000]of node;

function gcd(x,y:longint):longint;

begin

if x=0 then gcd:=y

else gcd:=gcd(y mod x,x);

end;

procedure qsort(s,t:longint);

var i,j:longint;

mid:double;

te:node;

begin

i:=s;j:=t;mid:=sn[(s+t)div 2].d;

while i<=j do

begin

while sn[i].d<mid do inc(i);

while sn[j].d>mid do dec(j);

if i<=j then

begin

te:=sn[i];sn[i]:=sn[j];sn[j]:=te;

inc(i);dec(j);

end;

end;

if i<t then qsort(i,t);

if s<j then qsort(s,j);

end;

begin

// while not eof do begin

read(n);

sn[1].x:=0;sn[1].y:=1;sn[1].d:=0.0;

sn[2].x:=1;sn[2].y:=1;sn[2].d:=1.0;

len:=2;

for i:=2 to n do

for j:=1 to i-1 do

if gcd(i,j)=1 then //判断是否是真约数

begin

inc(len);

sn[len].x:=j;sn[len].y:=i;sn[len].d:=j/i;

end;

qsort(1,len);

for i:=1 to len do

writeln(sn[i].x,'/',sn[i].y);

//end;

close(input);close(output);

end.

C++码

#include<cstdio>

using namespace std;

long n;

void dfs(long x1,long y1,long x2,long y2){

if(y1+y2<=n){

dfs(x1,y1,x1+x2,y1+y2);

printf("%d/%d\",x1+x2,y1+y2);

dfs(x1+x2,y1+y2,x2,y2);

}

}

int main()

{

scanf("%d",&n);

printf("0/1\");

dfs(0,1,1,1);

printf("1/1\");

return 0;

}