SICP找零

Question

因此;我是谁试图通过SICP工作一个业余爱好者（它是免费的！），并存在这样是为了计数可能的方式，以与美国硬币变化的第一章的示例过程; （转换器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

消除递归，一般最简单的/最通常的方式是使用辅助堆垛 - 而不是使递归调用，你把他们的论点入堆栈，并反复。当你需要为了在一般的情况下进行，再次递归调用的结果，这是一个稍微更复杂，因为你也将不得不能推动一个“连续请求”（即会关闭辅助叠时的结果是已知的）;然而，在这种情况下，因为所有你所有的递归调用的结果做一个总结，这是足以让一个蓄电池和，每次你得到一个数字结果，而不是一个需要做更多的通话时间，将其添加到累加器。

然而，这本身，是不的固定空间，因为该堆将增长。因此，另一种有益的观点是：因为这是一个纯函数（没有副作用），你会发现自己已经计算函数的值一组特定的参数中的任何时候，你可以的 memoize的参数-结果对应。这将限制呼叫的数量。导致大致相同的另一种计算概念上的方法是动态规划 [又名DP]，虽然与DP你经常锻炼自下而上“的编制结果被memoized”，可以这么说，而不是用递归开始，努力消除它。

以自下而上DP关于此函数，例如。你知道你会反复用“多少办法，使对于只有最小的硬币量X变”结束了（你消减下来的东西与从原来的amount各种硬币组合X），于是你开始计算这些amount值用一个简单的迭代（F（X）= X / value如果X是由最小的硬币值value，否则0整除;在这里，value是1，因此f（X）= X为所有的X> 0）。现在你继续通过计算一个新的函数g（x）的方式，使改变为X与双的最小硬币：再简单的迭代增加X，与G（X）= F（X） + G - 为对第二小的硬币的value（X value）（这将是一个简单的迭代，因为由一次你计算G（X）您已计算和存储F（X）的和用于Y 3 最小硬币X - H（X）= G（X）+ G（X-value）如上 - 和从现在开始，您将不再需要F（X）了，所以你可以重复使用的是的空间。总而言之，这将需要空间2 * amount - 没有“固定的空间”，但，但，越来越近......

要作出最后的飞跃“固定空间”，问问自己：你需要保持周围的所有的每一步（一个你最后计算的，你是一个两列的值目前计算），或者，只有部分的那些价值观，通过重新安排你的循环一点点......？

Answer 2

我想出了一个解决办法是保持硬币的每种类型的您正在使用的“钱包”

计数

在主循环是这样工作的; “denom为目前的面额，”改变是在钱包，硬币的总价值“给出的变化我需要和金额”明确了对通吃小于给定面额较小的硬币出钱包

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

阅读亚历马尔泰利的答案后，我想出了钱包的想法，但只得到周围使其工作

Answer 3

这里是我的版本的功能，使用动态编程。大小为n + 1的向量被初始化为0，除了第0项是最初1.然后，对于每个可能的硬币（外侧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 。

此程序

Answer 4

所以，在这个线程，问题的原提问者来了一个声音回答通过模块化。然而，我建议的是，他的码可以很容易地优化如果注意到cc-pennies完全是多余的（并且通过扩展，所以是cc-nothing）

请参阅，同程cc-pennies写入的问题是，因为没有低面额去，所有它将被模仿的高面额的程序结构从(- amount 1)向下迭代，以0做的，它会做到这一点每一次你通过它从cc-nickels程序的数量。因此，在第一轮，如果你尝试1美元，你会得到100的amount，所以(- amount 1)计算为99，这意味着你将经历cc-pennies和cc-nothing周期的99多余次。然后，镍会把你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 5

可以在伪多项式时间动态规划迭代地解决这个问题。