[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) ```