読書会の

宿題が出た。
SICP 1.2.2 の両替計算のパターンをリストにする、というもの。帰宅中にできた気がしたんですが気のせいでした。
木なので似たパターンが沢山出てくるので memoise させたいんですが、それ以前の問題として解をどうやって出すか。最初は再起で、って思ってたんですがこーゆーパターンは繰り返しの方が良さげ。
で試行錯誤の後にヒリ出たのが以下。

(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) 25)
	((= kinds-of-coins 5) 50)))

(define (change2list amount kinds-of-coins)
  (let f ((rslt '()) (amount amount) (kinds-of-coins kinds-of-coins))
    (cond ((= amount 0) (list rslt))
	  ((or (< amount 0) (= kinds-of-coins 0)) '())
	  (else
	   (append (if (null? rslt)
		       (change2list amount (- kinds-of-coins 1))
		       (f rslt amount (- kinds-of-coins 1)))
		   (f (append rslt 
			      (list (first-denomination kinds-of-coins)))
		      (- amount (first-denomination kinds-of-coins))
		      kinds-of-coins))))))

試験が以下。

(use gauche.test)

(add-load-path ".")
(load "change")

(test-start "change")
(test-section "first-denomination")
(test-section "change-list")
(test* "(change2list 1 5)"
       '((1))
       (change2list 1 5))

(test* "(change2list 2 5)"
       '((1 1))
       (change2list 2 5))

(test* "(change2list 3 5)"
       '((1 1 1))
       (change2list 3 5))

(test* "(change2list 4 5)"
       '((1 1 1 1))
       (change2list 4 5))

(test* "(change2list 5 5)"
       '((1 1 1 1 1) (5))
       (change2list 5 5))

(test* "(change2list 6 5)"
       '((1 1 1 1 1 1) (5 1))
       (change2list 6 5))

(test* "(change2list 7 5)"
       '((1 1 1 1 1 1 1) (5 1 1))
       (change2list 7 5))

(test* "(change2list 8 5)"
       '((1 1 1 1 1 1 1 1) (5 1 1 1))
       (change2list 8 5))

(test* "(change2list 9 5)"
       '((1 1 1 1 1 1 1 1 1) (5 1 1 1 1))
       (change2list 9 5))

(test* "(change2list 10 5)"
       '((1 1 1 1 1 1 1 1 1 1) (5 1 1 1 1 1) (5 5) (10))
       (change2list 10 5))

(test* "(change2list 15 5)"
       '((1 1 1 1 1 1 1 1 1 1 1 1 1 1 1) 
	 (5 1 1 1 1 1 1 1 1 1 1) 
	 (5 5 1 1 1 1 1) 
	 (5 5 5)
	 (10 1 1 1 1 1)
	 (10 5))
       (change2list 15 5))

(test-end)

ちょっとキタナい。買い物に行かなきゃなので帰宅後きれいにしつつ memoize 盛り込む方向で。あと、勉強会の中身な話も別途出力予定ッス。