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
Leave a Reply