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

描述

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

输入

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

输出

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

样例输入

100 7 13

样例输出

50 93

算法分析：枚举法

1 #include
     
       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
     

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

1 #include 
     
         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\n", p, q);  17   18     return 0;  19 }
     

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