C++ Greedy Approach-Egyptian Fractions














































C++ Greedy Approach-Egyptian Fractions




Greedy Approach For Egyptain Fractions:
An Egyptian fraction is the sum of finitely many rational numbers, each of which can be expressed in the form
1/q where q is an integer.
For example, the Egyptian fraction 61/66 is written as 1/2 + 1/3 + 1/11 

Every positive fraction can be represented as sum of unique unit fractions. A fraction is unit fraction if numerator is 1 and denominator is a positive integer, for example 1/3 is a unit fraction. Such a representation is called Egyptian Fraction as it was used by ancient Egyptians.

Following are few examples:

Egyptian Fraction Representation of 2/3 is 1/2 + 1/6
Egyptian Fraction Representation of 6/14 is 1/3 + 1/11 + 1/231
Egyptian Fraction Representation of 12/13 is 1/2 + 1/3 + 1/12 + 1/156

We can generate Egyptian Fractions using Greedy Algorithm. For a given number of the form nr/dr where dr > nr, first find the greatest possible unit fraction, then recur for the remaining part. For example, consider 6/14, we first find ceiling of 14/6, i.e., 3. So the first unit fraction becomes 1/3, then recur for (6/14 %u2013 1/3) i.e., 4/42.

Find the Egyptian fraction representation of 8/9 

The greatest unit fraction less than 8/9 is 1/2.

The remainder is 7/18 

The greatest unit fraction less than 7/18 is 1/3.

The remainder is 1/18.

This is a unit fraction, so the answer is given by 

       7/18= 1/2 + 1/3 + 1/18 

// C++ program to print a fraction in Egyptian Form using Greedy

// Algorithm

#include <iostream>

using namespace std;

 

void findEgyptian(int nr, int dr)

{

    

    if (dr == 0 || nr == 0)

        return;

 

    

    if (dr%nr == 0)

    {

        cout << "1/" << dr/nr;

        return;

    }

 

    

    if (nr%dr == 0)

    {

        cout << nr/dr;

        return;

    }

 

    

    if (nr > dr)

    {

        cout << nr/dr << " + ";

        findEgyptian(nr%dr, dr);

        return;

    }

 

    

    int n = dr/nr + 1;

    cout << "1/" << n << " + ";

    findEgyptian(nr*n-dr,dr*n);

   }

  int main(){

    int nr=6,dr=14;

    cout<<"Egyptian Fraction Representation of"<<nr<<"/"<<dr<<" is \n";


More Articles of M Mounika:

Name Views Likes
C++ Segmented Sieve (Print Primes In a Range) 162 0
C++ Sieve Of Erastosthenes 135 0
C++ Gold Mine Problem 295 0
C++ Merge K Sorted Arrays 117 0
C++ K Centers Problem 240 0
C++ Find Nth Catalan Number 311 0
C++ Inplace Rotate square matrix by 90 degrees 285 0
C++ Find Non Repeating Elements in Array 87 0
C++ Merge Two Binary Trees 120 0
C++ Sum of Numbers From Root To Leaf Paths 89 0
C++ Meta Strings 91 0
C++ Flood Fill Algorithm 402 0
C++ smallest substring with maximum distinct characters 199 0
C++ Smallest window with all characters in string 93 0
C++ Minimum Removal of Characters from string to make its permutation as palindrome 87 0
C++ Minimum characters added at front of string in palindrome conversion 69 0
C++ Number of Bracket Reversals needed to make expression Balanced 72 0
C++ String to Palindrome with Append Function 83 0
C++ WildCard pattern matching 75 0
C++ Anagram substring Search 72 0
C++ Manachars Algorithm 74 0
C++ Search String in Grid 83 0
C++ String Matching(Z Algorithm) 67 0
C++ String Matching(Naive Algorithm) 113 0
C++ String Matching(KMP Algorithm) 140 0
C++ Remove Duplicates From String 110 0
C++ Basics of String Manipulation 85 1
C++ Disjoint Data Structure Cycle Detection 86 0
C++ Problem On Disjoint Data Structures 95 0
C++ Disjoint Data Structures Part3 79 0
Disjoint Data Structures Part2 90 0
Disjoint Data Structures 93 1
C++ Segment Trees 321 2
C++ Trie Cost of Data 290 1
C++ Trie Datastructure 279 1
C++ Greedy Approach Minimum number of coins 526 0
C++ Greedy Approach Maximum height Pyramid 328 1
C++ Greedy Approach String lexicographically largest subsequence 246 0
C++ Greedy Approach Lexicographically largest subsequence 364 0
C++ Greedy Approach Prims MST 398 1
C++ Greedy Approach Krushkals MST 458 1
C++ Greedy Approach N-array maximum sum 333 1
C++ Greedy Approach Policemen Catch Thieves 563 1
C++ Greedy Approach Maximum product Subset 546 1
C++ Greedy Approach Minimum Product Subset 348 1
C++ Greedy Approach Fractional Knapsack 737 1
C++ Greedy Approach-Activity Selection Problem 745 1
C++ Greedy Approach-Egyptian Fractions 640 0
C++ Greedy Approach-Huffman Codes 1031 1
C++ Introduction to Greedy Approach 955 2

Comments