有100美元需找零.
美元中有50美分(half-dollars),25美分(quarters),10美分(dimes),5美分(nickels),1美分(pennies).
总共有多少种方式?
分成两步:
1.计算使用50美分找零的方法数.
2.上面数目加上除了使用50美分找零的方法数以外的数目.
(define (count-change amount)
(cc amount 6))
(define (first-denomination kinds-of-coins)
(cond ((= kinds-of-coins 1) 1)
((= kinds-of-coins 2) 2)
((= kinds-of-coins 3) 5)
((= kinds-of-coins 4) 10)
((= kinds-of-coins 5) 20)
((= kinds-of-coins 6) 50)))
(define (cc amount kinds-of-coins)
(cond ((= amount 0) 1)
((or (< amount 0)
(= kinds-of-coins 0))
0)
(else (+ (cc (- amount ;第一步
(first-denomination kinds-of-coins))
kinds-of-coins)
(cc amount ;第二步
(- kinds-of-coins 1))))))