0

我试图用 M=10、c={5,3,1} 和 d=3 来追踪硬币找零问题的递归算法。M 是需要找零的货币价值，c 是可用的不同硬币价值，d 是可用的不同硬币价值的数量。我对如何追踪它感到困惑。

RecursiveChange(M,c,d)

if M = 0
    return 0
bestNumCoins <- infinity
for i -> 1 to d
    if M ≥ c(i)
        numCoins <- RecursiveChange(M – c(i) , c, d)
        if numCoins + 1 < bestNumCoins
            bestNumCoins <- numCoins + 1
    return bestNumCoins

调用 1：RecursiveChange(10, {5, 3, 1}, 3)

调用 2：RecursiveChange(5, {5, 3, 1}, 3)

调用 3：RecursiveChange(0, {5, 3, 1}, 3)

在调用 3 中，由于 M=0，将返回 0。我的理解是：0 返回到调用 2。然后，从调用 2 继续，运行以下部分：

if numCoins + 1 < bestNumCoins
                bestNumCoins <- numCoins + 1
        return bestNumCoins

其中 bestNumCoins 将取值 1。然后将这个值 1 返回给调用 1。然后，从调用 1 继续，因为 numCoins + 1（即 2）不 < bestNumCoins（即 1），bestNumCoins 将保持为 1，并且然后这个值 1 将是最终值。首先，我认为 2 应该是这里的最终值，因为要获得 10 个单位，需要两个价值 5 的硬币。

我需要帮助来解决这个问题，拜托。我已经花了好几个小时了。

4

1 回答 1

0

bestNumCoins意味着是一个局部变量，这意味着对函数的每次调用都有自己单独的值bestNumCoins。

尽管在调用 #2bestNumCoins中设置为 1，但在调用 #1 中，它的值仍然是无穷大。在对#2 的调用返回值1 后，bestNumCoins在调用#1 中将更改为值2（返回值加1）。

于 2014-09-21T15:10:53.567 回答