UVa 654 - Ratio

链接

传送门

题意

给出\(a,b\)求，输出从分母从1到\(b\)的最接近\(a/b\)的分数，输出要保证精度不断上升，如果精度下降则不输出。

思路

枚举分母计算。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int inf = 0x3f3f3f3f;

int main() {
    int a, b, t = 0;
    while (~scanf("%d%d", &a, &b)) {
        if (t++) {
            puts("");
        }
        double x = double(a) / b, pre = inf;
        for (int i = 1; i <= b; ++i) {
            int s = floor(i * x + 0.5);
            double cur = fabs(double(s) / i - x);
            if (cur < pre) {
                pre = cur;
                printf("%d/%d\n", s, i);
            }
        }
    }
    return 0;
}