• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            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




            解法一:
            生成所有分?jǐn)?shù),排序,去重。
            我剛開(kāi)始就是這么干的。

            解法二:
            老肖教的。
            Farey 數(shù)列。
            本題實(shí)際上是要求輸出 Farey 數(shù)列。


            遞歸生成:

             1/*
             2EOJ 1852 Ordered Fractions 
             3
             4Farey 數(shù)列。
             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 數(shù)列。
             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 閱讀(405) 評(píng)論(0)  編輯 收藏 引用 所屬分類: ACMAlgorithmMathematics課內(nèi)作業(yè)

            国产人久久人人人人爽| 99久久精品费精品国产| 无码任你躁久久久久久| 久久久久这里只有精品| 亚洲日本va午夜中文字幕久久| 一本大道久久东京热无码AV| 久久九九兔免费精品6| 久久精品国产亚洲AV高清热| 国产精品综合久久第一页| 久久亚洲国产成人精品无码区| 欧美一级久久久久久久大| 无码伊人66久久大杳蕉网站谷歌| 国产精品无码久久久久久| 久久亚洲AV无码西西人体| 欧美va久久久噜噜噜久久| 亚洲综合精品香蕉久久网97| 亚洲AV伊人久久青青草原| 99久久精品影院老鸭窝| 亚洲午夜久久久| 久久亚洲国产欧洲精品一| 久久香综合精品久久伊人| 国产91色综合久久免费| 日韩美女18网站久久精品| 久久九九青青国产精品| 亚洲中文久久精品无码| 久久精品成人免费观看97| 国内精品伊人久久久久av一坑 | 久久久久国产一区二区三区| 久久精品国产亚洲AV影院| 性欧美大战久久久久久久| 久久最近最新中文字幕大全| 久久水蜜桃亚洲av无码精品麻豆| 精品久久久久久久中文字幕| 国产99久久精品一区二区| 无码国产69精品久久久久网站| 亚洲国产综合久久天堂| 日本久久中文字幕| 亚洲欧洲精品成人久久奇米网| 99久久国产热无码精品免费久久久久 | 精品水蜜桃久久久久久久| 久久久久久久尹人综合网亚洲|