How to resolve the algorithm Greedy algorithm for Egyptian fractions step by step in the C++ programming language

Published on 7 June 2024 03:52 AM
#cpp

How to resolve the algorithm Greedy algorithm for Egyptian fractions step by step in the C++ programming language

Table of Contents

Problem Statement

An   Egyptian fraction   is the sum of distinct unit fractions such as: Each fraction in the expression has a numerator equal to   1   (unity)   and a denominator that is a positive integer,   and all the denominators are distinct   (i.e., no repetitions).
Fibonacci's   Greedy algorithm for Egyptian fractions   expands the fraction

x y

{\displaystyle {\tfrac {x}{y}}}

to be represented by repeatedly performing the replacement

(simplifying the 2nd term in this replacement as necessary, and where

⌈ x ⌉

{\displaystyle \lceil x\rceil }

is the   ceiling   function).

For this task,   Proper and improper fractions   must be able to be expressed.

Proper  fractions   are of the form

a b

{\displaystyle {\tfrac {a}{b}}}

where

a

{\displaystyle a}

and

b

{\displaystyle b}

are positive integers, such that

a < b

{\displaystyle a<b}

,     and improper fractions are of the form

a b

{\displaystyle {\tfrac {a}{b}}}

where

a

{\displaystyle a}

and

b

{\displaystyle b}

are positive integers, such that   a ≥ b.

(See the REXX programming example to view one method of expressing the whole number part of an improper fraction.) For improper fractions, the integer part of any improper fraction should be first isolated and shown preceding the Egyptian unit fractions, and be surrounded by square brackets [n].

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Greedy algorithm for Egyptian fractions step by step in the C++ programming language

This C++ program demonstrates Egyptian fractions, which are sums of unit fractions (fractions with a numerator of 1). It calculates and displays Egyptian fractions for given fractions and also finds the proper fraction with the most terms and the largest denominator within a specified limit.

Here's a breakdown of the code:

  1. Header Inclusions:

    • The program includes necessary headers:
      • <boost/multiprecision/cpp_int.hpp>: For handling large integer values.
      • <iostream>: For input/output.
      • <optional>: For handling optional values.
      • <sstream>: For string manipulations.
      • <string>: For string handling.
      • <vector>: For storing collections of fractions.

  2. Type Definitions:

    • typedef boost::multiprecision::cpp_int integer;: Defines integer as a type alias for Boost's high-precision integer type cpp_int.

  3. fraction Struct:

    • This struct represents fractions with numerator and denominator as integer members. It provides an operator for displaying fractions in the format "numerator/denominator."

  4. Helper Functions:

    • mod(const integer& x, const integer& y): Calculates the modulo operation x % y and ensures the result is non-negative.
    • count_digits(const integer& i): Counts the number of digits in the decimal representation of i.
    • to_string(const integer& i): Converts i to a string.
    • operator<<(std::ostream& out, const fraction& f): Overloads the << operator to print fractions in "numerator/denominator" format.

  5. Egyptian Fraction Calculation:

    • egyptian(const fraction& f, std::vector<fraction>& result):
      • Calculates the Egyptian fraction representation of f.
      • It follows the Euclidean algorithm to decompose f into a sum of unit fractions and stores the result in the result vector.

  6. Output Functions:

    • print_egyptian(const std::vector<fraction>& result): Prints the Egyptian fraction representation as a sum of unit fractions.
    • print_egyptian(const fraction& f):
      • Calculates and prints the Egyptian fraction representation of f.
      • It handles cases where the numerator is larger than the denominator and prints the integer part separately.

  7. Main Function:

    • show_max_terms_and_max_denominator(const integer& limit):
      • Finds the proper fraction within the given limit with the most terms and largest denominator.
      • It iterates through proper fractions, calculates Egyptian fractions, and keeps track of the ones with the most terms and largest denominators.

  8. Main Calculations:

    • The program calculates and displays Egyptian fractions for specific examples and then finds the proper fractions with the most terms and largest denominators within limits of 100 and 1000.

In summary, this program demonstrates the calculation and representation of Egyptian fractions for various input fractions. It also performs analysis to find fractions with specific characteristics within numerical limits.

Source code in the cpp programming language

#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>
#include <optional>
#include <sstream>
#include <string>
#include <vector>

typedef boost::multiprecision::cpp_int integer;

struct fraction {
    fraction(const integer& n, const integer& d)
        : numerator(n), denominator(d) {}
    integer numerator;
    integer denominator;
};

integer mod(const integer& x, const integer& y) { return ((x % y) + y) % y; }

size_t count_digits(const integer& i) {
    std::ostringstream os;
    os << i;
    return os.str().length();
}

std::string to_string(const integer& i) {
    const int max_digits = 20;
    std::ostringstream os;
    os << i;
    std::string s = os.str();
    if (s.length() > max_digits)
        s.replace(max_digits / 2, s.length() - max_digits, "...");
    return s;
}

std::ostream& operator<<(std::ostream& out, const fraction& f) {
    return out << to_string(f.numerator) << '/' << to_string(f.denominator);
}

void egyptian(const fraction& f, std::vector<fraction>& result) {
    result.clear();
    integer x = f.numerator, y = f.denominator;
    while (x > 0) {
        integer z = (y + x - 1) / x;
        result.emplace_back(1, z);
        x = mod(-y, x);
        y = y * z;
    }
}

void print_egyptian(const std::vector<fraction>& result) {
    if (result.empty())
        return;
    auto i = result.begin();
    std::cout << *i++;
    for (; i != result.end(); ++i)
        std::cout << " + " << *i;
    std::cout << '\n';
}

void print_egyptian(const fraction& f) {
    std::cout << "Egyptian fraction for " << f << ": ";
    integer x = f.numerator, y = f.denominator;
    if (x > y) {
        std::cout << "[" << x / y << "] ";
        x = x % y;
    }
    std::vector<fraction> result;
    egyptian(fraction(x, y), result);
    print_egyptian(result);
    std::cout << '\n';
}

void show_max_terms_and_max_denominator(const integer& limit) {
    size_t max_terms = 0;
    std::optional<fraction> max_terms_fraction, max_denominator_fraction;
    std::vector<fraction> max_terms_result;
    integer max_denominator = 0;
    std::vector<fraction> max_denominator_result;
    std::vector<fraction> result;
    for (integer b = 2; b < limit; ++b) {
        for (integer a = 1; a < b; ++a) {
            fraction f(a, b);
            egyptian(f, result);
            if (result.size() > max_terms) {
                max_terms = result.size();
                max_terms_result = result;
                max_terms_fraction = f;
            }
            const integer& denominator = result.back().denominator;
            if (denominator > max_denominator) {
                max_denominator = denominator;
                max_denominator_result = result;
                max_denominator_fraction = f;
            }
        }
    }
    std::cout
        << "Proper fractions with most terms and largest denominator, limit = "
        << limit << ":\n\n";
    std::cout << "Most terms (" << max_terms
              << "): " << max_terms_fraction.value() << " = ";
    print_egyptian(max_terms_result);
    std::cout << "\nLargest denominator ("
              << count_digits(max_denominator_result.back().denominator)
              << " digits): " << max_denominator_fraction.value() << " = ";
    print_egyptian(max_denominator_result);
}

int main() {
    print_egyptian(fraction(43, 48));
    print_egyptian(fraction(5, 121));
    print_egyptian(fraction(2014, 59));
    show_max_terms_and_max_denominator(100);
    show_max_terms_and_max_denominator(1000);
    return 0;
}

You may also check:How to resolve the algorithm Averages/Root mean square step by step in the ALGOL-M programming language
You may also check:How to resolve the algorithm Dragon curve step by step in the M2000 Interpreter programming language
You may also check:How to resolve the algorithm Magnanimous numbers step by step in the Sidef programming language
You may also check:How to resolve the algorithm Sorting algorithms/Bead sort step by step in the PowerShell programming language
You may also check:How to resolve the algorithm Infinity step by step in the Mathematica / Wolfram Language programming language