首页 > 其他 > 详细

USACO Ordered Fractions

时间:2014-02-05 00:57:11      阅读:350      评论:0      收藏:0      [点我收藏+]

就是法雷数列。。。

Ordered Fractions

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.

PROGRAM NAME: frac1

INPUT FORMAT

One line with a single integer N.

SAMPLE INPUT (file frac1.in)

5

OUTPUT FORMAT

One fraction per line, sorted in order of magnitude.

SAMPLE OUTPUT (file frac1.out)

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

/*
ID: qhn9992
PROG: frac1
LANG: C++11
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int n;

void getans(int a,int b,int c,int d)
{
    int nc=a+c,tr=b+d;
    if(tr<=n)
    {
        getans(a,b,nc,tr);
        printf("%d/%d\n",nc,tr);
        getans(nc,tr,c,d);
    }
}

int main()
{
    freopen("frac1.in","r",stdin);
    freopen("frac1.out","w",stdout);
    scanf("%d",&n);
    printf("0/1\n");
    getans(0,1,1,1);
    printf("1/1\n");
    return 0;
}



USACO Ordered Fractions

原文:http://blog.csdn.net/u012797220/article/details/18923521

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!