UVa 654 - Ratio

链接

传送门

题意

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

思路

枚举分母计算。

代码

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
#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;
}