Implementation of Egyptian Fraction using Greedy Algorithm in C++
By Abinash ReddyIn 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
Leave a Reply