Greedy algorithm for Egyptian fractions: Difference between revisions
Greedy algorithm for Egyptian fractions (view source)
Revision as of 18:06, 31 March 2019
, 5 years ago→{{header|Go}}
(Added Fōrmulæ) |
|||
Line 397:
The option to show Fōrmulæ programs and their results is showing images. Unfortunately images cannot be uploaded in Rosetta Code.
=={{header|Erlang}}==
<lang erlang>-module(egypt).
-import(lists, [reverse/1, seq/2]).
-export([frac/2, show/2, rosetta/0]).
rosetta() ->
Fractions = [{N, D, second(frac(N, D))} || N <- seq(2,99), D <- seq(N+1, 99)],
{Longest, A1, B1} = findmax(fun length/1, Fractions),
io:format("~b/~b has ~b terms.~n", [A1, B1, Longest]),
{Largest, A2, B2} = findmax(fun (L) -> hd(reverse(L)) end, Fractions),
io:format("~b/~b has a really long denominator. (~b)~n", [A2, B2, Largest]).
second({_, B}) -> B.
findmax(Fn, L) -> findmax(Fn, L, 0, 0, 0).
findmax(_, [], M, A, B) -> {M, A, B};
findmax(Fn, [{A,B,Frac}|Fracs], M, A0, B0) ->
Val = Fn(Frac),
case Val > M of
true -> findmax(Fn, Fracs, Val, A, B);
false -> findmax(Fn, Fracs, M, A0, B0)
end.
show(A, B) ->
{W, R} = frac(A, B),
case W of
0 -> ok;
_ -> io:format("[~b] ", [W])
end,
case R of
[] -> ok;
[D0|Ds] ->
io:format("1/~b ", [D0]),
[io:format("+ 1/~b ", [D]) || D <- Ds],
ok
end.
frac(A, B) ->
{A div B, reverse(proper(A rem B, B, []))}.
proper(0, _, L) -> L;
proper(1, Y, L) -> [Y|L];
proper(X, Y, L) ->
D = ceildiv(Y, X),
X2 = mod(-Y, X),
Y2 = Y*ceildiv(Y, X),
proper(X2, Y2, [D|L]).
ceildiv(A, B) ->
Q = A div B,
case A rem B of
0 -> Q;
_ -> Q+1
end.
mod(A, M) ->
B = A rem M,
if
B < 0 -> B + M;
true -> B
end.
</lang>
{{out}}
<pre>
129> egypt:show(43,48).
1/2 + 1/3 + 1/16 ok
130> egypt:show(5,121).
1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795642093418846225 ok
131> egypt:show(2014,59).
[34] 1/8 + 1/95 + 1/14947 + 1/670223480 ok
132> egypt:rosetta().
8/97 has 8 terms.
8/97 has a really long denominator. (579504587067542801713103191859918608251030291952195423583529357653899418686342360361798689053273749372615043661810228371898539583862011424993909789665)
ok
</pre>
=={{header|Go}}==
| |||