POJ 1650 - Integer Approximation

http://poj.org/problem?id=1650

概要

小数 \(A\) と整数 \(L\) が与えられる． \(1 \le N, D \le L\) なる整数 \(L, D\) で，\(\left|A - \frac{N}{D}\right|\) が最小になる組を答える．

制約

• \(0.1 \le A < 10\)
• \(A\) は15桁以下
• \(1 \le L \le 10 ^ 5\)

解法

ある \(D\) を決めると，\(\left|A - \frac{N}{D}\right|\) を最小にする \(N\) は \(n = \lfloor A D \rfloor\) に対して \(n-1, n, n+1\) のいずれかであるため，全 \(D\) に関してこらの最小値をとればよい．

最初，精度が足りないかと思って色々工夫していたが，実は double の精度で十分だった．

 1 #include <iostream>
 2 #include <cmath>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   double A;
 8   int L;
 9   cin >> A >> L;
10 
11   int ansN, ansD;
12   double err = 100;
13   for (int D = 1; D <= L; D++) {
14     const int N = A*D;
15     for (int n = N-1; n <= N+1 && n <= L; n++) {
16       const double d = fabs(A - double(n)/D);
17       if (d < err) {
18         err = d;
19         ansN = n;
20         ansD = D;
21       }
22     }
23   }
24   cout << ansN << ' ' << ansD << endl;
25   return 0;
26 }