読書会の
宿題が出た。
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 盛り込む方向で。あと、勉強会の中身な話も別途出力予定ッス。