使用连分数获得无理数的最佳有理数逼近

连分数是一种很神奇的分数。关于连分数的概念、定理和一些简单的应用，请参见维基百科。

$$ x=a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cdots}}} $$

使用连分数，我们可以优雅的表示出所有的实数。对于有理数，它是有限连分数，对于无理数，它是无限逼近的。

现在我们来考虑一下如何将一个无理数表示为一个尽可能接近的分数。我们以二次根式为例。

首先，连分数的定义具有很强的递归性，我们可以很轻松的给出下面的方法，将一个实数转换为连分数：

SETP1 取出其整数部分。

SETP2 将其小数部分取倒数，然后重复第一步。

在这个过程中，每次取出整数，就依次排列，分别作为 $a_0$，$a_1$，$a_2$，…的值。

如果你能理解上面的方法，那么我们很快就可以找到取无理数的最佳有理数逼近的方法：使用无限连分数。无理数的无限连分数表示是非常有用的，因为它的初始段提供了对这个数的优异的有理数逼近。在维基百科该词条的「无限连分数」章节中，清晰了告诉了我们在计算这样的有理数时的递推公式。

下面这个程序实现了这样的算法。

#include <iostream>
#include <cmath>
#include <cstring>
 
using namespace std;
 
#define min(a,b) a>b?b:a
 
long long d[10000], fz[10000], fm[10000];
long long i = 0, p;
long long l1 = 0, l2 = 0;
 
void digui(double num)
{
	int zs = (int)floor(num);
	d[i++] = zs;
	if (zs == num)
		return;
	if (i > 2000)
		return;
	digui(1 / (num - zs));
}
 
long long getfenzi(int n)
{
	if (fz[n] != 0)
		return fz[n];
	long long i = -1;
	if (n == 0)
		i = d[0];
	else if (n == 1)
		i = d[0] * d[1] + 1;
	else i =  getfenzi(n - 1) * d[n] + getfenzi(n - 2);
	fz[n] = i;
	return i;
 
	if (i > p)
	{
		l1 = n - 1;
		i = 0;
		fz[n] = 0;
	}
	else
		fz[n] = i;
	return i;
}
 
long long getfenmu(int n)
{
	if (fm[n] != 0)
		return fm[n];
	long long i = -1;
	if (n == 0)
		i = 1;
	else if (n == 1)
		i = d[1];
	else i = getfenmu(n - 1) * d[n] + getfenmu(n - 2);
	fm[n] = i;
	return i;
 
	if (i > p)
	{
		l2 = n - 1;
		i = 0;
		fm[n] = 0;
	}
	else
		fm[n] = i;
	return i;
}
 
int main()
{
	int n;
	while (cin >> n)
	{
		if (n == 0)
			return 0;
		i = 0;
 
		memset(fz, 0, sizeof(fz));
		memset(fm, 0, sizeof(fm));
 
		digui(sqrt((double)n));
 
		getfenzi(25); getfenmu(25);
 
		int f;
		for (f = 0; f < 25; ++f)
		{
			cout << fz[f] << " " << fm[f] << endl;
		}
	}
	return 0;
}

这里的程序只计算了25项，其实可以继续精确下去，（但是前提是sqrt函数的结果要保证准确）。测试结果如下：

输入2（表示根号2），程序可以输出分式 759029082/536714611 : 1.41421356

这个结果和根号2的值已经相当的接近。

题外话：我帮你整理了包括 AI 写作、绘画、视频（自媒体制作）零门槛 AI 课程 + 国内可直接顺畅使用的软件。想让自己快速用上 AI 工具来降本增效，辅助工作和生活？限时报名。

猜你喜欢