SICP计数变化问题为什么N=xy？

Question

我是一个潜伏的门外汉，试图自学CS，目前正在努力完成SICP的第一章。

我遇到了“计数变化”示例程序，像其他人一样，尽管我理解这个程序本身，但我正在努力解决它所基于的前提：

假设我们认为可用的硬币类型是按一定顺序排列的。那么以下关系成立：

使用n种硬币改变数量的方法数量等于

>

使用所有n种硬币改变金额的方式数量a-d，其中d是第一种硬币的面额。

要了解为什么这是真的，请注意改变的方法可以分为两组：不使用任何第一种硬币的方法和使用第一种硬币的方法。因此，对某一金额进行更改的方式总数等于在不使用任何第一种硬币的情况下对该金额进行更改的方式数，加上假设我们使用第一种硬币的情况下进行更改的方式数。但后一个数字等于使用第一种硬币后剩余的硬币数量的改变方法的数量。

问题和过程可以在上下文中找到，但我不会包括过程，因为这是我正在努力解决的逻辑，而不是过程本身。

我不明白的是，为什么这些都是平等的：

1. “方式”的总数，减去在不使用第一种硬币的情况下获得全额的“方式”
2. 在减去第一枚硬币的面额后，使用所有类型的硬币制作剩余金额的“方式”的数量

我已经手动运行了无数个测试示例，是的，这种关系成立，但是我不明白为什么。

他们解释的第一句话很有道理：

请注意，做出改变的方式可以分为两组：不使用第一种硬币的人和使用第一种硬币的人。

如果我们有“方法”的总数，我们可以根据这个规则将总数分成两组。没问题。

第二句话也很清楚：

因此，改变某一金额的方法总数等于在不使用第一种硬币的情况下改变该金额的方法数，加上假设我们使用第一种硬币的方法数一种硬币。

这只是说明，总的方法数是被分为两类的方法的总和。好啊

这就是他们失去我的地方：

后一个数字等于使用第一种硬币后剩余金额的变化方式的数量。

我假设这意味着“后一个数字”指的是所有必须使用第一面额中至少一枚硬币的改变方式。

为什么这个数字等于所有硬币的总金额减去第一枚硬币的面额的兑换方式的数量，以及如何与之相等？

为了试着想象这个问题，我重申了这一点，即试图在杠铃上达到80公斤的特定重量，有三种重量标准：

1. 红色： 5Kg
2. 绿色： 10Kg
3. 蓝色： 20Kg

我把每个场景都视觉化了，确实这种关系成立了，但我仍然不明白为什么：

健美运动员的递归

感觉好像答案就在我的眼皮底下，但也许那个特定附属物的巨大尺寸会永远掩盖答案。

Answer 1

在其他回应者的帮助下，经过几天的思考，我认为这个问题可以通过在书的原始解释后面增加一个阐述来澄清（至少对我来说）：

但是后一个数字等于使用第一种硬币后剩余的金额的变化方式的数量。

我将新段落措辞如下：

这是因为我们可以假设，对于每个组合，必须包含至少一种我们已经使用过的第一种硬币（“交给”）的一个实例。我们只需要计算出改变剩余n的方法。

因此，在以下方面进行改变的方式数量没有差异：

1. 至少使用第一个面额中的一个面额的全额，以及
2. n减去使用任意数量硬币的第一个面额的金额

随后，我成功地编写了该问题的“称重室”版本，其输出与我的视觉解决方案相匹配：

(define (loadways weight plates)
(cond
   [(= weight 0) 1]
   [(or (= (length plates) 0) 
        (< weight 0)
        ) 0]
   [else (+ (loadways weight (cdr plates))
            (loadways (- weight (car plates)) plates))]
   ))  

(define weight-rack (list 20 10 5))

(loadways 40 weight-rack)

Answer 2

这里的诀窍是，考虑到一堆硬币的面额，其中一种我们称之为d，有两种方法可以兑换一定数量的a：

• 不要使用任何面额为d的硬币
• 至少使用一个d（我指的是“d”所指的“d”面额硬币）

而做出改变的方式总数就是这两种方式的总和（尤其是我们没有错过任何其他方式）。

所以，在第一种情况下，我们可以用除了d之外的所有面额来计算改变的方式的数量（我们显然要通过选择其他面额来做这件事

在第二种情况下，我们将使用至少一个d。所以我们知道，因为我们使用了至少一个d，所以A的量可以被拆分为A=d（A-d）：这就是“使用至少一个d”的意思。那么现在有多少种方法可以组合成这样的硬币呢？答案是，这是一个数量（A-d）的改变方式的数量，但这次我们仍然可以使用ds来改变。

Answer 3

让我们想象一种简化的货币，只有1和5面额。我要求你拿出15美元，条件是你给我的硬币中至少有一枚必须是5美元。你有多少种方法可以做到这一点？在这一点上，你可以尝试生成所有的方法来产生15的变化，然后扔掉所有不符合我要求的方法。但是很容易观察到，你也可以从留出一个5来满足我的需求开始，然后想出如何以你选择的任何方式改变剩下的10。