Count the coins: Difference between revisions

Content added Content deleted

Inline

@@ Line 2,620: / Line 2,620: @@
 ,398,445,413,854,496      -- 32 bit (5 out)
 ,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>