Algoritmo codicioso para la fracción egipcia

Cada fracción positiva se puede representar como una suma de fracciones unitarias únicas. Una fracción es una fracción unitaria si el numerador es 1 y el denominador es un número entero positivo, por ejemplo, 1/3 es una fracción unitaria. Tal representación se llama fracción egipcia, ya que fue utilizada por los antiguos egipcios. 
Los siguientes son algunos ejemplos: 
 

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

Podemos generar fracciones egipcias usando el algoritmo codicioso . Para un número dado de la forma ‘nr/dr’ donde dr > nr, primero encuentra la fracción unitaria más grande posible, luego repite para la parte restante. Por ejemplo, considere 6/14, primero encontramos el techo de 14/6, es decir, 3. Entonces, la primera fracción unitaria se convierte en 1/3, luego recurre a (6/14 – 1/3), es decir, 4/42. 
A continuación se muestra la implementación de la idea anterior.
 

// C++ program to print a fraction in Egyptian Form using Greedy
// Algorithm
#include <iostream>
using namespace std;
  
void printEgyptian(int nr, int dr)
{
    // If either numerator or denominator is 0
    if (dr == 0 || nr == 0)
        return;
  
    // If numerator divides denominator, then simple division
    // makes the fraction in 1/n form
    if (dr%nr == 0)
    {
        cout << "1/" << dr/nr;
        return;
    }
  
    // If denominator divides numerator, then the given number
    // is not fraction
    if (nr%dr == 0)
    {
        cout << nr/dr;
        return;
    }
  
    // If numerator is more than denominator
    if (nr > dr)
    {
        cout << nr/dr << " + ";
        printEgyptian(nr%dr, dr);
        return;
    }
  
    // We reach here dr > nr and dr%nr is non-zero
    // Find ceiling of dr/nr and print it as first
    // fraction
    int n = dr/nr + 1;
    cout << "1/" << n << " + ";
  
    // Recur for remaining part
    printEgyptian(nr*n-dr, dr*n);
 }
  
// Driver Program
int main()
{
    int nr = 6, dr = 14;
    cout << "Egyptian Fraction Representation of "
         << nr << "/" << dr << " is\n ";
    printEgyptian(nr, dr);
    return 0;
}

//Java program to print a fraction 
// in Egyptian Form using Greedy 
// Algorithm 
  
class GFG {
  
    static void printEgyptian(int nr, int dr) {
        // If either numerator or 
        // denominator is 0 
        if (dr == 0 || nr == 0) {
            return;
        }
  
        // If numerator divides denominator, 
        // then simple division makes 
        // the fraction in 1/n form 
        if (dr % nr == 0) {
            System.out.print("1/" + dr / nr);
            return;
        }
  
        // If denominator divides numerator, 
        // then the given number is not fraction 
        if (nr % dr == 0) {
            System.out.print(nr / dr);
            return;
        }
  
        // If numerator is more than denominator 
        if (nr > dr) {
            System.out.print(nr / dr + " + ");
            printEgyptian(nr % dr, dr);
            return;
        }
  
        // We reach here dr > nr and dr%nr 
        // is non-zero. Find ceiling of 
        // dr/nr and print it as first 
        // fraction 
        int n = dr / nr + 1;
        System.out.print("1/" + n + " + ");
  
        // Recur for remaining part 
        printEgyptian(nr * n - dr, dr * n);
    }
  
// Driver Code 
    public static void main(String[] args) {
        int nr = 6, dr = 14;
        System.out.print("Egyptian Fraction Representation of "
                + nr + "/" + dr + " is\n ");
        printEgyptian(nr, dr);
    }
}
  
/*This code is contributed by Rajput-Ji*/

# Python3 program to print a fraction 
# in Egyptian Form using Greedy
# Algorithm
  
# import math package to use
# ceiling function
import math
  
# define a function egyptianFraction 
# which receive parameter nr as
# numerator and dr as denominator
def egyptianFraction(nr, dr):
  
    print("The Egyptian Fraction " +
          "Representation of {0}/{1} is".
                format(nr, dr), end="\n")
  
    # empty list ef to store
    # denominator
    ef = []
  
    # while loop runs until 
    # fraction becomes 0 i.e,
    # numerator becomes 0
    while nr != 0:
  
        # taking ceiling
        x = math.ceil(dr / nr)
  
        # storing value in ef list
        ef.append(x)
  
        # updating new nr and dr
        nr = x * nr - dr
        dr = dr * x
  
    # printing the values
    for i in range(len(ef)):
        if i != len(ef) - 1:
            print(" 1/{0} +" . 
                    format(ef[i]), end = " ")
        else:
            print(" 1/{0}" .
                    format(ef[i]), end = " ")
  
# calling the function
egyptianFraction(6, 14)
  
# This code is contributed 
# by Anubhav Raj Singh

// C# program to print a fraction 
// in Egyptian Form using Greedy
// Algorithm
using System;
  
class GFG
{
static void printEgyptian(int nr, int dr)
{
    // If either numerator or
    // denominator is 0
    if (dr == 0 || nr == 0)
        return;
  
    // If numerator divides denominator, 
    // then simple division  makes
    // the fraction in 1/n form
    if (dr % nr == 0)
    {
        Console.Write("1/" + dr / nr);
        return;
    }
  
    // If denominator divides numerator, 
    // then the given number is not fraction
    if (nr % dr == 0)
    {
        Console.Write(nr / dr);
        return;
    }
  
    // If numerator is more than denominator
    if (nr > dr)
    {
        Console.Write(nr / dr + " + ");
        printEgyptian(nr % dr, dr);
        return;
    }
  
    // We reach here dr > nr and dr%nr
    // is non-zero. Find ceiling of
    // dr/nr and print it as first
    // fraction
    int n = dr / nr + 1;
    Console.Write("1/" + n + " + ");
  
    // Recur for remaining part
    printEgyptian(nr * n - dr, dr * n);
}
  
// Driver Code
public static void Main()
{
    int nr = 6, dr = 14;
    Console.Write( "Egyptian Fraction Representation of " +
                                 nr + "/" + dr + " is\n ");
    printEgyptian(nr, dr);
}
}
  
// This code is contributed 
// by Akanksha Rai(Abby_akku)

<?php
// PHP program to print a fraction 
// in Egyptian Form using Greedy
// Algorithm
  
function printEgyptian($nr, $dr)
{
    // If either numerator or 
    // denominator is 0
    if ($dr == 0 || $nr == 0)
        return;
  
    // If numerator divides denominator, 
    // then simple division makes the 
    // fraction in 1/n form
    if ($dr % $nr == 0)
    {
        echo "1/", (int)$dr / $nr;
        return;
    }
  
    // If denominator divides numerator, 
    // then the given number is not fraction
    if ($nr%$dr == 0)
    {
        echo (int)($nr / $dr);
        return;
    }
  
    // If numerator is more than denominator
    if ($nr > $dr)
    {
        echo (int)($nr/$dr), " + ";
        printEgyptian($nr % $dr, $dr);
        return;
    }
  
    // We reach here dr > nr and dr%nr is 
    // non-zero. Find ceiling of dr/nr and 
    // print it as first fraction
    $n = (int)($dr / $nr ) + 1;
    echo "1/" , $n , " + ";
  
    // Recur for remaining part
    printEgyptian($nr * $n - $dr, $dr * $n);
}
  
// Driver Code
$nr = 6;
$dr = 14;
echo "Egyptian Fraction Representation of ",
                    $nr, "/", $dr, " is\n ";
printEgyptian($nr, $dr);
      
// This code is contributed by ajit.
?>

<script>
    // Javascript program to print a fraction 
    // in Egyptian Form using Greedy
    // Algorithm
      
    function printEgyptian(nr, dr)
    {
        // If either numerator or
        // denominator is 0
        if (dr == 0 || nr == 0)
            return;
  
        // If numerator divides denominator, 
        // then simple division  makes
        // the fraction in 1/n form
        if (dr % nr == 0)
        {
            document.write("1/" + parseInt(dr / nr, 10));
            return;
        }
  
        // If denominator divides numerator, 
        // then the given number is not fraction
        if (nr % dr == 0)
        {
            document.write(parseInt(nr / dr, 10));
            return;
        }
  
        // If numerator is more than denominator
        if (nr > dr)
        {
            document.write(parseInt(nr / dr, 10) + " + ");
            printEgyptian(nr % dr, dr);
            return;
        }
  
        // We reach here dr > nr and dr%nr
        // is non-zero. Find ceiling of
        // dr/nr and print it as first
        // fraction
        let n = parseInt(dr / nr, 10) + 1;
        document.write("1/" + n + " + ");
  
        // Recur for remaining part
        printEgyptian(nr * n - dr, dr * n);
    }
      
      let nr = 6, dr = 14;
    document.write( "Egyptian Fraction Representation of " + nr + "/" + dr + " is\n ");
    printEgyptian(nr, dr);
  
// This code is contributed by divyeshrabadiya07.
</script>

import math
  
def getEgyptianFraction(numerator,denominator):
    str = ""
    output = getEgyptianFractionUtil(numerator,denominator,[])
    for denom in output:
        str += "1/{0} + ".format(denom);
    strCopy = str[:-3] #removing the last + sign
    return strCopy
  
def getEgyptianFractionUtil(numerator,denominator,listOfDenoms):
    if numerator == 0:
        return listOfDenoms
    newDenom = math.ceil(denominator/numerator);
    #append in output list
    listOfDenoms.append(newDenom);
    listOfDenoms = getEgyptianFractionUtil(numerator*newDenom - denominator,
                                          newDenom*denominator,listOfDenoms);
    return listOfDenoms
  
print(getEgyptianFraction(6,14))
  # Code contributed by 
  # Mayur Sonowal