Greedy algorithm for Egyptian fractions: Difference between revisions
Greedy algorithm for Egyptian fractions (view source)
Revision as of 16:12, 12 December 2023
, 5 months agoAdded link to numberphile video
(add RPL) |
(Added link to numberphile video) |
||
| (5 intermediate revisions by 4 users not shown) | |||
Line 41:
;Also see:
* Wolfram MathWorld™ entry: [http://mathworld.wolfram.com/EgyptianFraction.html Egyptian fraction]
* Numberphile YouTube video: [https://youtu.be/aVUUbNbQkbQ Egyptian Fractions and the Greedy Algorithm]
<br><br>
Line 459 ⟶ 460:
{{libheader|Boost}}
The C++ standard library does not have a "big integer" type, so this solution uses the Boost library.
<syntaxhighlight lang="cpp">#include <
#include <optional>
▲#include <vector>
#include <string>▼
#include <sstream>
#include <
typedef boost::multiprecision::cpp_int integer;
struct fraction {
fraction(const integer& n, const integer& d)
: numerator(n), denominator(d) {}
integer numerator;
integer denominator;
};
integer mod(const integer& x, const integer& y) { return ((x % y) + y) % y; }
size_t count_digits(const integer& i) {
Line 489:
os << i;
std::string s = os.str();
if (s.length() > max_digits)
s.replace(max_digits
return s;
}
Line 503 ⟶ 502:
integer x = f.numerator, y = f.denominator;
while (x > 0) {
integer z = (y + x - 1) / x;
result.emplace_back(1, z);
x = mod(-y, x);
Line 524 ⟶ 523:
integer x = f.numerator, y = f.denominator;
if (x > y) {
std::cout << "[" << x / y << "] ";
x = x % y;
}
Line 557 ⟶ 556:
}
}
std::cout
std::cout << "Most terms (" << max_terms << "): " << max_terms_fraction.value() << " = ";▼
<< limit << ":\n\n";
std::cout << "Most terms (" << max_terms
print_egyptian(max_terms_result);
std::cout << "\nLargest denominator ("
<< " digits): " << max_denominator_fraction.value() << " = ";
print_egyptian(max_denominator_result);
}
Line 1,116 ⟶ 1,119:
{{FormulaeEntry|page=https://formulae.org/?script=examples/Egyptian_fractions}}
'''Solution'''
[[File:Fōrmulæ - Egyptian fractions 01.png]]
'''Test cases part 1'''
[[File:Fōrmulæ - Egyptian fractions 02.png]]
[[File:Fōrmulæ - Egyptian fractions 03.png]]
[[File:Fōrmulæ - Egyptian fractions 04.png]]
[[File:Fōrmulæ - Egyptian fractions 05.png]]
[[File:Fōrmulæ - Egyptian fractions 06.png]]
[[File:Fōrmulæ - Egyptian fractions 07.png]]
'''Test cases part 2'''
[[File:Fōrmulæ - Egyptian fractions 08.png]]
[[File:Fōrmulæ - Egyptian fractions 09.png]]
[[File:Fōrmulæ - Egyptian fractions 10.png]]
[[File:Fōrmulæ - Egyptian fractions 11.png]]
[[File:Fōrmulæ - Egyptian fractions 12.png]]
[[File:Fōrmulæ - Egyptian fractions 13.png]]
[[File:Fōrmulæ - Egyptian fractions 14.png]]
=={{header|Go}}==
Line 2,987 ⟶ 3,024:
</pre>
In algebraic expressions, RPL automatically replaces <code>1/n</code> by <code>INV(n)</code>
====Quest for the largest number of items for proper fractions 2.99/2..99====
≪ '1/1' 0
2 99 '''FOR''' d 2 d 1 - '''FOR''' n
"'" n →STR + "/" + d →STR + "'" + STR→
DUP <span style="color:blue">EGYPF</span> SIZE → f sf
≪ '''IF''' sf OVER > '''THEN''' DROP2 f sf '''END''' ≫
'''NEXT NEXT''' DROP
≫ '<span style="color:blue">TASK</span>'
{{out}}
<pre>
1: '44/53'
</pre>
Limited precision of basic RPL prevents from searching the largest denominator.
=={{header|Ruby}}==
Line 3,719 ⟶ 3,769:
{{libheader|Wren-big}}
We use the BigRat class in the above module to represent arbitrary size fractions.
<syntaxhighlight lang="
var toEgyptianHelper // recursive
| |||