版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: "题解 - [POJ 1650] Integer Approximation" categories:
The FORTH programming language does not support floating-point arithmetic at all. Its author, Chuck Moore, maintains that floating-point calculations are too slow and most of the time can be emulated by integers with proper scaling. For example, to calculate the area of the circle with the radius $R$ he suggests to use formula like $R \times R \times 355 / 113$, which is in fact surprisingly accurate. The value of $355 / 113 ≈ 3.141593$ is approximating the value of $\pi$ with the absolute error of only about $2\times10^{-7}$. You are to find the best integer approximation of a given floating-point number $A$ within a given integer limit $L$. That is, to find such two integers $N$ and $D$ ($1 \leqslant N, D \leqslant L$) that the value of absolute error $|A - N / D|$ is minimal
The first line of input contains a floating-point number $A$ ($0.1 \leqslant A < 10$) with the precision of up to $15$ decimal digits. The second line contains the integer limit $L$. ($1 \leqslant L \leqslant 100000$)
Output file must contain two integers, N and D, separated by space
3.14159265358979
10000
355 113
Northeastern Europe 2001, Far-Eastern Subregion
给出一个小数 $A$(精确到至多 15 位)和一个整数 $L$, 求一个分数 $\frac{N}{D}$, 其中 $1\leqslant N,D\leqslant L$ 使得 $|A-\frac{N}{D}|$ 最小
直接暴力枚举就行, 比如枚举分母讨论分子
这里给出一种枚举方法
令min_diff记录当前绝对值的最小值, ans_n, ans_d分别为其对应的分子和分母
讨论当前的 N / D
N / D > AN / D - A < min_diff, 则更新 min_diff 等D 加一N / D < AA - N / D < min_diff, 则更新 min_diff 等N 加一N, D 有一个超出范围则结束另外要注意一点, 不能用long double, 因为数据是按double做的 (要求精度这么高数据还不好好做也是迷)