coin.scm
30分シリーズ、その11。ある金額を持つとき、硬貨と紙幣が最低何枚必要かを求めるプログラム。SICPに載ってたネタ。
gosh> (jp-change 3) ; 3円 = 1円玉 * 3 ((1 3)) gosh> (jp-change 15) ; 15円 = 10円玉 * 1 + 5円玉 * 1 ((10 1) (5 1)) gosh> (jp-change 16) ; 15円 = 10円玉 * 1 + 5円玉 * 1 + 1円玉 * 1 ((10 1) (5 1) (1 1)) gosh> (jp-change 2000) ; ときどきでいいので2000円札のことを思い出してあげてください ((2000 1)) gosh> (jp-change 2142) ((2000 1) (100 1) (10 4) (1 2))
(use srfi-1) (define (cost->coin cost coins) (cond ((null? coins) '()) ((>= cost (car coins)) (let1 changed (change (- cost (car coins)) coins) (cons (+ 1 (car changed)) (cdr changed)))) (else ; (< cost (car coins)) (cons 0 (change cost (cdr coins)))))) (define (coin->cost counts coins) (fold (lambda(count coin cost) (+ cost (* count coin))) 0 counts coins)) (define (cost->with-coin cost coins) (filter (lambda(x) (not (= 0 (cadr x)))) (zip coins (change cost coins)))) (define (jp-change cost) (cost->with-coin cost '(10000 5000 2000 1000 500 100 50 10 5 1)))
