# coreBugZJ

## EOJ 1852. Ordered Fractions

Ordered Fractions

Time Limit:1000MSMemory Limit:30000KB
Total Submit:191Accepted:122

Description

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.

Input

One line with a single integer N.

Output

One fraction per line, sorted in order of magnitude.

Sample Input

5

Sample Output

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

Source

usaco

Farey 数列。

1/*
2EOJ 1852 Ordered Fractions
3
4Farey 数列。
5
6*/

7
8
9#include <stdio.h>
10
11int n;
12
13void farey( int a1, int b1, int a2, int b2 ) {
14        if ( b1 + b2 > n ) {
15                return;
16        }

17        farey( a1, b1, a1+a2, b1+b2 );
18        printf( "%d/%d\n", a1+a2, b1+b2 );
19        farey( a1+a2, b1+b2, a2, b2 );
20}

21
22int main() {
23        scanf( "%d"&n );
24        puts( "0/1" );
25        farey( 0111 );
26        puts( "1/1" );
27        return 0;
28}

29

1/*
2EOJ 1852 Ordered Fractions
3
4Farey 数列。
5
6*/

7
8
9#include <stdio.h>
10
11void farey( int n ) {
12        int preA, preB, curA, curB, nxtA, nxtB;
13
14        preA = 0;
15        preB = 1;
16        curA = 1;
17        curB = n;
18
19        printf( "%d/%d\n", preA, preB );
20        printf( "%d/%d\n", curA, curB );
21        while ( curA != curB ) {
22                nxtA = ( preB + n ) / curB * curA - preA;
23                nxtB = ( preB + n ) / curB * curB - preB;
24                printf( "%d/%d\n", nxtA, nxtB );
25                preA = curA;
26                preB = curB;
27                curA = nxtA;
28                curB = nxtB;
29        }

30}

31
32int main() {
33        int n;
34        scanf( "%d"&n );
35        farey( n );
36        return 0;
37}

38

posted on 2012-02-29 19:33 coreBugZJ 阅读(291) 评论(0)  编辑 收藏 引用 所属分类: ACMAlgorithmMathematics课内作业