SICP示例:计数变化，看不懂 [英] SICP example: Counting change, cannot understand

问题描述

我是一名初学者，在 MIT OpenCourseWare 上学习 SICP 课程，使用视频讲座和在线提供的书籍.昨天我遇到了一个例子，它问我​​们是否可以编写一个程序来计算改变任何给定金额的方法的数量.

I am a beginner following SICP course on MIT OpenCourseWare using both the video lectures and the book available online. Yesterday I came across an example, which ask if we can write a procedure to compute the number of ways to change any given amount of money.

这个问题有一个简单的递归程序解决方案:

This problem has a simple solution as a recursive procedure:

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

如果您想查看更多内容，我从这里.

If you want to check more of it, I took it from here.

他们正在计算使用 K 种硬币改变数量 (A) 的方法数量 (N)，方法是:

they are calculating the number (N) of ways of change a quatity (A) using K kinds of coins by adding:

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

1. the number of ways (X) of changing A without coins of the first type.

改变 (A - D) 的方式 (Y) 的数量，其中 D 是第一个硬币的面额，使用所有 K 种硬币.

The number of ways (Y) of changing (A - D), where D is the denomination of the fisrt coin, using ALL K types of coins.

问题是，我只是不明白这一点.接下来，他们试图解释说:

The problem is, I just don't understand this. Following, they try to explain saying:

要了解为什么这是真的，请观察改变的方式可以分为两组:不使用任何第一种硬币的方式，以及使用任何一种的方式.因此，方式的总数找零钱等于不使用任何第一种硬币的方法数，加上假设我们确实使用第一种硬币的方法数.(最后一句和加法 N = X + Y 一样吗?) 但后面的数字等于使用第一种硬币后剩余的金额进行找零的次数.(用完这个硬币后，他们指的是有没有第一种硬币的变化方式?)

"To see why this is true, observe that the ways to make change can be divided into two groups: those that do not use any of the first kind of coin, and those that do. Therefore, the total number of ways to make change for some amount is equal to the number of ways to make change for the amount without using any of the first kind of coin, plus the number of ways to make change assuming that we do use the first kind of coin. (Is the last sentence the same as the addition N = X + Y ? ) But the latter number is equal to the number of ways to make change for the amount that remains after using a coin of the first kind. (After using this coin, they refer to ways of making change with or without the first kind of coin? ) "

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

I understand how they implemented the recursive algorithm, but I am unable to see how they got there. English is not my native language, so I might be missing something. If you could explain me, using other terms, the logic behind the solution I would really appreciate it. Thanks.

推荐答案

如果我们在递归上考虑太多，我们已经失败了.就个人而言，我在思考递归时使用了两个比喻.一本来自小书小阴谋家":第七诫 - 在性质相同的子部分重复.另一个是用于设计算法的分治结合范式.本质上，它们在如何递归思考方面是相同的.

If we think too hard on recursion, we already fail. Personally, I use two metaphors in thinking recursions. One is from the small book "the little schemer": The Seventh Commandment - Recur on the subparts that are of the same nature. Another is the divide-conquer-combine paradigm for designing algorithms. Essentially, they are the same thing in how to think recursively.

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

这个问题有两个变量:货币的数量(N)和硬币的种类(K)，因此任何划分都需要满足以下条件:1.减少所有变量:N 和 K， 2. 子部分具有相同的性质，因此每个子部分都可以通过递归过程本身解决，也可以直接解决.3.所有子部分加在一起==原来的一个部分，不多也不少.

The problem has two variables: The number (N) of money and the kinds (K) of coins, therefore any division needs to meet the following: 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 在第二部分减少.两者性质相同，可递归求解，共同构成原问题.

The division in the solution divides the original problems into two subparts: the first subpart is all combinations that using the first coin (we can restate it that all combinations using at least one coin of the first coin in the same meaning). The remaining subpart is that all combinations using none of the first coin. N is reduced in the first subpart, K is reduced in the second part. Both are the same nature which can be solved recursively and they together are the original problem.

1. 征服

在这一步中，我会考虑基本情况.当问题减少到可以直接给出答案的最小值时，所有基本情况是什么?在这个解决方案中，有三个基本情况.第一个是 N 减少到 0.第二个是 N 减少到负数.第三是硬币减少到0但N仍然是正数.

In this step, I think about the base cases. What are the all base cases when the problem is reduced to the minimal that can be given answers directly. In this solution, there are three base cases. 1st is the N is reduced to 0. 2nd is the N is reduced to the negative. 3rd is the coins is reduced to 0 but N is still positive.

1. 结合

在求解子部分时如何组合结果.在这个解决方案中，它们只是 +.

How results are combined when the subparts are solved. In this solution, they are simply +.

此外，如果我们在一个列表上递归，那么除法通常是列表的 car 和列表的 cdr.通常list的car如果本身不是list可以直接求解.cdr 部分应该递归解决.如果满足，则基本情况是列表的末尾.

What's more, if we are recursive on a list, the division is usually car of the list and cdr of the list. Usually car of list can be solved directly if itself isn't a list. cdr part should be solved recursively. The base case is the end of list if met.

顺便说一句，我强烈推荐 the little schemer 来学习递归.就我所读到的而言，它在这一点上比任何其他人都要好得多.

B.T.W, I would highly recommend the little schemer for learning recursion. It is much better than any others on this particular point as far as I have read.

这篇关于SICP示例:计数变化，看不懂的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！