USACO sec2.1 Ordered Fractions

首先两重 for 循环对可能取的值约分，分子分母分别存放，根据比较分数大小的方法排序，然后按顺序输出（相同的只输出一个）；

/*
PROG : frac1
LANG : C++
*/
# include <stdio.h>
# include <stdlib.h>

# define MAXN (160 * 160)

/***************************************************/
int num[MAXN], den[MAXN], r[MAXN], m = 0;
int cmp(const void *xx, const void *yy)
{
    int x = *(int*)xx;
    int y = *(int*)yy;
    return num[x]*den[y] > den[x]*num[y] ? 1 : -1;
}

int gcd(int a, int b)
{
    if (!b) return a;
    return gcd(b, a%b);
}

void solve(void)
{
    int i, j, n;
    scanf("%d", &n);
    num[0] = 0, den[0] = 1;
    for (i = 1; i <= n; ++i)
    for (j = 1; j <= n; ++j)
    {
        if (i > j) continue;
        ++m;
        num[m] = i/gcd(i, j);
        den[m] = j/gcd(i, j);
    }
    for (i = 0; i <= m; ++i) r[i] = i;
    qsort(r, m, sizeof(r[0]), cmp);
    printf("%d/%d\n", num[r[0]], den[r[0]]);
    for (i = 1; i <= m; ++i)
    {
        if (num[r[i]] == num[r[i-1]] && den[r[i]] == den[r[i-1]])
            continue;
        else
            printf("%d/%d\n", num[r[i]], den[r[i]]);
    }
}

/***************************************************/

int main()
{
    freopen("frac1.in", "r", stdin);
    freopen("frac1.out", "w", stdout);
    
    solve();
    
    fclose(stdin);
    fclose(stdout);
    
    return 0;
}