coreBugZJ

此 blog 已弃。

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 数列。
本题实际上是要求输出 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课内作业


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理