Dividir la fracción en suma de múltiples fracciones con numerador 1

Dados dos números enteros positivos N y D que representan una fracción como N/D , la tarea es dividir la fracción en la suma de varias fracciones cuyo numerador es 1 .

Ejemplos: 

Entrada: n = 4, d = 5
Salida: 1/2, 1/4, 1/20
Explicación: 1/2 + 1/4 + 1/20 = 4/5

Entrada: n = 15, d = 16
Salida: 1/2, 1/3, 1/10, 1/240

Enfoque: La idea es que todas las fracciones positivas de la forma n/d se pueden escribir como una suma de distintas fracciones unitarias . La respuesta se puede encontrar eliminando la fracción unitaria más grande 1/x hasta que la fracción llegue a cero , donde x se puede encontrar como ceil (d/n). Después de encontrar la fracción unitaria, actualice la fracción a n/d – 1/x para que n cambie a nx-d y d cambie a dx en cada paso.

A continuación se muestra la implementación del enfoque anterior: 

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to split the fraction into
// distinct unit fraction
vector<string> FractionSplit(long long n, long long d)
{
 
    // To store answer
    vector<string> UnitFactions;
 
    // While numerator is positive
    while (n > 0) {
 
        // Finding x = ceil(d/n)
        long long x = (d + n - 1) / n;
 
        // Add 1/x to list of ans
        string s = "1/" + to_string(x);
        UnitFactions.push_back(s);
 
        // Update fraction
        n = n * x - d;
        d = d * x;
    }
    return UnitFactions;
}
 
// Driver Code
int main()
{
    // Given Input
    long long n = 13, d = 18;
 
    // Function Call
    auto res = FractionSplit(n, d);
 
    // Print Answer
    for (string s : res)
        cout << s << ", ";
 
    return 0;
}

// Java program for the above approach
import java.util.Vector;
 
public class GFG {
 
    // Function to split the fraction into
    // distinct unit fraction
    static Vector<String> FractionSplit(long n, long d)
    {
 
        // To store answer
        Vector<String> UnitFactions = new Vector<>();
 
        // While numerator is positive
        while (n > 0) {
 
            // Finding x = ceil(d/n)
            long x = (d + n - 1) / n;
 
            // Add 1/x to list of ans
            String s = "1/" + String.valueOf(x);
            UnitFactions.add(s);
 
            // Update fraction
            n = n * x - d;
            d = d * x;
        }
        return UnitFactions;
    }
 
    // Driver code
    public static void main(String[] args)
    {
       
        // Given Input
        long n = 13, d = 18;
 
        // Function Call
        Vector<String> res = FractionSplit(n, d);
 
        // Print Answer
        for (String s : res)
            System.out.print(s + ", ");
    }
}
 
// This code is contributed by abhinavjain194

# Python program for the above approach
 
# Function to split the fraction into
# distinct unit fraction
def FractionSplit(n, d):
 
    # To store answer
    UnitFactions = []
 
    # While numerator is positive
    while (n > 0):
 
        # Finding x = ceil(d/n)
        x = (d + n - 1) // n
 
        # Add 1/x to list of ans
        s = "1/" + str(x)
        UnitFactions.append(s);
 
        # Update fraction
        n = n * x - d;
        d = d * x
    return UnitFactions;
 
# Driver Code
 
# Given Input
n = 13;
d = 18;
 
# Function Call
res = FractionSplit(n, d);
 
# Print Answer
for s in res:
    print(s + ", ", end=" ");
 
# This code is contributed by _saurabh_jaiswal

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to split the fraction into
// distinct unit fraction
static List<string> FractionSplit(long n, long d)
{
     
    // To store answer
    List<string> UnitFactions = new List<string>();
 
    // While numerator is positive
    while (n > 0)
    {
         
        // Finding x = ceil(d/n)
        long x = (d + n - 1) / n;
 
        // Add 1/x to list of ans
        string s = "1/" + x.ToString();
        UnitFactions.Add(s);
 
        // Update fraction
        n = n * x - d;
        d = d * x;
    }
    return UnitFactions;
}
 
// Driver code
public static void Main(string[] args)
{
     
    // Given Input
    long n = 13, d = 18;
 
    // Function Call
    List<string> res = FractionSplit(n, d);
 
    // Print Answer
    foreach(string s in res)
        Console.Write(s + ", ");
}
}
 
// This code is contributed by ukasp

<script>
// Javascript program for the above approach
 
// Function to split the fraction into
// distinct unit fraction
function FractionSplit(n, d) {
 
    // To store answer
    let UnitFactions = [];
 
    // While numerator is positive
    while (n > 0) {
 
        // Finding x = ceil(d/n)
        let x = Math.floor((d + n - 1) / n);
 
        // Add 1/x to list of ans
        let s = "1/" + String(x);
        UnitFactions.push(s);
 
        // Update fraction
        n = n * x - d;
        d = d * x;
    }
    return UnitFactions;
}
 
// Driver Code
 
// Given Input
let n = 13, d = 18;
 
// Function Call
let res = FractionSplit(n, d);
 
// Print Answer
for (let s of res)
    document.write(s + ", ");
 
// This code is contributed by gfgking.
</script>

1/2, 1/5, 1/45, 

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)