线性的算法,记录最近的分数,最后约分。
#include <stdio.h>

int gdc(int a, int b)
{

    
if (a==0)
    
{
        
return b;
    }

    
if (b==0)
    
{
        
return a;
    }

    
return gdc(b, a%b); 
}


int main()
{

    
int n, d;
    
int i;
    
double min;
    
int mn, md;
    
int men, med;
    
double minest;
    
int temp;
    
int pub;
    
double t1, t2;
    
while (scanf("%d%d"&n, &d) != EOF)
    
{
        minest 
= 1;
        pub 
= gdc(n, d);
        n 
= n/pub;
        d 
= d/pub;
        
for (i=1; i<=32767; i++)
        
{
            min 
= 1;
            temp 
= (int)((double)i * (double)n / (double)d);
            pub 
= gdc(i, temp);
            
if (temp/pub!=|| i/pub!=d)
            
{
                
if ((double)n/(double)d-(double)temp/(double)i < (double)(temp+1)/(double)i-(double)n/(double)d)
                
{
                    min 
= (double)temp/(double)i;
                    mn 
= temp;
                    md 
= i;
                }

                
else
                
{
                    min 
= (double)(temp+1)/(double)i;
                    mn 
= temp+1;
                    md 
= i;
                }

            }

            t1 
= min-(double)n/(double)d>0 ? min-(double)n/(double)d:(double)n/(double)d-min;
            t2 
= minest-(double)n/(double)d>0 ? minest-(double)n/(double)d:(double)n/(double)d-minest;
            
if (t1<t2)
            
{
                minest 
= min;
                men 
= mn;
                med 
= md;
            }

        }

        pub 
= gdc(men, med);
        printf(
"%d %d\n", men/pub, med/pub);
    }

    
return 0;
}