Implementation of Egyptian Fraction using Greedy Algorithm in C++

In this article, we will learn how to implement Egyptian Fraction using a Greedy Algorithm in C++. A positive fraction number can be represented as the sum of unique unit fractions. A fraction is said to be a unit fraction if its numerator is one and the denominator some positive number. For example, 1/8 is said to be a unit fraction.

Some of the examples of Egyptian Fraction are

Egyptian Fraction representation of 5/6 is 2/3 + 1/2.

Egyptian Fraction representation of 8/15 is 1/3 + 1/5.

Egyptian Fraction using Greedy Algorithm in C++

1. Firstly, get the numerator and denominator of the fraction as n and d respectively.

2. Check the corner when d is equal to zero or n is equal to zero.

3. Check if d is divisible by n then print 1/(d/n).

4. If n is divisible by d then print (n/d).

5. Now compare n with d, if n is greater than d

• print n/d
• recursively call the egyptianFraction() function i.e. egyptianFraction(n%d, d);

6. If d is greater than n

• print d/n + 1
• recursively call the egyptianFraction() function i.e. egyptianFraction(n*x-d, d*x);

#include <bits/stdc++.h>
using namespace std;
void egyptianFraction(int n, int d){
    if (d == 0 || n == 0)
    return;
    if(d%n == 0){
        cout<<"1/"<<d/n;
        return;
    }
    if(n%d == 0){
        cout<<n/d;
        return;
    }
    if (n>d){
        cout<<n/d<<" + ";
        egyptianFraction(n%d, d);
        return;
    }
    int x = d/n+1;
    cout<<"1/"<<x<<" + ";
    egyptianFraction(n*x-d, d*x);
}
int main(){
    int n, d;
    cout<<"Enter the numerator of fraction: ";
    cin>>n;
    cout<<"Enter the denominator of fraction: ";
    cin>>d;
    cout<<"Egyptian Fraction representation of "<<n<<"/"<<d<<" is"<<endl;
    egyptianFraction(n, d);
    return 0;
}

Output

Enter the numerator of fraction: 2
Enter the denominator of fraction: 3
Egyptian Fraction representation of 2/3 is
1/2 + 1/6

Enter the numerator of fraction: 1
Enter the denominator of fraction: 6
Egyptian Fraction representation of 1/6 is
1/6

Enter the numerator of fraction: 18
Enter the denominator of fraction: 19
Egyptian Fraction representation of 18/19 is
1/2 + 1/3 + 1/9 + 1/342

Also, read

• Activity Selection Problem using Greedy method in C++
• Find recurring sequence of a fraction in C++