[TOC] ## 問題 1美元換 50美分,24美分,10美分,5美分,1美分,有幾種方式 ## 思考 將總數為a的現金換成n種硬幣的不同方式的數目等于 1. 將現金數a換成除第一種硬幣之外的所有其他硬幣的不同方式數目,加上 2. 將現金數a-d換成所有種類的硬幣的不同方式數目,其中的d是第一種硬幣的幣值 將某個給定現金數的換零錢方式的問題,遞歸地歸**約為**對更少現金數或者更少種類硬幣的同一個問題。 - 如果a就是0,應該算作是有1種換零錢的方式。 - 如果a小于0,應該算作是有0種換零錢的方式 - 如果n是0,應該算作是有0種換零錢的方式。 ``` (define (count-change amount) (cc amount 5)) (define (cc amount kinds-of-coins) (cond ((= amount 0) 1) ((or (< amount 0) (= kinds-of-coins 0)) 0) (else (+ (cc amount (- kinds-of-coins 1)) (cc (- amount (first-denomination kinds-of-coins)) kinds-of-coins))))) (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))) ;; -> 292 (count-change 100) ```