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 數列。
本題實際上是要求輸出 Farey 數列。
遞歸生成：
1
/**//*
2
EOJ 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( 0, 1, 1, 1 );
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