Greedy algorithm for Egyptian fractions: Difference between revisions
Greedy algorithm for Egyptian fractions (view source)
Revision as of 20:33, 13 January 2020
, 4 years agoC++ solution writes out numerator and denominator for Egyptian fractions with most terms/largest denominator
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 235 ⟶ 257:
}
{
std::vector<integer> result
while (x > 0)
{
Line 245 ⟶ 267:
y = y * z;
}
}
Line 266 ⟶ 289:
x = x % y;
}
std::vector<integer> result(egyptian(x ,y));
▲ egyptian(x ,y, result);
print_egyptian(result);
}
Line 274 ⟶ 296:
{
size_t max_terms = 0;
integer max_terms_numerator, max_terms_denominator;
integer max_denominator_numerator, max_denominator_denominator;
std::vector<integer> max_terms_result;
integer max_denominator = 0;
std::vector<integer> max_denominator_result;
std::
for (integer b = 2; b < limit; ++b)
{
for (integer a = 1; a < b; ++a)
{
if (fractions.find(r) != fractions.end())
continue;
fractions.insert(r);
std::vector<integer> result = egyptian(a, b);
if (result.size() > max_terms)
{
max_terms = result.size();
max_terms_result = result;
max_terms_numerator = a;
max_terms_denominator = b;
}
integer largest_denominator = result.back();
Line 293 ⟶ 323:
max_denominator = largest_denominator;
max_denominator_result = result;
max_denominator_numerator = a;
max_denominator_denominator = b;
}
}
}
std::cout << "Proper fractions with most terms and largest denominator, limit = " << limit << ":\n\n";
std::cout << "Most terms (" << max_terms << "): "
<< '/' << max_terms_denominator << " = ";
print_egyptian(max_terms_result);
std::cout << "Largest denominator (" << count_digits(
<< max_denominator_numerator << '/' << max_denominator_denominator << " = ";
print_egyptian(max_denominator_result);
}
Line 311 ⟶ 345:
show_max_terms_and_max_denominator(1000);
return 0;
}</lang>▼
▲}
▲</lang>
{{out}}
<pre>
Egyptian fraction for 5/121: 1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795...3418846225
Line 322 ⟶ 357:
Proper fractions with most terms and largest denominator, limit = 100:
Most terms (8): 44/53 = 1/2 + 1/4 + 1/13 + 1/307 + 1/120871 + 1/20453597227 + 1/6972493991...6783218655 + 1/1458470173...7836808420
Largest denominator (150 digits): 8/97 = 1/13 + 1/181 + 1/38041 + 1/1736503177 + 1/3769304102927363485 + 1/1894353789...8154430149 + 1/5382864419...4225813153 + 1/5795045870...3909789665
Proper fractions with most terms and largest denominator, limit = 1000:
Most terms (13): 641/796 = 1/2 + 1/4 + 1/19 + 1/379 + 1/159223 + 1/28520799973 + 1/9296411783...1338400861 + 1/1008271507...4174730681 + 1/1219933718...8484537833 + 1/1860297848...1025882029 + 1/4614277444...8874327093 + 1/3193733450...1456418881 + 1/2039986670...2410165441
Largest denominator (2847 digits): 36/457 = 1/13 + 1/541 + 1/321409 + 1/114781617793 + 1/1482167225...0844346913 + 1/2510651068...4290086881 + 1/7353930250...3326272641 + 1/6489634815...7391865217 + 1/5264420004...5476206145 + 1/3695215730...1238141889 + 1/2048192894...4706590593 + 1/8390188268...5525592705▼
▲Largest denominator (2847 digits): 1/13 + 1/541 + 1/321409 + 1/114781617793 + 1/1482167225...0844346913 + 1/2510651068...4290086881 + 1/7353930250...3326272641 + 1/6489634815...7391865217 + 1/5264420004...5476206145 + 1/3695215730...1238141889 + 1/2048192894...4706590593 + 1/8390188268...5525592705
</pre>
| |||