• <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 閱讀(407) 評(píng)論(0)  編輯 收藏 引用 所屬分類(lèi): ACMAlgorithmMathematics課內(nèi)作業(yè)

            中文字幕无码精品亚洲资源网久久| 国产韩国精品一区二区三区久久| 久久精品无码一区二区三区免费| 久久精品亚洲乱码伦伦中文| 亚洲乱码精品久久久久..| 99热成人精品热久久669| 93精91精品国产综合久久香蕉 | 99久久免费国产精品特黄| 久久精品国产99久久久| 无码精品久久一区二区三区 | 久久一区二区免费播放| 亚洲国产精品18久久久久久| 久久se这里只有精品| 久久久久久久久无码精品亚洲日韩 | 久久er国产精品免费观看8| 超级碰碰碰碰97久久久久| 国内精品久久久久久不卡影院| 精品久久久无码人妻中文字幕| 久久久WWW成人| 99精品久久精品| 久久精品国产亚洲AV嫖农村妇女 | 欧美大香线蕉线伊人久久| 女人高潮久久久叫人喷水| 91精品日韩人妻无码久久不卡| 精品久久久久久成人AV| 欧洲成人午夜精品无码区久久 | 久久99精品国产自在现线小黄鸭| 久久人人爽人人爽人人av东京热| 欧美亚洲另类久久综合婷婷| 精品一久久香蕉国产线看播放| 成人精品一区二区久久| 色综合久久精品中文字幕首页| 国产美女久久久| 国产精品久久久久乳精品爆| 国产精品成人无码久久久久久 | 久久亚洲AV成人出白浆无码国产 | 久久久精品国产亚洲成人满18免费网站 | 蜜臀久久99精品久久久久久| 久久人人爽人人澡人人高潮AV | 久久久久久亚洲精品不卡| 亚洲精品高清一二区久久|