Anonymous user
Count the coins: Difference between revisions
Added more efficient version, also inspired by a Haskell version
(Added Tailspin solution) |
(Added more efficient version, also inspired by a Haskell version) |
||
Line 160:
{{works with|ALGOL 68G|Any - tested with release 2.4.1}}
{{trans|Haskell}}
<lang Algol68>
#
Rosetta Code "Count the coins"
This is a direct translation of
rather than a list. LWB, UPB, and array slicing makes the mapping very simple:
LWB > UPB <=> []
Line 197 ⟶ 195:
Output:<pre>
+242
</pre>
{{works with|ALGOL 68G|Any - tested with release 2.8.4}}
{{trans|Haskell}}
<lang Algol68>
#
Rosetta Code "Count the coins"
This uses what I believe are the ideas behind the "much faster, probably
harder to read" Haskell version.
#
BEGIN
PROC ways to make change = ([] INT denoms, INT amount) LONG INT:
BEGIN
[0:amount] LONG INT counts, new counts;
FOR i FROM 0 TO amount DO counts[i] := (i = 0 | 1 | 0) OD;
FOR i FROM LWB denoms TO UPB denoms DO
INT denom = denoms[i];
FOR j FROM 0 TO amount DO new counts[j] := 0 OD;
FOR k FROM 0 TO amount DO
IF LONG INT count = counts[k]; count > 0 THEN
FOR l FROM k + denom BY denom TO amount DO
new counts[l] +:= count
OD
FI
OD;
FOR j FROM 0 TO amount DO counts[j] +:= new counts[j] OD
OD;
counts[amount]
END;
print((ways to make change((1, 5, 10, 25), 100), newline));
print((ways to make change((1, 5, 10, 25, 50, 100), 10000), newline));
print((ways to make change((1, 5, 10, 25, 50, 100), 100000), newline))
END
</lang>
Output:<pre>
+242
+139946140451
+13398445413854501
</pre>
| |||