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

Question

在经典著作《计算机程序结构与解释》的 1.2.2 节中，有一个例子说明了如何计算将一笔钱分成较小面额的方法的数量。这是他们写的语言：

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

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

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

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

要了解为什么这是真的，请观察做出改变的方式可以分为两组：不使用任何第一种硬币的方式，以及使用的方式。因此，找零的方式总数等于不使用任何第一种硬币的找零方式的数量，加上假设我们确实使用了找零的方式的数量。第一种硬币。但后一个数字等于使用第一种硬币后剩余数量的找零方式的数量。

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

标签： algorithmrecursioncomputer-sciencesicpcoin-change

Answer 1

假设我们有各种方法可以兑换美元，并且我们可以选择任何面额，假设是 quater (25c)。我们可以通过解决方案将它们分为使用 quater 和不使用 quater 的解决方案：

“1 美元的所有解决方案”=“使用 quater 的 1 美元解决方案”+“不使用 quater 的 1 美元解决方案”

作者声称“使用 quater 的 1 美元的所有解决方案”的大小与“75c 的所有解决方案”的大小相同。你可能会直觉地看到这是真的。正式地说，你可以说：

a）“使用 quater 的 1 美元解决方案”<=“75c 的所有解决方案”，因为对于每个“使用 quater 的 1 美元解决方案”，您可以删除 quater 并获得 75c 的解决方案。

b）“75c 的所有解决方案”<=“使用 quater 的 1 美元解决方案”，因为对于 75c 的每个解决方案，您可以添加一个 quater 并获得“使用 quater 的 1 美元解决方案”中的解决方案。

所以它们必须是相同的大小，即：

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"