Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #!/usr/bin/ruby
- # Calculate the number of ways to make change for a given amount. Pass
- # the amount as number of cents as the only parameter.
- AMOUNT = Integer(ARGV[0])
- COINS = [10000, 5000, 1000, 500, 200, 100, 50, 25, 10, 5, 1]
- # Count the number of ways to make change, given the amount and types of
- # coins. The coins are passed as an array sorted from largest to smallest
- def ways(amount, coins)
- # When there is only one type of coin, the only way to make change is to
- # divide the amount evenly by the value of the coin.
- if coins.length == 1
- if amount % coins.first == 0
- 1
- else
- 0
- end
- else
- # With each possible number of the largest coin, calculate the number
- # of ways to make change with the second largest through smallest coins
- # for the remaining amount recursively, and sum them
- 0.step(amount, coins.first).inject(0) do |total_ways, used_amount|
- total_ways + ways(amount - used_amount, coins[1..-1])
- end
- end
- end
- puts ways(AMOUNT, COINS)
Add Comment
Please, Sign In to add comment