文章作者：姜南(Slyar) 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。
暴力枚举
Description
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 * R * 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*10-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 <= N, D <= L) that the value of absolute error |A – N / D| is minimal.
Input
The first line of input contains a floating-point number A (0.1 <= A < 10) with the precision of up to 15 decimal digits. The second line contains the integer limit L. (1 <= L <= 100000).
Output
Output file must contain two integers, N and D, separated by space.
Sample Input
3.14159265358979
10000
Sample Output
355 113
Slyar:求出在L范围内的两个数，使得它们相除后减去A的结果的绝对值最小。暴力枚举就好了，这题很恶心…
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include <iostream> #include <cmath> using namespace std; int main() { double a, min, temp; int i, j, l, n, d; cin >> a >> l; n = d = 1; min = 20; for (i = 1; i <= l; i++) { j = (int)(i / a); if (j > l) continue; temp = fabs(a - (double)i / (double)j); if (temp < min) { min = temp; n = i; d = j; } j++; if (j > l) continue; temp = fabs(a - (double)i / (double)j); if (temp < min) { min = temp; n = i; d = j; } } cout << n << " " << d << endl; //system("pause"); return 0; } |