Greedy algorithm for Egyptian fractions: Difference between revisions

Content added Content deleted
m (C++ solution writes out numerator and denominator for Egyptian fractions with most terms/largest denominator)
Line 202: Line 202:
=={{header|C++}}==
=={{header|C++}}==
The C++ standard library does not have a "big integer" type, so this solution uses the Boost library.
The C++ standard library does not have a "big integer" type, so this solution uses the Boost library.
<lang cpp><lang cpp>#include <iostream>
<lang cpp>#include <iostream>
#include <vector>
#include <vector>
#include <algorithm>
#include <algorithm>
#include <string>
#include <string>
#include <sstream>
#include <sstream>
#include <set>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_int.hpp>


typedef boost::multiprecision::cpp_int integer;
typedef boost::multiprecision::cpp_int integer;

struct rational
{
integer numerator_;
integer denominator_;
rational(const integer& n, const integer& d) : numerator_(n), denominator_(d)
{
}
};

std::ostream& operator<<(std::ostream& os, const rational& r)
{
os << r.numerator_ << '/' << r.denominator_;
return os;
}

bool operator<(const rational& a, const rational& b)
{
return a.numerator_ * b.denominator_ < b.numerator_ * a.denominator_;
}


integer mod(const integer& x, const integer& y)
integer mod(const integer& x, const integer& y)
Line 257: Line 236:
}
}


std::vector<integer> egyptian(integer x, integer y)
void egyptian(integer x, integer y, std::vector<integer>& result)
{
{
std::vector<integer> result;
result.clear();
while (x > 0)
while (x > 0)
{
{
Line 267: Line 246:
y = y * z;
y = y * z;
}
}
⚫
return result;
}
}


Line 289: Line 267:
x = x % y;
x = x % y;
}
}
std::vector<integer> result(egyptian(x ,y));
std::vector<integer> result;
⚫
egyptian(x, y, result);
print_egyptian(result);
print_egyptian(result);
}
}
Line 301: Line 280:
integer max_denominator = 0;
integer max_denominator = 0;
std::vector<integer> max_denominator_result;
std::vector<integer> max_denominator_result;
std::set<rational> fractions;
std::vector<integer> result;
for (integer b = 2; b < limit; ++b)
for (integer b = 2; b < limit; ++b)
{
{
for (integer a = 1; a < b; ++a)
for (integer a = 1; a < b; ++a)
{
{
rational r(a, b);
egyptian(a, b, result);
if (fractions.find(r) != fractions.end())
continue;
fractions.insert(r);
std::vector<integer> result = egyptian(a, b);
if (result.size() > max_terms)
if (result.size() > max_terms)
{
{
Retrieved from "https://rosettacode.org/wiki/Greedy_algorithm_for_Egyptian_fractions"