计算机程序结构和解释中的计数变化示例树递归部分

Question

在第1.2节中。在经典的文本结构和计算机程序的解释中，有一个例子说明了如何计算将一笔钱分成更小面额的方法的数量。以下是他们写的语言：

想出迭代斐波那契算法只需要一点小聪明。相比之下，考虑以下问题：我们可以用多少种不同的方法来找1美元的零钱，给0.5美元、25美分、10美分、5美分和1美分？更一般地说，我们可以写一个过程来计算改变任何给定金额的方式的数量吗？

这个问题有一个简单的递归过程解决方案。假设我们认为可用的硬币类型是按某种顺序排列的。那么以下关系成立：

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

...除第一种硬币外，使用其他硬币更改金额a的方法的数量，加上更改金额a的方法的数量− d使用所有n种硬币，其中d是第一种硬币的面额。

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

我的问题是关于最后一个陈述。我们谈论的是一美元（尽管他们后来建议尝试用更小的金额来解决这个问题，比如10美分）——为什么打破一美元的方法总是等于打破剩余金额的方法数量从一美元中取出一个面额的硬币（即一美元减去单个硬币的数量）后？

Answer 1

假设我们有各种方法可以兑换美元，我们可以选择任何面额，比如四分之一（25美分）。我们可以通过解决方案将它们分为使用四分之一和不使用四分之一：

"1美元的所有解决方案"="使用四分之一的1美元解决方案""不使用四分之一的1美元解决方案"

作者声称“使用四分之一的1美元的所有解决方案”与“75c的所有解决方案”大小相同。你可以直观地看到这是真的。形式上你可以说：

a） “使用四分之一的1美元解决方案”

b）"75c的所有解决方案"

因此，它们必须大小相同，即：

Size of "solutions for $1 that use a quater" 
    = Size of "all solutions for 75c"

因此：

Size of "All solutions for $1" = 
    Size of "solutions for $1 that use a quater"
    + Size of "solutions for $1 that don't use a quater"

可以重写为：

Size of "All solutions" = 
    Size of "all solutions for 75c"
    + Size of "solutions for $1 that don't use a quater"