[컴퓨팅사고력] 이집트 분수

이집트 분수(Egyptian fraction)는 다음과 같은 별개의 단위분수의 유한개의 합의 형태를 가리킵니다.

예를 들어 5/7 을 이집트 분수로 표현하면 다음과 같이 표현합니다.

5/7 = 1/2 + 1/5 + 1/70

이러한 이집트 분수는 이집트에서 기원전부터 사용한 역사적인 사실 외에도 분수의 또 다른 표현에서 몇가지 실질적인 잇점이 있습니다.

예를 들어 이집트 분수는 많은 개체를 동일한 공유로 나누는데 도움을 줄 수가 있는데 8명이 식사를 하는데 5개의 피자를 똑같이 나누고 싶습니다.

이것을 이집트 분수로 표현하면 다음과 같이 됩니다.

5/8 = 1/2 + 1/8

이것은 피자 4개를 절반으로 나누어서 8명에게 1/2 씩 주고 나머지 한개를 8조각으로 나누어서 1/8로 나누어 줄 수 있다는 의미가 됩니다.

그렇다면 48명이 식사를 하는데 피자가 43개일때 동일하게 나누는 경우 43/48 이 되는데 이것을 이집트 분수로 나타내면 어떻게 되는지 구해 주세요.

문제풀이

먼저 43/48 은 다음과 같이 표현할 수 있다. 1/(a+1) <43/48 < 1/a 이렇게 표현 후에 a의 값을 나열해 보자 a 의 값은 1만 나오지만 여기서 많은 수가 나열 된다고 하면 분수에 가장 가까눈 큰 a를 선택해 주면 된다. 따라서 1/2 + 19/48 같은 방법으로 1/(a+1) <19/48 < 1/a  에서 a를 나열하면 1,2 가 되고 여기서 a를 2를 선택해 주면 된다. 따라서 1/2 + 1/3 + 3/48  여기서 3/48 = 1/16 이므로 이집트 분수로 표현하면 다음과 같이 표현 할 수 있다. 1/2 + 1/3 + 1/16

 

컴퓨팅 사고력

문제 풀이 과정에서 1/(a+1) <43/48 < 1/a 에서 a의 가능한 값을 나열해 놓고 그 중에서 가장 큰 값을 구한 다음 해당 분수에서 1/a 를 뺀 나머지를 가지고 동일한 작업을 하는 것을 확인 할 수 있습니다.

이러한 문제는 컴퓨터과학에서 그리디 알고리즘이라고 합니다.

자신의 차례에서 최선의 선택을 한 후에 나머지를 다음 차례에게 돌려 주는 형태의 알고리즘입니다.

이러한 문제를 코딩으로 해결 하면 다음과 같이 코딩 할 수 있습니다.

int gcd(int a,int b){
    if(a%b==0) return b;
    return gcd(b,a%b);
}
int main()
{
    int bj=43;
    int bm=48;
    int a;

    while(1){
        //분모와 분자를 기약분수로 만들어 준다.
        int tempbm = bm/gcd(bm,bj);
        int tempbj = bj/gcd(bm,bj);
        bm = tempbm;
        bj = tempbj;
        if(bj==1) break; ///분자가 1이면 끝내자

        a = bm/bj;
        printf("1/%d + ",a+1);
        bj=bj*(a+1) - bm;
        bm=bm*(a+1);
    }

    printf("1/%d",bm/bj);
    return 0;
}