16

我是一名初学者，学习麻省理工学院 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. 改变 (A - D) 的方式 (Y) 的数量，其中 D 是第一枚硬币的面额，使用所有 K 种硬币。

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

“要了解为什么这是真的，请观察做出改变的方式可以分为两组：不使用任何第一种硬币的那些，以及使用任何一种硬币的那些。因此，做出改变的方式的总数for some amount 等于不使用任何第一种硬币的金额的找零方式的数量，加上假设我们使用第一种硬币的找零方式的数量。（是最后一句与加法相同 N = X + Y ?)但后一个数字等于使用第一种硬币后剩余金额的找零方式的数量。（使用此硬币后，他们指的是方式用或不用第一种硬币找零？） ”

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

4

3 回答 3

24

“方式数（N）......使用N种”这两个Ns显然不一样。所以让我们说K各种硬币。

我们有很多硬币，但每个硬币是 1、5、10、25 或 50 美分，总共 5 种硬币。我们需要花一美元买东西，100 美分。假设每种硬币无限供应。我们有多少种方法可以达到 100 的总和？

我们要么使用一些 50 美分的硬币（一个或多个），要么不使用。如果没有，我们仍然只能用 4 种硬币达到 100。但如果我们这样做，那么在使用一枚50 美分硬币后，总和变为 100 - 50 = 50 美分，我们仍然可以使用所有 5 种硬币来达到新的、更小的总和：

ways{ 100, 5 } = ways{ 100, 5 - 1 }      ;   never use any 50-cent coins
                 +                       ; OR
                 ways{ 100 - 50,  5 }    ;   may use 50-cent coins, so use one

或者一般来说，

ways( sum, k ) = ways( sum, k - 1 )
                 +
                 ways( sum - first_denomination(k),  k )

这里的所有都是它的。看？泛化自然伴随着抽象（用符号替换具体值并将它们作为函数定义中的参数）。

然后我们需要处理基本情况。如果sum = 0，则结果为 1：有一种方法可以使总和为 0（即：不拿硬币）。

如果k = 0，这意味着我们不允许使用任何种类的硬币；换句话说，我们无法在不使用至少一些硬币的情况下达到一个总和，任何总和（除非总和为 0，但我们已经在上面处理过这种情况）。所以结果一定是0。

sum < 0当然，如果 相同。不可能，即使用任何正面额的任何硬币来总结它的 0 种方法。

如果你愿意的话，另一种看待这个问题的方法是从时间箭头的另一端。

想象一下，有人已经为您完成了所有这些工作，并将所有这些成堆的账单放在您面前，每一堆加起来就是目标金额。不失一般性，让每一堆都被分类，以便更大的钞票在上面。

将所有纸币分成两组：一组纸币的顶部面额最大，另一组没有纸币。如果总堆数是ways( denomsList, targetSum)，那么显然第二组的堆数是ways( rest(denomsList), targetSum)。

然后，我们可以从第一组中的每一堆中取出最上面的钞票，并且其中的堆数显然不会因此而改变。删除了每一堆中最上面的钞票，我们看到它们的总和为targetSum - first(denomsList)，因此它们ways( denomsList, targetSum - first(denomsList))的总数为 。

（结构）递归的要点是从小处思考——不要试图立即描绘整个操作序列，而是静止不动并试图理解你当前的情况。它是解决问题的一种心理工具，它是以最简单、最自然的方式解决问题，迈出尽可能小的一步。

给自己打电话（副本）是一种技术性问题。最重要的是信仰的飞跃，你可以称自己为：假设你已经写下了你的定义，只要使用它是合适的。这就是它被写下来的方式。您只需描述您拥有的东西，它是如何由较小的部分组成的（其中一些类似于完整的东西），以及如何将这些部分的结果与其他部分组合起来以获得完整的解决方案。

编辑（来自评论）：递归解决问题的关键是要认识到它可以分解为较小的子问题的集合，我们正在寻求的相同的一般解决程序适用于每个子问题，并且总解决方案是然后以一些简单的方式从这些子问题的解决方案中找到（通过相同的一般程序找到，就好像它已经可供我们使用一样）。这样创建的每个子问题都“更小”，保证最终会达到基本情况。

换句话说，尝试找到问题中的结构，使其具有与整体相似的子结构（如分形；或者例如，列表的后缀也是列表；等等）；那么，递归是：假设我们已经有了解决方案；将问题实例分开（根据我们构建问题的方式）；通过解决方案转换“较小”的子结构；然后以某种简单的方式将它们组合起来（根据我们构建问题的方式）。诀窍是识别现有的, 问题中的固有结构，因此解决方案自然而然。

或者，在Prolog（所有编程语言中：））：

recursion(       In,  Out) :- 
  is_base_case(  In), 
  base_relation( In,  Out).

recursion(       In,  Out) :- 
  not_base_case( In),
  constituents(  In,   SelfSimilarParts,       LeftOvers),  % (* forth >>>    *)
  maplist( recursion,  SelfSimilarParts,
                             InterimResults),
  constituents(       Out,   InterimResults,   LeftOvers).  % (* and back <<< *)

也就是说，在伪代码中，

(In <--> Out) are related by recursion when
   either
      In is indivisible, and Out its counterpart
   or
      In  =  Sub_1 <+> Sub_2 <+> ... <+> Sub_N  <++>  Shell
             ------  r e c u r s i o n  ------
      Out =  Res_1 {+} Res_2 {+} ... {+} Res_N  {++}  Shell
        where
        (Sub_i <--> Res_i) ,  for each  i = 1, ..., N

和+的组合操作可能不同，因为它们可以是不同类型的值。InOut

于 2015-01-06T18:05:21.340 回答
7

如果我们在递归上想得太多，我们就已经失败了。就个人而言，我在思考递归时使用了两个隐喻。一本来自小书《小计谋》：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. 结合

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

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.

于 2015-01-07T02:52:10.593 回答
7

The first code box in Will Ness' answer above gave me enough insight to understand the algorithm. Once I understood it, I realized I'd probably have got there very quickly by actually seeing what the algorithm does step-by-step.

Below is the graph of how the algorithm proceeds for a simple case. The amount is 6 pence and we have two kinds of coin: five pence (index 2) and a penny (index 1).

Note that the leaf nodes all evaluate to 0 or 1. This is obvious when we look at the condition in the procedure (one of these values is returned, or else the function calls itself again.) Only two leaf nodes evaluate to 1, so there are 2 ways to make 6 pence from these two kinds of coin, i.e. 6 pennies, or a penny and a five pence.

I now understand the algorithm but I still don't see how I would have worked out the algorithm from the initial problem. Maybe, as I read more of the SICP book, this kind of solution will seem more obvious to me.

                             (cc 6 2)
                                |
                 -----------------------------------
                 |                                 |
              (cc 6 1)                          (cc 1 2)
                 |                                 |
   ------------------                         --------------
   |                |                         |            |
(cc 6 0)=0       (cc 5 1)                  (cc 1 1)     (cc -4 2)=0
                    |                         |
             -------------             -------------
             |           |             |           |
          (cc 5 0)=0  (cc 4 1)      (cc 1 0)=0  (cc 0 1)=1
                         |
               --------------
               |            |
            (cc 4 0)=0   (cc 3 1)
                            |
                     --------------
                     |            |
                  (cc 3 0)=0   (cc 2 1)
                                  |
                           --------------
                           |            |
                        (cc 2 0)=0   (cc 1 1)
                                        |
                                 --------------
                                 |            |
                              (cc 1 0)=0   (cc 0 1)=1
于 2016-09-22T20:48:11.780 回答