7832:最接近的分数

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

描述

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

输入

三个正整数N，A，B，相邻两个数之间用单个空格隔开。1 <= A < B < N <= 1000。

输出

两个正整数，分别是所求分数的分子和分母，中间用单个空格隔开。

样例输入

100 7 13

样例输出

50 93

算法分析：枚举法

 1 #include<cstdio>
 2 double commom(double x,double y)
 3 {
 4     double m=x,n=y,r;
 5     do
 6     {
 7         r=int(m)%int(n);
 8         m=n;
 9         n=r;
10     }while(r!=0);
11     return m;
12 }
13 int main()
14 {
15     double sum,a,b,n,i,A,B,max=0,p,q;
16     scanf("%lf%lf%lf",&n,&a,&b);
17     for(B=n;B>=1;B--)
18         for(A=1;;A++)
19         {
20             if(A/B>a/b) break;
21             if(A/B>max&&A/B<a/b)
22             {
23                 max=A/B;
24                 p=A/commom(A,B);
25                 q=B/commom(A,B);
26             }
27         }
28     printf("%g %g",p,q);
29     return 0;
30 }

另一个AC代码，参考链接：http://blog.csdn.net/tigerisland45/article/details/71157783

 1 #include <iostream>  
 2 using namespace std;    
 3 int main()  
 4 {  
 5     int n, a, b, p, q, x, y;  
 6   
 7     scanf("%d%d%d", &n, &a, &b);  
 8   
 9     // 分子x从1-n，分母y从n-1；结果p/q，开始时1/n（最小值）  
10     p = 1, q = n;  
11     for(x=1; x<=n; x++)  
12         for(y=n; y>=1; y--)  
13             if(b * x < a * y && x * q > p * y)  
14                 p = x, q = y;  
15   
16     printf("%d %d
", p, q);  
17   
18     return 0;  
19 }

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