Greedy algorithm for Egyptian fractions: Difference between revisions
Greedy algorithm for Egyptian fractions (view source)
Revision as of 11:29, 11 January 2020
, 4 years agono edit summary
m (→{{header|Phix}}: bugfix) |
No edit summary |
||
Line 199:
Term max is 97/53 with 9 terms
Denominator max is 8/97 with 150 digits 57950...89665</pre>
=={{header|C++}}==
The C++ standard library does not have a "big integer" type, so this solution uses the Boost library.
<lang cpp>#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <boost/multiprecision/cpp_int.hpp>
typedef boost::multiprecision::cpp_int integer;
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 integer_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 = s.substr(0, max_digits/2) + "..." + s.substr(s.length()-max_digits/2);
}
return s;
}
void egyptian(integer x, integer y, std::vector<integer>& result)
{
result.clear();
while (x > 0)
{
integer z = (y + x - 1)/x;
result.push_back(z);
x = mod(-y, x);
y = y * z;
}
}
void print_egyptian(const std::vector<integer>& result)
{
if (result.empty())
return;
auto i = result.begin();
std::cout << "1/" << integer_to_string(*i++);
for (; i != result.end(); ++i)
std::cout << " + 1/" << integer_to_string(*i);
std::cout << "\n\n";
}
void print_egyptian(integer x, integer y)
{
std::cout << "Egyptian fraction for " << x << "/" << y << ": ";
if (x > y)
{
std::cout << "[" << x/y << "] ";
x = x % y;
}
std::vector<integer> result;
egyptian(x ,y, result);
print_egyptian(result);
}
void show_max_terms_and_max_denominator(const integer& limit)
{
size_t max_terms = 0;
std::vector<integer> max_terms_result;
integer max_denominator = 0;
std::vector<integer> max_denominator_result;
std::vector<integer> result;
for (integer b = 2; b < limit; ++b)
{
for (integer a = 1; a < b; ++a)
{
egyptian(a, b, result);
if (result.size() > max_terms)
{
max_terms = result.size();
max_terms_result = result;
}
integer largest_denominator = result.back();
if (largest_denominator > max_denominator)
{
max_denominator = largest_denominator;
max_denominator_result = result;
}
}
}
std::cout << "Proper fractions with most terms and largest denominator, limit = " << limit << ":\n\n";
std::cout << "Most terms (" << max_terms << "): ";
print_egyptian(max_terms_result);
std::cout << "Largest denominator (" << count_digits(max_denominator_result.back()) << " digits): ";
print_egyptian(max_denominator_result);
}
int main()
{
print_egyptian(43, 48);
print_egyptian(5, 121);
print_egyptian(2014, 59);
show_max_terms_and_max_denominator(100);
show_max_terms_and_max_denominator(1000);
return 0;
}
</lang>
{{out}}
<pre>Egyptian fraction for 43/48: 1/2 + 1/3 + 1/16
Egyptian fraction for 5/121: 1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795...3418846225
Egyptian fraction for 2014/59: [34] 1/8 + 1/95 + 1/14947 + 1/670223480
Proper fractions with most terms and largest denominator, limit = 100:
Most terms (8): 1/2 + 1/4 + 1/13 + 1/307 + 1/120871 + 1/20453597227 + 1/6972493991...6783218655 + 1/1458470173...7836808420
Largest denominator (150 digits): 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): 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): 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>
=={{header|Common Lisp}}==
| |||