Greedy algorithm for Egyptian fractions: Difference between revisions
Greedy algorithm for Egyptian fractions (view source)
Revision as of 23:10, 7 April 2020
, 4 years ago→{{header|C sharp|C#}}
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
|||
Line 42:
* Wolfram MathWorld™ entry: [http://mathworld.wolfram.com/EgyptianFraction.html Egyptian fraction]
<br><br>
=={{header|C}}==
Output has limited accuracy as noted by comments. The problem requires bigint support to be completely accurate.
<lang c>#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
typedef int64_t integer;
struct Pair {
integer md;
int tc;
};
integer mod(integer x, integer y) {
return ((x % y) + y) % y;
}
integer gcd(integer a, integer b) {
if (0 == a) return b;
if (0 == b) return a;
if (a == b) return a;
if (a > b) return gcd(a - b, b);
return gcd(a, b - a);
}
void write0(bool show, char *str) {
if (show) {
printf(str);
}
}
void write1(bool show, char *format, integer a) {
if (show) {
printf(format, a);
}
}
void write2(bool show, char *format, integer a, integer b) {
if (show) {
printf(format, a, b);
}
}
struct Pair egyptian(integer x, integer y, bool show) {
struct Pair ret;
integer acc = 0;
bool first = true;
ret.tc = 0;
ret.md = 0;
write2(show, "Egyptian fraction for %lld/%lld: ", x, y);
while (x > 0) {
integer z = (y + x - 1) / x;
if (z == 1) {
acc++;
} else {
if (acc > 0) {
write1(show, "%lld + ", acc);
first = false;
acc = 0;
ret.tc++;
} else if (first) {
first = false;
} else {
write0(show, " + ");
}
if (z > ret.md) {
ret.md = z;
}
write1(show, "1/%lld", z);
ret.tc++;
}
x = mod(-y, x);
y = y * z;
}
if (acc > 0) {
write1(show, "%lld", acc);
ret.tc++;
}
write0(show, "\n");
return ret;
}
int main() {
struct Pair p;
integer nm = 0, dm = 0, dmn = 0, dmd = 0, den = 0;;
int tm, i, j;
egyptian(43, 48, true);
egyptian(5, 121, true); // final term cannot be represented correctly
egyptian(2014, 59, true);
tm = 0;
for (i = 1; i < 100; i++) {
for (j = 1; j < 100; j++) {
p = egyptian(i, j, false);
if (p.tc > tm) {
tm = p.tc;
nm = i;
dm = j;
}
if (p.md > den) {
den = p.md;
dmn = i;
dmd = j;
}
}
}
printf("Term max is %lld/%lld with %d terms.\n", nm, dm, tm); // term max is correct
printf("Denominator max is %lld/%lld\n", dmn, dmd); // denominator max is not correct
egyptian(dmn, dmd, true); // enough digits cannot be represented without bigint
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/1025410058030422033
Egyptian fraction for 2014/59: 34 + 1/8 + 1/95 + 1/14947 + 1/670223480
Term max is 97/53 with 9 terms.
Denominator max is 69/97
Egyptian fraction for 69/97: 1/2 + 1/5 + 1/89 + 1/9593 + 1/118309099 + 1/32659766662805104 + 1/2591418766870639376</pre>
=={{header|C sharp|C#}}==
| |||