[hoj 1076] Ordered Fractions[Farey 시퀀스]

1253 단어
N보다 분모가 크지 않은 Farey 시퀀스를 생성합니다.
이것은 귀속구법이다.
확장 유클리드의 정리로 인접한 다음 항목을 구할 수 있다.
공식 K1*L2 - K2*L1 = 1
아직 공부를 안 해서...
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int n;
typedef struct node
{
    int up,down;
    double val;
}node;
bool cmp(node a, node b)
{
    return a.val<b.val;
}
vector<node> v;
int gcd(int x,int y)
{
    if(!x)  return y;
    if(x<y)
    {
        return gcd(y%x,x);
    }
    return gcd(x%y,y);
}
void build(int a, int b, int x, int y)
{
    int p = a+x;
    int q = b+y;
    int tmp = gcd(p,q);// 
    p /= tmp;
    q /= tmp;
    if(q<=n)
    {
        build(a,b,p,q);
        v.push_back((node){p,q,(double)p/q});
        build(p,q,x,y);
    }
}

int main()
{
    while(scanf("%d",&n)==1)
    {
        while(!v.empty())   v.pop_back();
        v.push_back((node){0,1,0.0});
        v.push_back((node){1,1,1.0});
        build(0,1,1,1);
        sort(v.begin(),v.end(),cmp);
        for(vector<node>::iterator it = v.begin();it < v.end(); it++)
        {
            printf("%d/%d
",it->up,it->down);
        }
        printf("
");
    }
}
알고리즘 테마: Merge Sort
1,1,3,5......귀속 알고리즘

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage