両替日本版

両替問題は面白かった。
理屈は分かるけど、解けてしまうことがやっぱり不思議。
せっかくなので日本硬貨での両替計算も作ってみました。

(define (count-change amount)
  (define (cc amount kinds-of-coins)
    (cond ((= amount 0) 1)
	  ((or (< amount 0) (= kinds-of-coins 0)) 0)
	  (else (+ (cc amount
		       (- kinds-of-coins 1))
		   (cc (- amount
			  (first-denomination kinds-of-coins))
		       kinds-of-coins)))))
  (define (first-denomination kinds-of-coins)
    (cond ((= kinds-of-coins 1) 1)
	  ((= kinds-of-coins 2) 5)
	  ((= kinds-of-coins 3) 10)
	  ((= kinds-of-coins 4) 50)
	  ((= kinds-of-coins 5) 100)
	  ((= kinds-of-coins 6) 500)))
  (cc amount 6))