SICP 计算找零

Question

所以，我是一个业余爱好者，正在努力学习《计算机程序的构造和解释》（免费下载！）。在第一章中有一个示例过程可以计算使用美国硬币进行找零的可能方式；(change-maker 100) => 292。它的实现大致如下：

(define (change-maker amount)
  (define (coin-value n)
    (cond ((= n 1) 1)
          ((= n 2) 5)
          ((= n 3) 10)
          ((= n 4) 25)
          ((= n 5) 50)))

  (define (iter amount coin-type)
    (cond ((= amount 0) 1)
          ((or (= coin-type 0) (< amount 0)) 0)
          (else (+ (iter amount
                         (- coin-type 1))
                   (iter (- amount (coin-value coin-type))
                         coin-type)))))

  (iter amount 5))

无论如何，这是一个树形递归过程，作者们“留下挑战”是找到一种迭代过程来解决同样的问题（即在固定空间内）。我没有运气弄清楚这个问题或在沮丧后找到答案。我想知道我是不是被卡住了，还是作者在和我玩。

- RyanD

---

http://c2.com/cgi/wiki?SicpIterationExercise 对此进行了广泛讨论，并在最后给出了一个或多个相对完整的解决方案。 - Nietzche-jou

Answer 1

最简单/最通用的消除递归的方法是使用辅助栈——而不是进行递归调用，将它们的参数推入栈中并迭代。当你需要递归调用的结果以便继续进行时，在一般情况下，这会略微复杂，因为你还需要能够推送“继续请求”（当结果知道时从辅助栈中出来）；然而，在这种情况下，由于你只是对所有递归调用结果进行求和，所以保持一个累加器就足够了，每次得到一个数字结果而不是需要进行更多调用时，将其添加到累加器中即可。

然而，这本质上并不是固定空间，因为该栈会增长。因此，另一个有用的想法是: 由于这是一个纯函数（没有副作用），每当你发现已经计算出某个特定参数集的函数值时，你可以将参数-结果对应关系memoize。这将限制调用的数量。另一个导致大致相同计算的概念方法是 dynamic programming [[也称为DP]]，虽然在DP中，你经常从底层向上工作，"准备要进行记忆化的结果"，而不是从递归开始并工作以消除它。

以这个函数为例，采用自底向上的动态规划。你会反复得到“使用最小硬币来找零X元有多少种方法”（因为你不断地用各种硬币组合将事物缩小到X），所以你开始使用简单迭代计算这些金额值（如果X恰好可被最小硬币值value整除，则f(X)=X/value，否则f(X)=0；在这里，value为1，因此对于所有X>0，f(X)=X）。现在你继续通过计算一个新的函数g(X)来进行，即使用两个最小硬币的方式来找零X：再次进行递增X的简单迭代，其中g(X)=f(X)+g(X-value)，value是第二个最小硬币的价值（这将是一个简单的迭代，因为在计算g(X)时，您已经计算并存储了f(X)和所有Y2 * amount的空间——虽然还不是“固定空间”，但已经越来越接近了...

为了实现最终的“固定空间”，请问自己：在每一步中，您是否需要保留两个数组的所有值（您上次计算的数组和您当前正在计算的数组），还是通过稍微重新排列循环，只需保留某些值？

- Alex Martelli

---

我对你在这里提到的迭代方法有一些疑问，如果你能澄清一下就好了：

1. 你说f(X) = X/value，如果X恰好可以被最小硬币价值整除，则为X/value，否则为0。难道不应该是f(X) = 1，如果X完全可以被value整除，否则为0吗？
2. 如果我对上面的问题1的理解是正确的，我们如何修改这个方法来找到原始金额的“最少硬币数量”？

- lambdapilgrim

1. 如果 X 能被某个值整除，我认为 f(X) 应该为 1。
2. 我认为 f(0), g(0), h(0) 也应该是 1，因为 g(5) = f(5) + g(0)，而且用 1 分和 5 分硬币组成 5 分有两种方式，所以 g(5) 应该为 2。
3. 因为我们知道 g(5) = 2，所以我们可以说 g(10) = f(10) + g(5) = 3，这样 g(100) 就等于 21。
4. h(10) = g(10) + h(0) = 4，h(20) = g(20) + h(10)，这样，我们可以用循环计算出 h(100)，然后计算 i(100)，其值为 25，再计算 j(100)，其值为 50，这将得到数字 292。

- Peng Qi

除了上面的评论之外，我想指出方程式“h(X) = g(X) + g(X-value)”应该是“h(X) = g(X) + h(X-value)”，就我所看到的而言。 - Mark

Answer 2

因此，在this thread中，问题的原始提出者通过模块化提出了一个合理的答案。然而，我建议，如果您注意到cc-pennies完全是多余的（以及扩展的cc-nothing），他的代码可以很容易地进行优化。

看，cc-pennies的问题在于，由于没有更小的面额可以使用，所以它模仿更高面额程序的结构时，会从(- amount 1)迭代到0，并且每次你从cc-nickels过程传递给它一个金额时都会这样做。因此，在第一次通过时，如果您尝试1美元，您将得到100的amount，因此(- amount 1)计算为99，这意味着您将经历99个多余的cc-pennies和cc-nothing周期。然后，nickels会将95作为金额传递给您，因此您会浪费94个以上的周期，依此类推。而且这还只是在您上升到角、25美分或半美元之前。

当您到达cc-pennies时，您已经知道只需将累加器增加1，因此我建议进行以下改进:

(define (count-change-iter amount)
    (cc-fifties amount 0))

(define (cc-fifties amount acc)
    (cond ((= amount 0) (+ 1 acc))
        ((< amount 0) acc)
        (else (cc-fifties (- amount 50)
                (cc-quarters amount acc)))))

(define (cc-quarters amount acc)
    (cond ((= amount 0) (+ 1 acc))
        ((< amount 0) acc)
        (else (cc-quarters (- amount 25)
                (cc-dimes amount acc)))))

(define (cc-dimes amount acc)
    (cond ((= amount 0) (+ 1 acc))
        ((< amount 0) acc)
        (else (cc-dimes (- amount 10)
                (cc-nickels amount acc)))))

(define (cc-nickels amount acc)
    (cond ((= amount 0) (+ 1 acc))
        ((< amount 0) acc)
        (else (cc-nickels (- amount 5)
                (cc-pennies amount acc)))))

(define (cc-pennies amount acc)
    (+ acc 1))

希望您觉得这很有用。

- user242007

Answer 3

这里是我使用动态规划的函数版本。一个大小为n+1的向量被初始化为0，除了0号元素最初为1。然后对于每个可能的硬币（外部do循环），从第k个开始的每个向量元素（内部do循环），其中k是硬币的价值，都会增加当前索引减去k的值。

(define (counts xs n)
  (let ((cs (make-vector (+ n 1) 0)))
    (vector-set! cs 0 1)
    (do ((xs xs (cdr xs)))
        ((null? xs) (vector-ref cs n))
      (do ((x (car xs) (+ x 1))) ((< n x))
        (vector-set! cs x (+ (vector-ref cs x)
          (vector-ref cs (- x (car xs)))))))))

> (counts '(1 5 10 25 50) 100)
292

您可以在http://ideone.com/EiOVY上运行此程序。

- user448810

Answer 4

我想到的解决方案是在一个“钱包”中记录每种硬币的数量。

主循环的工作方式如下：'denom' 是当前面额，'changed' 是钱包中硬币的总价值，'given' 是我需要找回的零钱金额，'clear-up-to' 取出钱包中小于给定面额的所有硬币。

#lang scheme
(define (sub changed denom)
  (cond
   ((> denom largest-denom)
    combinations)

   ((>= changed given)
    (inc-combinations-if (= changed given))

    (clear-up-to denom)
    (jump-duplicates changed denom)) ;checks that clear-up-to had any effect.

   (else
    (add-to-purse denom)
    (sub
     (purse-value)
     0
     ))))

(define (jump-duplicates changed denom)
  (define (iter peek denom)
    (cond
     ((> (+ denom 1) largest-denom)
      combinations)

     ((= peek changed)
      (begin
        (clear-up-to (+ denom 1))
        (iter (purse-value) (+ denom 1))))

      (else
       (sub peek (+ denom 1)))))
  (iter (purse-value) denom))

在阅读了Alex Martelli的回答后，我想到了这个钱包的主意，但直到现在才开始让它发挥作用。

- RyanD

Answer 5

你可以使用动态规划的迭代方法在伪多项式时间内解决它。

- newacct