計算機プログラムの構造と解釈　第二版 P58 問題2.19

目的は

・手続きfirst-denominationを定義する
・手続きexcept-first-denominationを定義する
・手続きno-more?を定義する
・リストcoin-valuesの順はccの答えに影響があるか？なぜか？語る

あんまり難しく考えないほうがいい。
no-more?
はどう考えても、リストが空か否か調べる幹事だし、

first-denomination
は、「初めの貨幣」ってなって

except-first-denomination
は、「それ以外の貨幣」

だので、まあ予想はつくよね。

で、求める四番目のリストの順番は関係ない。
関係あると思ったけど、試してみたら順番関係なかった。
まー、よくよく考えたらそりゃそうかなと思った。

実装

#!/usr/local/bin/gosh
;; -*- coding: utf-8 -*-

(use ggc.debug.trace)
(use math.mt-random)


(define us-coins (list 50 25 10 5 1)) 

(define us-coins2 (list 1 5 10 25 50))

(define uk-coins (list 100 50 20 10 5 2 1 0.5))

(define (cc amount coin-values)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (no-more? coin-values)) 0)
        (else
          (+ (cc amount
                 (exept-first-denomination coin-values))
             (cc (- amount
                    (first-denomination coin-values))
                 coin-values)))))

(define (no-more? items)
  (null? items))

(define (first-denomination items)
  (car items))

(define (exept-first-denomination items)
  (cdr items))

;; main
(define (main args)

  (display "(cc 100 us-coins): ")
  (display (cc 100 us-coins))
  (newline)

  (display "(cc 100 us-coins2): ")
  (display (cc 100 us-coins2))
  (newline)

  (display "(cc 100 uk-coins): ")
  (display (cc 100 uk-coins))
  (newline)
 0)

実行

(cc 100 us-coins): 292
(cc 100 us-coins2): 292
(cc 100 uk-coins): 104561