POJ NOI MATH-7832 最接近的分数

问题链接：POJ NOI MATH-7832 最接近的分数。

---

总时间限制: 1000ms 内存限制: 65536kB 描述

分母不超过 N 且 小于 A/B 的最大最简分数是多少？

输入 三个正整数N，A，B，相邻两个数之间用单个空格隔开。1 <= A < B < N <= 1000。 输出 两个正整数，分别是所求分数的分子和分母，中间用单个空格隔开。 样例输入 100 7 13 样例输出 50 93 提示 来源 2007年我爱数学少年夏令营数学竞赛 第9题

---

问题分析

  穷举法虽然不理想，却是一种最后的手段，而且逻辑简单，全靠计算机算得快。

  用穷举法找满足条件的最大分数。

程序说明

  给出的程序采用穷举法，说明都在程序中了。

  应该可以使用二分法来优化的。

---

参考链接：（略）。

---

AC的C++语言程序：

#include <iostream> using namespace std; int main() { int n, a, b, p, q, x, y; scanf("%d%d%d", &n, &a, &b); // 分子x从1-n，分母y从n-1；结果p/q，开始时1/n（最小值） p = 1, q = n; for(x=1; x<=n; x++) for(y=n; y>=1; y--) if(b * x < a * y && x * q > p * y) p = x, q = y; printf("%d %d\n", p, q); return 0; }