Anonymous user
Count the coins: Difference between revisions
Second Python version
(Shorter D version) |
(Second Python version) |
||
Line 310:
13398445413854501
1333983445341383545001</pre>
With [http://psyco.sourceforge.net/introduction.html Psyco] it runs as fast as some natively compiled languages.
===Alternative version===
{{trans|C}}
This version is about three times faster:
<lang python>try:
import psyco
psyco.full()
except ImportError:
pass
def make_change(amount_cents, coins):
n = len(coins)
t = [0] * (n * (amount_cents + 1))
for i in xrange(n):
t[i] = 1
pos = n
for s in xrange(1, amount_cents + 1):
if coins[0] <= s:
t[pos] = t[pos - (n * coins[0])]
pos += 1
for i in xrange(1, n):
if coins[i] <= s:
t[pos] = t[pos - (n * coins[i])]
t[pos] += t[pos - 1]
pos += 1
return t[pos - 1]
print make_change( 100, [1,5,10,25])
print make_change( 100000, [1,5,10,25,50,100])
# extra
print make_change(1000000, [1,5,10,25,50,100])
print make_change( 100000, [1,2,5,10,20,50,100,200])
print make_change(1000000, [1,2,5,10,20,50,100,200])</lang>
Output:
<pre>242
13398445413854501
1333983445341383545001
10056050940818192726001
99341140660285639188927260001</pre>
=={{header|Ruby}}==
| |||