Count the coins: Difference between revisions
(draft task) |
(Common Lisp code) |
||
Line 13: | Line 13: | ||
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 2<sup>32</sup>). |
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 2<sup>32</sup>). |
||
=={{header|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> |
Revision as of 04:24, 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).
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>