零钱问题
最后更新于：2022-04-02 04:23:04
[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)
```
';