Count the coins: Difference between revisions
m (reference) |
(add Ruby) |
||
Line 41: | Line 41: | ||
(print (count-change 100000 '(100 50 25 10 5 1))) ; = 13398445413854501 |
(print (count-change 100000 '(100 50 25 10 5 1))) ; = 13398445413854501 |
||
(terpri)</lang> |
(terpri)</lang> |
||
=={{header|Ruby}}== |
|||
The algorithm also appears [http://www.algorithmist.com/index.php/Coin_Change 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]) |
|||
return @cache[[n,m]] |
|||
elsif n == 0 |
|||
return 1 |
|||
elsif n < 0 |
|||
return 0 |
|||
elsif m < 0 and n >= 1 |
|||
return 0 |
|||
end |
|||
return @cache[[n,m]] = do_count(n, m-1) + do_count(n-@coins[m], m) |
|||
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 |
|||
<pre>242 |
|||
stack level too deep</pre> |
|||
'''Iterative''' |
|||
<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 ? (i == 0 ? 1 : 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 |
|||
<pre>242 |
|||
13398445413854501</pre> |
Revision as of 17:16, 28 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]) return @cachen,m elsif n == 0 return 1 elsif n < 0 return 0 elsif m < 0 and n >= 1 return 0 end return @cachen,m = do_count(n, m-1) + do_count(n-@coins[m], m)
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
Iterative
<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 ? (i == 0 ? 1 : 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