小数逼近算法

常用的小数逼近算法有擂台算法与追赶算法，擂台最坏的时间复杂度为O(N^2)，追赶的时间复杂度为O(2n)。

擂台算法

给定小数A，求[1,L]范围内的两个整数N，D，使得N/D≈A，且为该范围内的精度最高比。

擂台算法通过让N、D双重循环，找到最优解，保存输出。

追赶算法

同为上题，追赶算法让N、D均从最小值1开始，近似拟合A，并不断调整比值。比值大了，就把分母增大1；比值小了，就把分子增大1。直到分子或分母达到最大值L处，结束循环。把循环中出现的精度最高值保存并输出。

查看代码

#include <bits/stdc++.h>
#define MAX 10.0
using namespace std;
int main() {
	double a, imin = MAX;
	int l, n, d, cld = 1, prt = 1;
	cin >> a >> l;
	while (cld<=l && prt<=l) {
		double t = cld*1.0/prt-a;
		if (fabs(t)<imin) {
			imin = fabs(t);
			n = cld;
			d = prt;
		}
		if (!t) break;
		else if (t<0) cld ++;
		else prt ++;
	}
	cout << n << ' ' << d;
	return 0;
}