This program requires two initial arrays: an array of coins (which is at first empty) and an array of amounts. The "amounts" array stores the number of cents each coin is worth.
def change(coins, amounts, highest, sum, goal)
# Display result if we have correct change.
if sum == goal
display(coins, amounts)
end
# Return if we have too much money.
if sum > goal
return
end
# Loop over coin amounts and try adding them.
amounts.each do |value|
if value >= highest
# Copy the coins array, add value to it.
copy = Array[]
copy.concat coins
copy.push(value)
# Recursive call: add further coins if needed.
change(copy, amounts, value, sum + value, goal)
end
end
end
def display(coins, amounts)
# Display all the coins.
amounts.each do |amount|
count = 0
coins.each do |coin|
if coin == amount
count += 1
end
end
print amount,
": ", count,
"\n"
end
print
"\n"
end
# Specify our starting coins and all coin amounts.
coins = Array[]
amounts = Array[1, 5, 10, 25, 50]
# Make change for 51 cents.
change(coins, amounts, 0, 0, 51)
1: 51
5: 0
10: 0
25: 0
50: 0
1: 46
5: 1
10: 0
25: 0
50: 0
1: 41
5: 2
10: 0
25: 0
50: 0
1: 41
5: 0
10: 1
25: 0
50: 0...