使用連分數獲得無理數的最佳有理數逼近

連分數是一種很神奇的分數。關於連分數的概念、定理和一些簡單的應用，請參見維基百科。

$$ 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的值已經相當的接近。

猜你喜歡