学步园

化实数为分数

实数包含有理数和无理数，任何有理数都可以表示为p/q(p,q是整数，q!=0)的形式，如果指定一个分数的分母不超过某个值，对于一般的有理数或者无理数，是不可以用一个分数来准确地表示的。我们这里主要讨论，如何找出一对分数p1/q1和p2/q2,使得q1 和q2 小于给定的值n，而p1/q1和p2/q2尽可能接近一个给定的实数.。为了便于说明，我们用C++语言的格式给出问题的定义：

函数接口void search( int &p1, int &q1, int &p2,int &q2, int n, double f)

功能: 找出一对不可约p1/q1 和p2/q2, 使得这两个分数的分母不大于n, 且p1/q1 <= f <= p2/q2, 且这两个分数尽可能接近f。

 

在解决这个问题之前，我们先介绍一些准备知识。

 

定义1：最简分数（也称既约分数或不可约分数）。若p,q的最大公约数是1，我们称分数p/q 是最简分数。不特别说明，以下提到的分数的分子和分母均为非负整数。

 

定义2：真分数，若p,q是正整数，0<p/q<1, 我们说p/q是真分数

 

定理1：分数a/b, c/d是最简真分数（也可以是0/1或者1/1）且a/b <c/d, 则有

1） 数(a+c)/(b+d)是一个最简分数，

2） a/b < (a+c)/(b+d)<b/d.

 

我们这里仅对第二个结论给出证明。我们定义r1 =a /b, r2= c/d, 则

 （a+c）/(b+d) – a/b

= (ab+cb-ab-ad)/(bb+bd)

=(cb-ad)/(bb+bd)

=(r2*bd-r1bd)/(bb+bd)

= (r2-r1)*bd / (bb+bd) >0

固(a+c)/(b+d)>a/b。同理可证 (a+c)/(b+d) < c/d

 

定义3：法雷数列

对任意给定的一个自然数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.

 

法雷数列的构造：

 法雷数列的构造可采用2分法，即如果 a/b， c/d （a/b<c/d）是一个n级法雷数列中的两个元素，且b+d<=n, 则可以在a/b, c/d 中间插入一个分数 (a+b)/(c+d)。下面以5级法雷数列为例，给出详细的过程。

 

step1: 准备两个数 0/1, 1/1 作为整个法雷数列的第一个元素和最后一个元素

step2: 在两个数中间插入1个数1/2, 变为

step3: 在每对相邻两个数中间插入1个数，变为

step4: 在每对相邻两个数中间插入1个数，变为

step5: 0/1 和 1/4 之间 和3/4和 1/1 仍然可插入1个数，使得插入的数分母不大于5

至此，该序列包含了所有分母不大于5的最简真分数，且各个分数以递增顺序排列。

 

法雷数列的性质：

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

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

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(分母大于指定值），计算中止。

若 abs(p/q-f)小于指定的值=, 计算中止。

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

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

 Step4, 重复step 2-3

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

 

 

 

   误差分析，根据法雷数列性质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。

 

下面给出一段示例代码，这段代码可计算出sqrt(2),sqrt(3),sqrt(5) 以及无理数π和e的 分数表示。 

 

 

#include "math.h"
#include "stdlib.h"
#include "stdio.h"
 
typedef struct _frac
{
	unsigned long numerator;
	unsigned long denominator;
}FRAC;
 
double getValue( FRAC f)
{
	double t=(double)f.numerator / (double)f.denominator;
	return t;
}
 
//f必须为正数
void searchFrac( FRAC* pLow, FRAC* pHigh,int n, double f)
{
	FRAC low;
	FRAC high;
	FRAC mid;
	int c;

	int k=(int)f;
	f -= (double)k; //得到ｆ的小数部分
    if ( f <= 0.5)
	{
		c=(int)(1.0/f);
		low.numerator=1;
		low.denominator=c+1;
		high.numerator=1;
		high.denominator=c;
	}
    else
	{
        c=(int)(1.0/(1.0-f));
		low.numerator=c-1;
		low.denominator=c;
		high.numerator=c;
		high.denominator=c+1;
	}
	
	mid.numerator= low.numerator + high.numerator;
	mid.denominator=low.denominator + high.denominator;
	
	while ( mid.denominator < n && fabs(f-getValue(mid))>1e-15 )
	{
#ifdef _DEBUG
		printf("f=%.16f\tmid=%u/%u=%.16f\n",f,mid.numerator,mid.denominator,getValue(mid));
#endif
		if ( getValue(mid) > f)
		{
			high=mid;
		}
		else
		{
			low=mid;
		}
		mid.numerator= low.numerator+ high.numerator;
		mid.denominator=low.denominator + high.denominator;
	}
	
	if (k>0)
	{
		low.numerator += k * low.denominator;
		high.numerator += k * high.denominator;
	}
	*pHigh = high;
	*pLow =low;
}
 
int main(int argc, char* argv[])
{
	FRAC low, high;
	double t;
	double f[]=
	{
		2,
		3,
		5,
		6,
		3.1415926535897932384626433832795,
		2.7182818284590452353602874713527
	};
	
	for (int i=0;i<sizeof(f)/sizeof(double);i++)
	{
		if (i<4)
			 t=sqrt(f[i]);
		else
			t=f[i];
 
		searchFrac(&low,&high,10000,t);
		printf("\nf=%.16f, low=%u/%u=%.16f high=%u/%u=%.16f\n\n",t,
			low.numerator,low.denominator,getValue(low),
			high.numerator,high.denominator,getValue(high));
	}
	return 0;
}

 版权所有 liangbch@263.net, 转载或者引用请注明出处。

 

参考文献：

1.        第36次编程比赛第1题题目 — 编程爱好者论坛：http://www.programfan.com/club/post-185318.html

2.        Farey Sequence -- from Wolfram MathWorld:http://mathworld.wolfram.com/FareySequence.html