SICP問題2.19
first-denomination, except-first-denomination, no-more?の定義
(define (first-denomination coin-values) (car coin-values)) (define (except-first-denomination coin-values) (cdr coin-values)) (define (no-more? coin-values) (null? coin-values))
coin-valuesの順がccの答えに影響するか?の実験
(define us-coins (list 50 25 10 5 1)) (cc 100 us-coins) ; 292 (define us-coins (list 1 5 10 25 50)) (cc 100 us-coins) ; 292 (define uk-coins (list 100 50 20 10 5 2 1 0.5)) (cc 100 uk-coins) ; 104561 (define uk-coins (list 0.5 1 2 5 10 20 50 100)) (cc 100 uk-coins) ; 104561
上記の結果のとおり、リスト coin-values の順は、 cc の答えに影響はない。
cc のアルゴリズムは合計の金額からリストの先頭の硬貨を含む両替の組み合わせと、リストの先頭の硬貨を含まない両替の組み合わせの和を求める。
先頭の硬貨を含む場合は、合計金額から硬貨の金額を減じ、残額があるならばcc に再帰する。先頭の硬貨を含まない場合はリストの2番目以降の硬貨についての処理を行うためにccに再帰する。
上記のように、どの硬貨から始めたとしても、その硬貨を含む組み合わせ、その硬貨を含まない組み合わせの全てのパターンを走査するためリストの並び順は影響しない。