SICP例子：计数变化，无法理解-Java 学习之路

我是麻省理工学院开放式课程的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)))

如果你想检查更多，我从here .

他们通过添加以下内容计算使用K种硬币改变数量（N）的数量（N）：

在没有第一类硬币的情况下改变A的方式（X）的数量 .
改变（A - D）的方式（Y）的数量，其中D是fisrt硬币的面额，使用所有K种类型的硬币 .

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

“要明白为什么这是真的，请注意，改变的方式可以分为两组：那些不使用任何第一种硬币的那些，以及那些使用任何第三种硬币的方法 . 因此，改变方法的总数某些金额等于不使用任何第一种硬币进行金额变更的方式数量，加上假定我们使用第一种硬币进行变更的方式数量 . (Is the last sentence the same as the addition N = X + Y ? ) 但是后者的数字等于使用第一种硬币后剩余金额的变化方式. (After using this coin, they refer to ways of making change with or without the first kind of coin? ) “

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

3 回答

5
如果我们认为递归太过困难，我们就已经失败了 . 就个人而言，我在思考递归时使用了两个隐喻 . 一个来自小书"the little schemer"： The Seventh Commandment - Recur on the subparts that are of the same nature . 另一个是用于设计算法的分治 - 组合范式 . 从本质上讲，它们在如何递归思考方面是相同的 .
- 除以相同性质的子部分
问题有两个变量：货币的数量（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在第二部分减少 . 两者都是相同的性质，可以递归地解决，它们在一起是最初的问题 .
- 征服
在这一步中，我考虑了基本情况 . 当问题减少到可以直接给出答案的最小值时，所有基本情况是什么？在这个解决方案中，有三种基本情况 . 第一个是N减少到0.第二个是N减少到负数 . 第三是硬币减少到0但N仍然是正数 .
- 结合
解析子部分时如何组合结果 . 在这个解决方案中，它们很简单 .

更重要的是，如果我们在列表上递归，则除法通常是列表中的汽车和列表的cdr . 如果自己不是列表，通常可以直接解决列表中的汽车 . cdr部分应该递归解决 . 如果满足，基本情况是列表的结尾 .

B.T.W，我强烈推荐 the little schemer 用于学习递归 . 就我所读到的而言，在这个特定点上它比其他任何人都要好得多 .
回复于 2024-04-29T21:05:24+08:00
4
“数量（N）的方式......使用N种”这两个N显然不一样 . 让我们说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种方式来总结它，使用任何正面额的硬币 .

对（结构）递归的观点是小思考 - 不是试图一次性描绘整个操作序列，而是试图理解你当前的情况 . 它是解决问题的心理工具，它是以最简单最自然的方式解决问题，尽可能小的一步 .

自己打电话（a copy of）是一种技术性问题 . 最重要的是信念的飞跃，你可以自称：假设你已经写下了你的定义，只需使用它就是合适的 . 那是how it gets written down . 你只需要描述你拥有的东西，它是如何制成的（它们中的一些类似于完整的东西），以及如何将这些部分的结果组合起来以获得你所拥有的完整解决方案 .

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

换句话说，尝试在问题中找到结构，使其具有与整体相似的子结构（如分形;例如，列表的后缀也是列表;等等）;然后，递归是：假设我们已经有了解决方案;将问题实例分开（根据我们构建问题的方式）;通过解决方案转换"smaller"子结构;以一种简单的方式将它们组合在一起（根据我们构建问题的方式） . 诀窍是识别问题中现有的固有结构，以便解决方案自然而然 .

或者，在Prolog中：
```
recursion( In, Out) :- 
  is_base_case( In), 
  base_relation( In, Out).

recursion( In, Out) :- 
  is_not_base_case( In),
  constituents( In, SelfSimilarParts, LeftOvers),        % forth
  maplist( recursion, SelfSimilarParts, InterimResults),
  constituents( Out, InterimResult, LeftOvers).          % and back
```
回复于 2024-04-29T21:05:24+08:00

Will Ness上面回答的第一个代码框给了我足够的洞察力来理解算法 . 一旦我理解了它，我意识到我可能很快就会通过实际查看算法逐步执行的操作来实现目标 .

下面是算法如何针对简单情况进行的图表 . 金额为6便士，我们有两种硬币：五便士（指数2）和便士（指数1） .

请注意，叶节点都计算为0或1.当我们查看过程中的条件时（这些值中的一个被返回，或者函数再次调用自身），这是显而易见的 . ）只有两个叶节点计算为1，所以有两种方法可以从这两种硬币制作6便士，即6便士，或一便士和五便士 .

我现在理解算法，但我仍然没有看到我如何从最初的问题中找出算法 . 也许，当我阅读更多关于SICP的书时，这种解决方案对我来说似乎更为明显 .

(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

回复于 2024-04-29T21:05:24+08:00

SICP例子：计数变化，无法理解

3 回答

相关问题