Ordered Fractions - USACO 2.1.2

orderedfractions - codetrick
Consider the set of all reduced fractions between 0 and 1 inclusive with denominators less than or equal to N.
Here is the set when N = 5:

0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1  

Write a program that, given an integer N between 1 and 160 inclusive, prints the fractions in order of increasing magnitude.

PROGRAM NAME: frac1

INPUT FORMAT

One line with a single integer N.

SAMPLE INPUT (file frac1.in)

5  

OUTPUT FORMAT

One fraction per line, sorted in order of magnitude.

SAMPLE OUTPUT (file frac1.out)

0/1  1/5  1/4  1/3  2/5  1/2  3/5  2/3  3/4  4/5  1/1

http://blog.csdn.net/keybord_dancer/article/details/40623513

我们发现可以把0/1和1/1分别作为起点和终点，然后通过增大分子和分母来递归地生成中间的点。

0/1                                                             1/1
                                1/2
                  1/3                       2/3
        1/4              2/5          3/5              3/4
    1/5      2/7     3/8    3/7    4/7   5/8     5/7        4/5

每个分数都是由它左边和右边的分数生成的。这种想法有助于在递归过深时跳出。

Update: 据查，这个解法利用了法里数列及其相关性质。详见：资料1 资料2
http://sdjl.me/index.php/archives/70

    private static int n;
    private static int[] numerator = new int[8000];
    private static int[] denominator = new int[8000];
    private static int ansCount = 0;

    public static void main(String[] args) throws IOException
    {
        init();
        run();
        output();
        System.exit(0);
    }

    private static void run()
    {
        numerator[ansCount] = 0;
        denominator[ansCount] = 1;
        ansCount++;

        solve(0, 1, 1, 1);

        numerator[ansCount] = 1;
        denominator[ansCount] = 1;
        ansCount++;
    }

    private static void solve(int n1, int n2, int d1, int d2)
    {
        if (d1 + d2 > n)
        {
            return;
        }
        solve(n1, n1 + n2, d1, d1 + d2);

        numerator[ansCount] = n1 + n2;
        denominator[ansCount] = d1 + d2;
        ansCount++;

        solve(n1 + n2, n2, d1 + d2, d2);
    }

http://jackneus.com/programming-archives/ordered-fractions/

struct fraction{

    int nom, denom;

    bool operator < (const fraction & b) const {

        return 1.0 * nom / denom < 1.0 * b.nom / b.denom;

    }

};

bool isIn(fraction fract, vector<fraction> & a){

    for(int i = 0; i < a.size(); i++){

        if(a[i].nom == fract.nom && a[i].denom == fract.denom) return true;

    }

    return false;

}

fraction reduce(fraction fract){

    for(int i = fract.nom; i != 0; i--){

        if(fract.nom % i == 0 && fract.denom % i == 0){

            fract.nom /= i;

            fract.denom /= i;

            return fract;

        }

    }

    return fract;

}

int main(){

    ifstream in("frac1.in");

    ofstream out("frac1.out");

    int N;

    in >> N;

    vector<fraction> soluts;

    fraction fract;

    fract.nom = 0;

    fract.denom = 1;

    soluts.push_back(fract);

    fract.nom = 1;

    fract.denom = 1;

    soluts.push_back(fract);

    for(int i = 1; i <= N; i++){

        for(int j = i + 1; j <= N; j++){

            fraction fract;

            fract.nom = i;

            fract.denom = j;

            fract = reduce(fract);

            if(!isIn(fract, soluts)) soluts.push_back(fract);

        }

    }

    sort(soluts.begin(), soluts.begin() + soluts.size());

    for(int i = 0; i < soluts.size(); i++) out << soluts[i].nom << "/" << soluts[i].denom << endl;

}

http://blog.csdn.net/acm_lkl/article/details/44180387
while(fin>>n) { p[1].a=0; p[2].a=1; p[1].b=1; p[2].b=1; int cnt=3; for(int i=2;i<=n;i++) for(int j=1;j<i;j++) { p[cnt].a=j+0.0; p[cnt].b=i+0.0; cnt++; } sort(p+1,p+cnt,cmp); fout<<p[1].a<<"/"<<p[1].b<<endl; P tmp = p[1]; for(int i=2;i<cnt;i++) { if(p[i].a/p[i].b==tmp.a/tmp.b) continue; fout<<p[i].a<<"/"<<p[i].b<<endl; tmp=p[i]; } }
X. 利用两层循环进行枚举分子分母，当分子分母最大公约数为1时记录下来。
Java: https://github.com/TomConerly/Competition-Programming/blob/master/USACO/Chapter2/frac1.java

    while(~scanf("%d",&n))

    {

        int total=0;

        //total表示除0/1和1/1外最简分数的数量。

        for(int i=1;i<=n;i++)

            for(int j=1;j<i;j++)

                if(gcd(i,j)==1)

                //最大公约数等于1时，说明分子分母互质。

                {

                    arry[total].a=j;

                    arry[total++].b=i;

                }

        qsort(arry,total,sizeof(arry[0]),cmp);

        //排序

        printf("0/1\n");

        for(int i=0;i<total;i++)

            printf("%d/%d\n",arry[i].a,arry[i].b);

        printf("1/1\n");

    }

http://blog.csdn.net/keybord_dancer/article/details/40623513
Read full article from orderedfractions - codetrick