SICP making change

Asked
Viewd4223

13

So; I'm a hobbyist who's trying to work through SICP (it's free!) and there is an example procedure in the first chapter that is meant to count the possible ways to make change with american coins; (change-maker 100) => 292. It's implemented something like:

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

Anyway; this is a tree-recursive procedure, and the author "leaves as a challenge" finding an iterative procedure to solve the same problem (ie fixed space). I have not had luck figuring this out or finding an answer after getting frustrated. I'm wondering if it's a brain fart on my part, or if the author's screwing with me.

  • http://c2.com/cgi/wiki?SicpIterationExercise подробно обсуждает это и предлагает более или менее полное решение в конце.

    Nietzche-jou28 сентября 2009, 20:47

5 ответов

12

The simplest / most general way to eliminate recursion, in general, is to use an auxiliary stack -- instead of making the recursive calls, you push their arguments into the stack, and iterate. When you need the result of the recursive call in order to proceed, again in the general case, that's a tad more complicated because you're also going to have to be able to push a "continuation request" (that will come off the auxiliary stack when the results are known); however, in this case, since all you're doing with all the recursive call results is a summation, it's enough to keep an accumulator and, every time you get a number result instead of a need to do more call, add it to the accumulator.

However, this, per se, is not fixed space, since that stack will grow. So another helpful idea is: since this is a pure function (no side effects), any time you find yourself having computed the function's value for a certain set of arguments, you can memoize the arguments-result correspondence. This will limit the number of calls. Another conceptual approach that leads to much the same computations is dynamic programming [[aka DP]], though with DP you often work bottom-up "preparing results to be memoized", so to speak, rather than starting with a recursion and working to eliminate it.

Take bottom-up DP on this function, for example. You know you'll repeatedly end up with "how many ways to make change for amount X with just the smallest coin" (as you whittle things down to X with various coin combinations from the original amount), so you start computing those amount values with a simple iteration (f(X) = X/value if X is exactly divisible by the smallest-coin value value, else 0; here, value is 1, so f(X)=X for all X>0). Now you continue by computing a new function g(X), ways to make change for X with the two smallest coins: again a simple iteration for increasing X, with g(x) = f(X) + g(X - value) for the value of the second-smallest coin (it will be a simple iteration because by the time you're computing g(X) you've already computed and stored f(X) and all g(Y) for Y three smallest coins -- h(X) = g(X) + g(X-value) as above -- and from now on you won't need f(X) any more, so you can reuse that space. All told, this would need space 2 * amount -- not "fixed space" yet, but, getting closer...

To make the final leap to "fixed space", ask yourself: do you need to keep around all values of two arrays at each step (the one you last computed and the one you're currently computing), or, only some of those values, by rearranging your looping a little bit...?

1

Итак, в этой ветке исходный вопрос, задавший вопрос, дает здравый ответ. через модуляризацию. Я бы предположил, однако, что его код можно легко оптимизировать, если вы заметите, что cc-pennies совершенно лишний (и, по расширению, cc-nothing)

Видите ли, проблема с тем, как написано cc-pennies, заключается в том, что, поскольку нет более низкого достоинства, все, что он будет делать, имитируя структуру процедур более высокого достоинства, - это итерация вниз от (- amount 1) до 0, и он будет делать это каждый раз, когда вы передаете ему сумму из процедуры cc-nickels. Итак, на первом проходе, если вы попробуете 1 доллар, вы получите amount из 100, поэтому (- 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))
 

Надеюсь, вы нашли это полезным.

1

Вот моя версия функции с использованием динамического программирования . Вектор размера 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 .

1

Решение, которое я придумал, - вести учет каждого типа монет, которые вы используете в «кошельке»

Основной цикл работает следующим образом; 'denom - текущий номинал', 'изменен' - общая стоимость монет в кошельке, '' задано '' - это сумма сдачи, которую мне нужно внести, '' 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))
 

Прочитав ответ Алекса Мартелли, мне в голову пришла идея кошелька, но я просто нашел время, чтобы заставить ее работать

-2

Вы можете решить эту проблему итеративно с помощью динамического программирования за псевдополиномиальное время.