Anonymous user
Count the coins: Difference between revisions
→{{header|Ada}}: Added Ada version
(Added simpler Python version) |
(→{{header|Ada}}: Added Ada version) |
||
Line 16:
'''Algorithm''':
See [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_Temp_52 here].
=={{header|Ada}}==
{{Works with|gnat/gcc}}
<lang Ada>with Ada.Text_IO;
procedure Count_The_Coins is
type Counter_Type is range 0 .. 2**63-1; -- works with gnat
type Coin_List is array(Positive range <>) of Positive;
function Count(Goal: Natural; Coins: Coin_List) return Counter_Type is
Cnt: array(0 .. Goal) of Counter_Type := (0 => 1, others => 0);
-- 0 => we already know one way to choose (no) coins that sum up to zero
-- 1 .. Goal => we do not (yet) other ways to choose coins
begin
for C in Coins'Range loop
for Amount in 1 .. Cnt'Last loop
if Coins(C) <= Amount then
Cnt(Amount) := Cnt(Amount) + Cnt(Amount-Coins(C));
-- Amount-Coins(C) plus Coins(C) sums up to Amount;
end if;
end loop;
end loop;
return Cnt(Goal);
end Count;
procedure Print(C: Counter_Type) is
begin
Ada.Text_IO.Put_Line(Counter_Type'Image(C));
end Print;
begin
Print(Count( 1_00, (25, 10, 5, 1)));
Print(Count(1000_00, (100, 50, 25, 10, 5, 1)));
end Count_The_Coins;</lang>
Output:<pre> 242
13398445413854501</pre>
=={{header|AutoHotkey}}==
Line 37 ⟶ 77:
}
MsgBox % countChange(100)</lang>
=={{header|BBC BASIC}}==
Non-recursive solution:
| |||