1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
;;; This file is part of Oaklisp.
;;;
;;; This program is free software; you can redistribute it and/or modify
;;; it under the terms of the GNU General Public License as published by
;;; the Free Software Foundation; either version 2 of the License, or
;;; (at your option) any later version.
;;;
;;; This program is distributed in the hope that it will be useful,
;;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
;;; GNU General Public License for more details.
;;;
;;; The GNU GPL is available at http://www.gnu.org/licenses/gpl.html
;;; or from the Free Software Foundation, 59 Temple Place - Suite 330,
;;; Boston, MA 02111-1307, USA
;;; Number of ways of giving change, Barak A. Pearlmutter, Fall 1989.
;;; This technique is covered in Concrete Mathamatics by Graham, Knuth
;;; and Patashnik, page 331.
;;; Helper functions:
;;; This computes the number of ways to choose m objects from a pool
;;; of n. The arguments are in the usual mathematical order.
(define (choose n m)
(let aux ((n n)(m1 m)(total 1))
(if (= m1 0)
(let aux ((m m)(total2 1))
(if (= m 0)
(/ total total2)
(aux (- m 1) (* m total2))))
(aux (- n 1) (- m1 1) (* n total)))))
;;; These are the coefficients of the polynomial a(z) = (1-z^{10})^5 /
;;; (1-z)^2(1-z^2)(1-z^5)(1-z^{10}). The end should be zero padded to
;;; infinity, but the arguments given are always between 0 and 39
;;; inclusive.
(define (a i)
(nth '(01 02 04 06 09 13 18 24 31 39 45 52 57 63 67 69
69 67 63 57 52 45 39 31 24 18 13 09 06 04 02 01
0 0 0 0 0 0 0 0)
i))
;;; This returns the number of ways to make change on c cents using
;;; coins of denomination 1,5,10,25,50. The math behind this is too
;;; hairy for a comment, as it requires lots of superscripts and sums
;;; and stuff. In effect, we end up casing on (c mod 50) with each
;;; case determining the coefficients of a fourth order polynomial of
;;; floor(c/50).
(define (change c)
(let* ((c5 (quotient c 5))
(q (quotient c5 10))
(r (modulo c5 10)))
(+ (* (a r) (choose (+ q 4) 4))
(* (a (+ r 10)) (choose (+ q 3) 4))
(* (a (+ r 20)) (choose (+ q 2) 4))
(* (a (+ r 30)) (choose (+ q 1) 4)))))
;;; Test case, the number of ways of giving change for $1,000,000.00
;;; (change 100000000) = 66666793333412666685000001.
;;; For $1,000,000,000,000,000,000.00,
;;; (change 100000000000000000000)
;;; 66666666666666666793333333333333333412666666666666666685000000000000000001
;;; eof
|
