線性的算法，記錄最近的分數，最后約分。
#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!=n || 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;
}