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.

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

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. combine

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

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

此外，如果我们递归列表，则除法通常是列表的car和列表的cdr。如果列表汽车本身不是列表，通常可以直接解决。 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.

顺便说一句，我强烈建议小计划者学习递归。据我所读，在这一点上，它比其他任何地方都要好。

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屋！