Count the coins: Difference between revisions
Line 76: | Line 76: | ||
stack level too deep</pre> |
stack level too deep</pre> |
||
''' |
'''Dynamic Programming''' |
||
<lang ruby>def make_change2(amt, coins) |
<lang ruby>def make_change2(amt, coins) |
Revision as of 03:20, 29 October 2011
There are four types of common coins in US currency: quarters (25 cents), dimes (10), nickels (5) and pennies (1). There are 6 ways to make change for 15 cents:
- A dime and a nickel;
- A dime and 5 pennies;
- 3 nickels;
- 2 nickels and 5 pennies;
- A nickel and 10 pennies;
- 15 pennies.
How many ways are there to make change for a dollar? (1 dollar = 100 cents).
Optional:
Less common are dollar coins (100 cents); very rare are half dollars (50 cents). With the addition of these two coins, how many ways are there to make change for $1000? (note: the answer is larger than 232).
Algorithm: See here.
Common Lisp
<lang lisp>(defun count-change (amount coins)
(let ((cache (make-array (list (1+ amount) (length coins))
:initial-element nil)))
(macrolet ((h () `(aref cache n l))) (labels
((recur (n coins &optional (l (1- (length coins)))) (cond ((< l 0) 0) ((< n 0) 0) ((= n 0) 1) (t (if (h) (h) ; cached (setf (h) ; or not (+ (recur (- n (car coins)) coins l) (recur n (cdr coins) (1- l)))))))))
;; enable next line if recursions too deep ;(loop for i from 0 below amount do (recur i coins)) (recur amount coins)))))
- (compile 'count-change) ; for CLISP
(print (count-change 100 '(25 10 5 1))) ; = 242 (print (count-change 100000 '(100 50 25 10 5 1))) ; = 13398445413854501 (terpri)</lang>
Ruby
The algorithm also appears here
Recursive, with caching
<lang ruby>def make_change(amt, coins)
@cache = {} @coins = coins do_count(amt, @coins.length - 1)
end
def do_count(n, m)
if @cache.has_key?([n,m]) @cachen,m elsif n == 0 1 elsif n < 0 || m < 0 0 else @cachen,m = do_count(n, m-1) + do_count(n-@coins[m], m) end
end
p make_change(1_00, [1,5,10,25]) begin
p make_change(1000_00, [1,5,10,25,50,100])
rescue Exception => e
puts e.message
end</lang>
outputs
242 stack level too deep
Dynamic Programming
<lang ruby>def make_change2(amt, coins)
n = amt m = coins.length - 1
table = Array.new(n+1) {|i| Array.new(m+1)} table[0] = Array.new(m+1, 1) 1.upto(n) do |i| 0.upto(m) do |j| _i = i - coins[j] table[i][j] = (_i < 0 ? 0 : table[_i][j]) + (j-1 < 0 ? 0 : table[i][j-1]) end end table[n][m]
end
p make_change2(100, [1,5,10,25]) p make_change2(1000_00, [1,5,10,25,50,100])</lang> outputs
242 13398445413854501