SICP делает изменение

Итак, Я любитель, который пытается работать через 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))

В любом случае; это рекурсивная процедура, и автор "бросает вызов", ища итеративную процедуру для решения одной и той же задачи (т.е. фиксированного пространства). Мне не посчастливилось выяснить это или найти ответ после разочарования. Мне интересно, если это мозг пердеть с моей стороны, или если автор напортачил со мной.

Ответ 1

Простейшим/наиболее общим способом устранения рекурсии, в общем, является использование вспомогательного стека - вместо того, чтобы делать рекурсивные вызовы, вы вставляете их аргументы в стек и повторяете. Когда вам понадобится результат рекурсивного вызова, чтобы продолжить, опять же в общем случае, что еще сложнее, потому что вам также придется нажать "запрос продолжения" (который выйдет из вспомогательного стек, когда результаты известны); однако в этом случае, поскольку все, что вы делаете со всеми результатами рекурсивного вызова, является суммированием, достаточно держать накопитель, и каждый раз, когда вы получаете результат числа, вместо необходимости делать больше вызовов, добавьте его в аккумулятор.

Однако это само по себе не является фиксированным пространством, так как этот стек будет расти. Итак, еще одна полезная идея: поскольку это чистая функция (без побочных эффектов), каждый раз, когда вы обнаруживаете, что вычислили значение функции для определенного набора аргументов, вы можете memoize соответствие аргументов-результатов. Это ограничит количество вызовов. Другим концептуальным подходом, который приводит к таким же вычислениям, является динамическое программирование [[aka DP]], хотя с помощью DP вы часто работаете снизу вверх результаты должны быть запомнены ", так сказать, вместо того, чтобы начинать с рекурсии и работать над ее устранением.

Возьмите снизу вверх DP на эту функцию, например. Вы знаете, что вы будете в конечном итоге "иметь много способов внести изменения в сумму X с помощью самой маленькой монеты" (поскольку вы уменьшаете вещи до X с различными комбинациями монет из оригинала amount), поэтому вы начинаете вычислять эти amount значения с простой итерацией (f (X) = X/value, если X точно делится на наименьшее значение монеты value, else 0, здесь value равно 1, поэтому f (X) = X для всех X > 0). Теперь вы продолжаете вычислять новую функцию 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), как указано выше, - и теперь вы выиграли ' t нужно f (X), чтобы вы могли повторно использовать это пространство. Всем сказали, что для этого потребуется пространство 2 * amount - не "фиксированное пространство", но, приближаясь...

Чтобы сделать окончательный переход к "фиксированному пространству", спросите себя: вам нужно поддерживать все значения двух массивов на каждом шаге (тот, который вы последний раз вычисляли, и тот, который вы сейчас вычисляете), или только некоторые из этих значений, немного изменив ваш цикл...?

Ответ 2

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

Основной цикл работает следующим образом; "денома - текущее деноминация", изменено общее значение монет в кошельке, "учитывая, какое количество изменений мне необходимо внести и" прояснить ", чтобы все монеты, меньшие, чем данное деноминация, из кошелька.

#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, я придумал идею кошелька, но только обошел его, чтобы заставить его работать.

Ответ 3

Здесь - это моя версия функции с использованием динамического программирования. Вектор размера n + 1 инициализируется до 0, за исключением того, что 0-й элемент изначально 1. Затем для каждой возможной монеты (внешней петли do) каждый векторный элемент (внутренний цикл do), начиная с k'th, где 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.

Ответ 4

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