Greedy algorithm for Egyptian fractions: Difference between revisions
Content added Content deleted
m (→{{header|Phix}}: bugfix) |
No edit summary |
||
Line 199: | Line 199: | ||
Term max is 97/53 with 9 terms |
Term max is 97/53 with 9 terms |
||
Denominator max is 8/97 with 150 digits 57950...89665</pre> |
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}}== |
=={{header|Common Lisp}}== |