🌳 换零钱算法
题目
将币值100换成50,25,10,5,1的组合,有几种?
分治
这个组合可以分成两个互斥且穷尽的事件组合
- 不使用某一种币值
- 至少使用一次某一种币值
因为不使用和至少使用一次是互斥的
所以我们可以这么拆分
并且解答即两个组合相加
一个问题分解为规模更小的同类问题 – 递归
进而,我们将币值按面值大小排序,然后可以拆分为
- 不使用第一种币值
- 至少使用一次第一种币值
而对于 “不使用第一种币值” 的方案,我们可以看作 “将币值100换成25,10,5,1”,这样的问题
而对于 “至少使用一次第一种币值” ,我们可以看作 “将币值50换成50,25,10,5,1”,这样的问题
而上面两个问题是我们一开始的同类问题,使用相同的方式进行拆解
停止条件 – 边界
这是一个递归,那么必须有停机条件
- 当前要拆换的币值为0,说明我们换完了,且刚好,这时候算1种成功方案
- 当前要拆换的币值<0,说明当前方案组合出来的币值>100,失败了
- 当前可以被换的种类没有了,但币值>0, 说明当前方案组合出来的币值<100,失败了
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
(define (count-change amount)
(define (cc amount kind-of-coins)
(cond ((= amount 0) 1)
((< amount 0) 0)
((= kind-of-coins 0) 0)
(else
(+ (cc (- amount
(value kind-of-coins))
kind-of-coins)
(cc amount
(- kind-of-coins 1))))))
(define (value kind-of-coins)
(cond ((= kind-of-coins 1) 1)
((= kind-of-coins 2) 5)
((= kind-of-coins 3) 10)
((= kind-of-coins 4) 25)
((= kind-of-coins 5) 50)))
(cc amount 5)
)
This post is licensed under CC BY 4.0 by the author.