0과 1사이의 기약분수

프로그램 명: fraction

제한시간: 2 초

수 N 을 입력으로 받아 0 부터 N 까지의 수를 사용하여 0 과 1 사이(0,1 포함)에 있는 기약분수를 구하는게 문제이다.

예를 들어 , N 이 5 이면 0 , 1 , 2 , 3 , 4 , 5 를 사용하여 0 과 1 사이수를 크기 순으로 구하면

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

이 된다. 시간은 2 초를 초과할 수 없다.

입력 형식

양의 정수 N (1 <= N <= 100) 이 입력된다.

출력 형식

한 줄에 하나씩 크기 순으로 출력한다.

입출력 예

입력

5

출력 

0/1

1/5

1/4

1/3

2/5

1/2

3/5

2/3

3/4

4/5

1/1

#include <stdio.h>

int gcdof(int a, int b) {

    int r=1;

    while(r!=0) {

        r=a%b;

        a=b;

        b=r;

    }

    return a;

}

int bigger(int a1, int a2, int b1, int b2) {

    if(a1*b2>b1*a2) return 1;

    else return 0;

} 

int main() {

    int data[20000]={0,};

    int i, j, k=0, nk, n, x, y;

    scanf("%d", &n);

    for(i=2;i<=n;++i) {

        for(j=1;j<i;++j) {

            if(gcdof(i,j)==1) {

                data[k++]=j;

                data[k++]=i;

            }    

        }

    }

    nk=k;

    // 버블정렬을 한다. 갯수는 nk/2 개이다.

    for(i=0;i<nk;i+=2) {

        for(j=0;j<nk-i-2;j+=2) {

            if(bigger(data[j],data[j+1],data[j+2],data[j+3])) {

                x=data[j]; y=data[j+1]; 

                data[j]=data[j+2]; data[j+1]=data[j+3];

                data[j+2]=x; data[j+3]=y;

            }

        }

    }

    printf("0/1\n");

    for(i=0;i<nk;i+=2) {

        printf("%d/%d\n", data[i], data[i+1]);

    }

    printf("1/1\n");

    return 0;

}

============================

구조체를 사용하여 고친 것

#include <stdio.h>

typedef struct _fraction {

    int nmt; // 분자 numerator 를 줄여서 nmt 라고 적음

    int dnt;  // 분모 denominator 를 줄여서 dnt 라고 적음

}  fraction; // 분수 구조체

int gcdof(int a, int b) { // 두 정수를 받아서 최대공약수를 구함

    int r=1;

    while(r!=0) {

        r=a%b;

        a=b;

        b=r;

    }

    return a;

}

int bigger(fraction f1, fraction f2) { // 분수의 대소를 비교

    if((f1.nmt*f2.dnt)>(f2.nmt*f1.dnt)) return 1;

    else return 0;

} 

int main() {

    fraction data[1000]={0,}; // 분수를 위한 배열을 잡음 큰수를 위해서는 좀더 큰 배열이 필요

    fraction tmp; // 버블 정렬을 할 때 사용하기 위한 임시변수

    int i, j, k=0, nk, n, x, y;

    scanf("%d", &n);

    for(i=2;i<=n;++i) { // 모든 가능한 분모와 (2이상의)

        for(j=1;j<i;++j) { // 모든 가능한 분자에 대해서 (1이 되는 경우는 제외)

            if(gcdof(i,j)==1) { // 기약분수인 경우에만

                data[k].nmt=j; // data에 추가한다.

                data[k].dnt=i;

                k+=1;

            }    

        }

    }

    nk=k; 

    // 버블정렬을 한다. 갯수는 nk 개이다.

    for(i=0;i<nk;i+=1) {

        for(j=0;j<nk-i-1;j+=1) {

            if(bigger(data[j],data[j+1])) {

                tmp=data[j];   

                data[j]=data[j+1]; 

                data[j+1]=tmp;

            }

        }

    }

    printf("0/1\n"); // 처음에 0/1을 출력한다.

    for(i=0;i<nk;i+=1) {

        printf("%d/%d\n", data[i].nmt, data[i].dnt);

    }

    printf("1/1\n"); // 나중에 1/1을 출력한다.

    return 0;

}