Rosetta Code

Count the coins: Difference between revisions

Page Discussion

Count the coins (view source)

Revision as of 15:12, 5 February 2012

41 bytes removed ,  12 years ago
→‎{{header|Ruby}}
(→‎{{header|Ada}}: Added Ada version)
Line 823:
'''Recursive, with caching'''
 
<lang ruby>def make_change(amtamount, coins)
table@cache = Array.new(namount+1) {|i| Array.new(m+coins.size, i.zero? ? 1 : nil)}▼
@cache = {}▼
@coins = coins
do_count(amtamount, @coins.length - 1)
end
 
def do_count(n, m)
elsifif n < 0 || m < 0▼
if @cache.has_key?([n,m])▼
@cache[[n,m]]
elsif n == 0
1
▲ elsif n < 0 || m < 0
0
▲ ifelsif @cache.has_key?([n,][m])
▲ @cache = {}@cache[n][m]
else
@cache[[n,][m]] = do_count(n-@coins[m], m-1) + do_count(n-@coins[m], m-1)
end
end
 
p make_change( 1_00, [1,5,10,25])
p make_change(1000_00, [1,5,10,25,50,100])</lang>▼
begin
▲ p make_change(1000_00, [1,5,10,25,50,100])
rescue Exception => e
puts e.message
end</lang>
 
outputs
<pre>242
stack level too deep13398445413854501</pre>
 
'''Iterative'''
 
<lang ruby>def make_change2(amtamount, coins)
n, m = amtamount, coins.size
table = Array.new(n+1){|i| Array.new(m, i.zero? ? 1 : nil)}
m = coins.length - 1
for i in 1..n
 
for j in 0...m
▲ table = Array.new(n+1) {|i| Array.new(m+1)}
table[0i][j] = Array.new(m+1,i<coins[j] 1? 0 : table[i-coins[j]][j]) +
(j-1 < 01 ? 0 : table[i][j-1])▼
1.upto(n) do |i|
0.upto(m) do |j|
table[i][j] = (i-coins[j] < 0 ? 0 : table[i-coins[j]][j]) +
▲ (j-1 < 0 ? 0 : table[i][j-1])
end
end
table[n-1][m-1]
end
 
p make_change2(100 1_00, [1,5,10,25])
p make_change2(1000_00, [1,5,10,25,50,100])</lang>
outputs
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/203880"