SICP:换零钱方式统计问题

《SICP》书中“1.2.2 树形递归”一节中有一个“换零钱的方式统计”的实例,书上讲得有些概括,在本文中,我将结合自己的学习体会,详细地探讨这一问题。

我将按照以下四个部分介绍:

  • 换零钱方式统计问题
  • 问题解决思路
  • 源程序
  • 递归树

换零钱方式统计问题

我们首先明确换零钱方式统计这一问题:

试想我们手上有1美元,在我们面前有面值分别为半美元、四分之一美元、10美分、5美分和1美分的硬币。按照等值原则,我们可以随意地将我们手中的1美元兑换为5种硬币的任意组合。也就是说,我们可以五种都用上,也可以只用其中一种,也可以用其中的几种。问题为,我们总共有多少种组合的方式?

问题解决思路

在本节中,我们主要来详细解释书中解法的思路:

我们将使用美分这一单位,也就是说我们手上现在有100美分。

在开始兑换之前,我要引入一个概念——“回合”。我们整个兑换零钱的过程是由一个一个回合组合而成。在每一个回合中,我们仅能做出两种选择:

  1. 兑换一个当前面值的硬币

  2. 放弃这一面值

“当前面值”、“放弃这一面值”是什么意思呢?看完下面正式开始后的过程,就理解了。

现在我们正式开始,进入第一回合,在这一回合中,我们面临两个选择:

  1. 是否兑换一个半美元(50美分)的硬币

  2. 放弃半美元(50美分)这一面值

如果我们选择1:我们将得到一个半美元(50美分)的硬币,我们手上可兑换的钱还剩下50美分。

如果我们选择2:我们这回合什么也不做,我们手中可兑换的钱仍然是100美分。

不论做出哪一个选择,我们都进入了下一个回合,即第二回合,我们同样面临着选择:

如果我们在第一回合中做出了选择1,我们在第二回合中将面临两个选择:

  1. 再兑换一个半美元(50美分)的硬币

  2. 放弃半美元(50美分)这一面值

选择1意味着:我们将再得到一个半美元(50美分)的硬币,我们手上可兑换的钱为0,也就是我们成功地找到了一种兑换方式(两个半美元)。
选择2意味着:我们什么也没有做,手中可兑换的钱仍然是50美分。

如果我们在第一回合中做出了选择2,我们在第二回合中将同样面临两个选择:

  1. 是否兑换一个四分之一美元(25美分)的硬币

  2. 放弃四分之一美元(25美分)这一面值

选择1意味着:我们将得到一个四分之一美元(25美分)的硬币,我们手上可兑换的钱只剩下25美分。

选择2意味着:我们什么也没有做,手中可兑换的钱仍然是50美分。

从中我们可以找到规律:

  • 可供选择的硬币是按面值值从高到低排列的,除非我们放弃当前最高的币值,否则只要我们有钱,可以一直选择兑换一个

  • 当我们放弃了一种面值的硬币,在下一回合中,我们将面对面值小一个等级的硬币

  • 只要我们手中可兑换的钱有剩余,我们就可以继续一回合、一回合兑换下去,直到我们兑光

我们可以看出,整个过程是一个树形的结构,每一回合都将产生两个子节点。每个子节点又将再下一回合各产生两个子节点。

如果某个子节点处,可兑换钱数大于零,即还能产生新的子节点。如果等于零,说明我们刚好将钱兑光,即我们找到了一种有效的兑换方式。如果小于零,就违背了等值原则,说明这种兑换方式是无效的。

源程序

具体程序为:

(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)))

我们首先定义了一个函数 count-change ,它的参数 amount 即为我们手上的钱数,单位为美分。

第4行定义了函数 cc ,这就是我们在前一节中所述的一个回合。

它首先在第5~6行中定义了有效与无效方式。

第7~11行表示手里还有钱,还要递归下去,故将在递归树上产生两个子节点,一个是放弃这一面值,一个是继续兑换这一面值。

cc 函数有一个参数 kinds-of-coins ,它表示我们还可供兑换的硬币的种类数,在第2行中可见,它被初始化为5,表示面值我们还可以兑换5种,那么我们每回合将面对最贵的那一种硬币(半美元)。每次我们选择放弃一种面值,它就减1,直至为0被 cc 的终止条件检测到结束。

基于对 kinds-of-coins 的理解,最后我们再来看第13行定义 first-denomination ,它由一些列条件组成。如果我们传入的参数 kinds-of-coins 为5,那么将返回 50 ,即兑换一个半美元的硬币需扣除50美分。

递归树

基于前面的认识,我们可以徒手把整个递归树描述出来:

tree

在此我只展开了一部分。我们知道,将这100美分换成100个1美分也是一种有效的组合,可想而知这棵树的规模……