optimization - SICP做出改变

Question

所以; 我是一个正在尝试通过 SICP 工作的爱好者（它是免费的！），第一章中有一个示例程序，旨在计算用美国硬币找零的可能方法；(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))

反正; 这是一个树递归过程，作者“作为一个挑战离开”找到一个迭代过程来解决相同的问题（即固定空间）。在感到沮丧之后，我没有运气弄清楚这一点或找到答案。我想知道这是我的脑放屁，还是作者在和我开玩笑。

Answer 1

一般来说，消除递归的最简单/最通用的方法是使用辅助堆栈——而不是进行递归调用，而是将它们的参数推入堆栈并迭代。当您需要递归调用的结果才能继续时，同样在一般情况下，这有点复杂，因为您还必须能够推送“继续请求”（这将脱离辅助当结果已知时堆栈）；但是，在这种情况下，由于您对所有递归调用结果所做的只是求和，因此保留一个累加器就足够了，并且每次得到一个数字结果而不是需要进行更多调用时，将其添加到累加器。

但是，这本身并不是固定空间，因为该堆栈会增长。所以另一个有用的想法是：因为这是一个纯函数（没有副作用），所以任何时候你发现自己已经计算了某个参数集的函数值，你可以记住参数-结果的对应关系。这将限制调用次数。导致相同计算的另一种概念方法是动态编程[[aka DP]]，尽管使用 DP，您通常可以自下而上地“准备要记忆的结果”，而不是从递归开始并努力消除它。

以这个函数的自下而上 DP 为例。你知道你会反复得到“多少种方法可以用最小的硬币来改变金额 X”（当你用原始的各种硬币组合将事情减少到 X 时amount），所以你开始计算这些amount值简单迭代（f(X) = X/ valueifX可以被最小的硬币值整除value，否则0；这里value是 1，所以对于所有 X>0，f(X)=X）。现在您继续计算一个新函数 g(X)，用两个最小硬币对 X 进行更改的方法：再次简单迭代以增加 X，其中 g(x) = f(X) + g(X - value) 为这value的第二小的硬币（这将是一个简单的迭代，因为当你计算 g(X) 时，你已经计算并存储了 f(X)和所有 g(Y) 对于 Y < X - 当然, g(X) = 0 对于所有 X <= 0)。再次对于 h(X)，用三个最小的硬币为 X 找零的方法- h(X) = g(X) + g(X- value) 如上所述 - 从现在开始你将不需要 f (X) 更多，因此您可以重复使用该空间。总而言之，这需要空间2 * amount——还不是“固定空间”，但是，越来越近了……

为了实现“固定空间”的最后飞跃，问问自己：你是否需要在每一步都保留两个数组的所有值（你最后计算的一个和你当前正在计算的一个），或者只保留其中的一些值，通过重新安排你的循环一点点......？

Answer 2

这是我使用动态编程的函数版本。一个大小为 n+1 的向量初始化为 0，除了第 0 项最初为 1。然后对于每个可能的硬币（外部 do 循环），每个向量元素（内部 do 循环）从第 k 个开始，其中 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运行此程序。

Answer 3

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

看，这种cc-pennies写法的问题是，因为没有更低的面额，所以它通过模仿更高面额程序的结构所做的就是从(- amount 1)to向下迭代0，每次你传递它时它都会这样做程序的金额cc-nickels。因此，在第一次通过时，如果您尝试 1 美元，您将得到amount100，因此(- amount 1)计算结果为99，这意味着您将经历 99 个多余的cc-pennies和cc-nothing循环。然后，五分钱将95作为数量传递给您，因此您会再浪费 94 个循环，依此类推。而这一切都在你向上移动到一角钱、四分之一美元或半美元之前。

当您到达 时cc-pennies，您已经知道您只想将累加器加一，所以我建议进行以下改进：

(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))

希望你发现这很有用。

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 的回答后，我想出了钱包的想法，但只是想办法让它发挥作用

Answer 5

您可以在伪多项式时间内使用动态规划迭代求解。