题解 - [POJ 1650] Integer Approximation

发表于 更新于 分类于 ， 本文字数： 445 阅读时长 ≈ 2 分钟

题目链接

原始题面

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 \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

Input

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

Output file must contain two integers, N and D, separated by space

Sample Input

1
2
3.14159265358979
10000

Sample Output

1
355 113

Source

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 > A
    • 如果 N / D - A < min_diff, 则更新 min_diff 等
    • 否则 D 加一
  • 如果 N / D < A
    • 如果 A - N / D < min_diff, 则更新 min_diff 等
    • 否则 N 加一
  • 当 N, D 有一个超出范围则结束

另外要注意一点，不能用 long double, 因为数据是按 double 做的 (要求精度这么高数据还不好好做也是迷)

代码参考

Show code

POJ_1650view raw
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
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <cstdio>
int main() {
  double n;
  int d;
  scanf("%lf%d", &n, &d);
  double min_diff = 100;
  int a = 1, b = 1, min_a = 1, min_b = 1;
  while (a <= d && b <= d) {
    double now = 1.0l * a / b;
    if (now > n) {
      if (now - n < min_diff) {
        min_diff = now - n;
        min_a = a;
        min_b = b;
      }
      ++b;
    } else if (now < n) {
      if (n - now < min_diff) {
        min_diff = n - now;
        min_a = a;
        min_b = b;
      }
      ++a;
    } else {
      min_diff = 0;
      min_a = a;
      min_b = b;
      break;
    }
  }
  printf("%d %d", min_a, min_b);
}