一尘不染

SICP示例:计数变化,无法理解

algorithm

我是MIT
OpenCourseWare上SICP课程的初学者,同时使用视频讲座和在线书籍。昨天我遇到了一个示例,该示例询问我们是否可以编写一个程序来计算更改给定金额的货币的数量。

此问题有一个简单的解决方案作为递归过程:

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

如果您想检查更多,我从这里拿走

他们正在通过添加以下K种硬币来计算改变数量(A)的数量(N):

  1. 在没有第一类硬币的情况下改变A的方式(X)的数量。

  2. 使用ALL K类型的硬币进行兑换(A-D)的方式(Y)数量,其中D是第一个硬币的面额。

问题是,我只是不明白这一点。接下来,他们尝试解释说:

“要弄清为什么如此,观察改变的方法可以分为两类:不使用第一类硬币的人和不使用第一类硬币的人。因此,进行改变的方法总数一定数量等于不使用第一类硬币中的任何一种进行金额更改的方法的数量,加上假设我们确实使用第一类硬币的情况下进行更改的方法的数量。
(是最后一句话等于加法N = X + Y?), 但后者等于使用第一种硬币后对剩余金额进行更改的方法的数量
(使用此硬币后,它们指的是方法是否需要第一种硬币进行更改?)

我了解他们是如何实现递归算法的,但是我看不到他们是如何到达那里的。英语不是我的母语,所以我可能会缺少一些东西。如果您可以使用其他术语向我解释解决方案背后的逻辑,我将不胜感激。谢谢。


阅读 158

收藏
2020-07-28

共1个答案

一尘不染

如果我们对递归考虑得太辛苦,那么我们已经失败了。就个人而言,我在思考递归时使用了两个隐喻。一种是从小书“小策划者”中获得的:The Seventh Commandment - Recur on the subparts that are of the same nature。另一个是设计算法的“分而治之”组合范例。本质上,它们在递归思考中是同一回事。

  1. 划分为相同性质的子部分

该问题有两个变量:货币数量(N)和硬币种类(K),因此任何除法运算都需要满足以下条件: 1. reducing all variables: both N and K, 2. the subparts are the same nature so each subpart can be solved by the recursion process itself or be can solved directly. 3. all subparts together == the original one part, no more and no less.

解决方案中的划分将原始问题分为两个子部分:第一个子部分是所有使用第一个硬币的组合(我们可以重申一下,所有组合使用至少一个第一个硬币的含义相同)。剩下的子部分是所有组合都不使用第一个硬币。在第一子部分中减少N,在第二部分中减少K。两者具有相同的性质,可以递归解决,它们在一起就是原始问题。

  1. 征服

在这一步中,我考虑基本情况。将问题减少到可以直接给出答案的最低限度的所有基本情况是什么?在此解决方案中,有三种基本情况。第一个是N减小为0。第二个是N减小为负。第三是硬币减少为0,但N仍为正。

  1. 结合

解决子部分时如何组合结果。在此解决方案中,它们只是+。

更重要的是,如果我们在列表上递归,则除法通常是列表的car和列表的cdr。如果列表本身不是列表,通常可以直接解决列表汽车。cdr部分应递归解决。如果满足,则基本情况为列表的末尾。

顺便说一句,我强烈建议the little schemer学习递归。据我所读,在这一点上,它比任何其他方法都要好得多。

2020-07-28