Rosetta Code

Greedy algorithm for Egyptian fractions: Difference between revisions

Page Discussion

Greedy algorithm for Egyptian fractions (view source)

Revision as of 20:38, 13 January 2020

626 bytes removed ,  4 years ago
m
→‎{{header|C++}}
m (C++ solution writes out numerator and denominator for Egyptian fractions with most terms/largest denominator)
Line 202:
=={{header|C++}}==
The C++ standard library does not have a "big integer" type, so this solution uses the Boost library.
<lang cpp><lang cpp>#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <set>
#include <boost/multiprecision/cpp_int.hpp>
 
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)
Line 257 ⟶ 236:
}
 
std::vector<integer>void egyptian(integer x, integer y, std::vector<integer>& result)
{
std::vector<integer> result.clear();
while (x > 0)
{
Line 267 ⟶ 246:
y = y * z;
}
return result;▼
}
 
Line 289 ⟶ 267:
x = x % y;
}
std::vector<integer> result(egyptian(x ,y));
▲ returnegyptian(x, y, result);
print_egyptian(result);
}
Line 301 ⟶ 280:
integer max_denominator = 0;
std::vector<integer> max_denominator_result;
std::setvector<rationalinteger> fractionsresult;
for (integer b = 2; b < limit; ++b)
{
for (integer a = 1; a < b; ++a)
{
rational regyptian(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)
{
Simonjsaunders
1,777

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/245583"