이집트 분수(Egyptian Fraction)

이집트 분수(Egyptian fraction)란 유리수를 단위분수((분자가 1인것))의 합으로 표현하는 것을 말한다.

[출처 ] https://www.futurelearn.com/courses/maths-puzzles/0/steps/13994

 

 

이집트 분수는 이집트에서 기원전부터 사용한 역사적인 사실 외에도, 분수의 또 다른 표현에서 많은 개체를 동일하게 공유할수있도록 나눈데 도움을 줄 수 있는 장점이 있다.
예를들어 만약 8명의 저녁 식사에 5개의 피자를 똑같이 나누기를 원한다면, 이집트 분수 표현은 아래처럼 표현 가능한데 이는 각 사람이 피자 반쪽(1/2)과 나머지 피자 8분의 1을씩 동일하게 공유할 수 있다는 것을 보여준다.

이것은 피자 4개를 반으로 나누고 나머지 피자는 8개로 나눌수 있고 또는 5개의 피자를 반으로 나누고 나뉜 피자 10개를 다시 각각 8개로 나누어 총80개로 나뉜 피자를 8명이서 10개씩 나눈것을 의미한다.

 

그럼 서로 다른 단위분수로 표현하는 문제를 생각해보자.

Greedy Algorithm을 사용하여 Egyptian Fractions을 생성 할 수 있는데  만약 A/B ( A < B) 인 경우, 가능한 가장 큰 단위 분수를 먼저 찾은 다음 나머지 부분을 반복(recursion) 하면된다. 

가장 큰 단위 분수를 찾는 공식(증명은 생략)은 다음과 같다.

 

A/B에 대한 가장 큰 단위분수 =  1 / ( B / A + 1) 이 된다.
예를들어 6/14를 고려하면 처음 가장큰 단위 분수를 구하기위해 N =  B/A 값을 먼저 구하면 2가 되고  대입하면 1/(2 + 1) = 1/3 이 된다.
이제 첫 번재 단위 분수는 1/3이 되고 그 다음에 나머지에 대한 단위분수중 가장 큰 단위분수를 찾으면 되는데
나머지는 (6/14 - 1/3) 즉 4/24 에 대해 위 과정을 반복하다가 분자%분모 = 0 이 되는 경우(그리디 방법은 그 분수에서 뺄 수 있는 가장 큰 단위 분수를 0이 될 때 까지 계속해서 빼는 방법)  더 이상 진행하지 않고 1/분자 를 출력하고 재귀를 빠져나가면 된다.

 

 

public class EgyptianFactionMain {
 
    /**
     * @n numerator 분자
     * @d denominator 분모
     * */
    public static void egyptianFaction(int n, int d) {
 
        if(n == 0 || d == 0) {
            return;
        }
        System.out.println(String.format("n=%d, d=%d", n, d));
        // If numerator divides denominator,
        // then simple division makes
        // the fraction in 1/n form
        if (d % n == 0) {
            System.out.println("1/" + d /n);
            return;
        }
 
        // 단위분수중 가장 큰 값을 공식에 의해 계산한다.
        int maxuf = d/n + 1; // max unit fraction.
        System.out.println(String.format("1/%d", maxuf));
 
        // 나머지 (n/d - 1/maxuf) 에 대해서도 반복한다.
        egyptianFaction(n*maxuf - d, d*maxuf);
    }
 
    public static void main(String[] args)  {
        egyptianFaction(2, 3);
 
    }
 
}
 

약간 변형 문제 : https://www.acmicpc.net/problem/4587

레퍼런스

• 위키백과 : https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%91%ED%8A%B8_%EB%B6%84%EC%88%98