有100美元需找零.
??? 美元中有50美分(half-dollars),25美分(quarters),10美分(dimes),5美分(nickels),1美分(pennies).
總共有多少種方式?
分成兩步:
??? 1.計算使用50美分找零的方法數(shù).
??? 2.上面數(shù)目加上除了使用50美分找零的方法數(shù)以外的數(shù)目.
(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))))))