algorithm - SICP 示例 : Counting change, 无法理解

Question

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

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

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

如果你想查看更多，我是从 here 获取的.

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

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

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

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

“要明白为什么这是真的，请观察改变的方式可以分为两组:那些不使用任何第一种硬币的人，以及那些使用的。因此，改变的方式总数for some amount 等于在不使用任何第一种硬币的情况下对该金额进行找零的方式数量，加上假设我们确实使用第一种硬币的情况下进行找零的方式数量。 (是最后一句与加法相同 N = X + Y ? ) 但后一个数字等于使用第一种硬币后剩余金额的找零次数。 (用完这枚硬币后，他们指的是有没有第一种硬币的找零方式？)”

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

Answer 1

“方法数(N)...使用N种”这两个N s 显然不一样。所以让我们说 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))总共。

(结构)递归的要点是小规模思考——不是试图一次描绘整个操作序列，而是站在原地不动并试图了解您当前的情况。它是解决问题的心理工具，它是以最简单最自然的方式解决问题，使一步尽可能小。
给自己打电话 ( a copy of ) 是一个技术问题。最主要的是信仰的飞跃，你可以这样称呼自己:假设你已经写下了你的定义，就用它是合适的。那就是 how it gets written down .您只需描述您拥有的东西，它是如何由较小的部分组成的(其中一些类似于完整的部分)，以及如何将这些部分的结果与其余部分结合起来以获得完整的解决方案。

编辑(来自评论):递归解决问题的关键是认识到它可以分解为一系列较小的子问题，我们正在寻求的相同的一般解决程序适用于每个子问题，并且总解决方案是然后以某种简单的方式从这些子问题的解决方案中找到(通过相同的一般程序找到，就好像它已经可供我们使用一样)。这样创建的每个子问题都“更小”，保证最终会达到基本情况。
换句话说，尝试找到问题中的结构，使其具有与整体相似的子结构(如分形；或者例如列表的后缀也是列表；等等)；那么，递归是:假设我们已经有了解决方案；拆分问题实例(根据我们构建问题的方式)；通过解决方案转换“较小”的子结构；然后以某种简单的方式将它们全部组合回来(根据我们构建问题的方式)。诀窍是识别问题中现有的固有结构，以便自然而然地找到解决方案。
或者，在 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

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