Anonymous user
Count the coins: Difference between revisions
Python version
(D version) |
(Python version) |
||
Line 132:
This algorithm is '''slow'''. A test machine needed '''1 minute''' to run ''100000 { 100 50 25 10 5 1 } make-change .'' and get 13398445413854501. The same machine needed less than 1 second to run the Common Lisp ([[SBCL]]), Ruby ([[MRI]]) or Tcl ([[tclsh]]) programs and get the same answer.
=={{header|Python}}==
{{trans|Ruby}}
<lang python>try:
import psyco
psyco.full()
except ImportError:
pass
def make_change(amount_cents, coins):
n = amount_cents
m = len(coins) - 1
table = [[0] * (m + 1) for _ in xrange(n + 1)]
table[0] = [1] * (m + 1)
for i in xrange(1, n + 1):
for j in xrange(m + 1):
ic = i - coins[j]
table[i][j] = (0 if ic < 0 else table[ic][j]) + \
(0 if j-1 < 0 else table[i][j-1])
return table[n][m]
print make_change( 100, [1,5,10,25])
print make_change( 100000, [1,5,10,25,50,100])
print make_change(1000000, [1,5,10,25,50,100]) # extra</lang>
Output:
<pre>242
13398445413854501
1333983445341383545001</pre>
With Psyco it's almost twice faster than the D version.
=={{header|Ruby}}==
| |||