Count the coins: Difference between revisions
→{{header|Picat}}
No edit summary |
|||
Line 2,620:
13,398,445,413,854,496 -- 32 bit (5 out)
9,007,199,254,740,992 -- max precision (53 bits) of a 64-bit float
</pre>
=={{header|Picat}}==
Using dynamic programming with tabling.
<lang Picat>go =>
Problems = [[ 1*100, [25,10,5,1]], % 1 dollar
[ 100*100, [100,50,25,10,5,1]], % 100 dollars
[ 1_000*100, [100,50,25,10,5,1]], % 1000 dollars
[ 10_000*100, [100,50,25,10,5,1]], % 10000 dollars
[100_000*100, [100,50,25,10,5,1]] % 100000 dollars
],
foreach([N,L] in Problems)
initialize_table, % clear the tabling from previous run
println([n=N,l=L]),
time(println(num_sols=coins(L,N,1)))
end.
table
coins(Coins, Money, M) = Sum =>
Sum1 = 0,
Len = Coins.length,
if M == Len then
Sum1 := 1,
else
foreach(I in M..Len)
if Money - Coins[I] == 0 then
Sum1 := Sum1 + 1
end,
if Money - Coins[I] > 0 then
Sum1 := Sum1 + coins(Coins, Money-Coins[I], I)
end,
end
end,
Sum = Sum1.
</lang>
Test:
<lang picat>Picat> go</lang>
Output:
<pre>
[n = 100,l = [25,10,5,1]]
num_sols = 242
CPU time 0.0 seconds.
[n = 10000,l = [100,50,25,10,5,1]]
num_sols = 139946140451
CPU time 0.005 seconds.
[n = 100000,l = [100,50,25,10,5,1]]
num_sols = 13398445413854501
CPU time 0.046 seconds.
[n = 1000000,l = [100,50,25,10,5,1]]
num_sols = 1333983445341383545001
CPU time 0.496 seconds.
[n = 10000000,l = [100,50,25,10,5,1]]
num_sols = 133339833445334138335450001
CPU time 5.402 seconds.
</pre>
| |||