Count the coins: Difference between revisions
Content added Content deleted
(Added Tailspin solution) |
(Added more efficient version, also inspired by a Haskell version) |
||
Line 160: | Line 160: | ||
{{works with|ALGOL 68G|Any - tested with release 2.4.1}} |
{{works with|ALGOL 68G|Any - tested with release 2.4.1}} |
||
{{trans|Haskell}} |
{{trans|Haskell}} |
||
This corresponds to a "naive" Haskell version; to do the larger problem will require a better approach. |
|||
<lang Algol68> |
<lang Algol68> |
||
# |
# |
||
Rosetta Code "Count the coins" |
Rosetta Code "Count the coins" |
||
This is a direct translation of |
This is a direct translation of the "naive" Haskell version, using an array |
||
a list. LWB, UPB, and array slicing makes the mapping very simple: |
rather than a list. LWB, UPB, and array slicing makes the mapping very simple: |
||
LWB > UPB <=> [] |
LWB > UPB <=> [] |
||
Line 197: | Line 195: | ||
Output:<pre> |
Output:<pre> |
||
+242 |
+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> |
</pre> |
||