SICP вносит изменения
https://stackoverflow.com/questions/1485022
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Итак;Я любитель, который пытается работать через 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))
В любом случае;это древовидно-рекурсивная процедура, и автор "оставляет в качестве задачи" поиск итеративной процедуры для решения той же проблемы (т. е. фиксированного пространства).Мне не повезло разобраться в этом или найти ответ после того, как я разочаровался.Мне интересно, является ли это пердежом с моей стороны, или автор издевается надо мной.
Решение
Самый простой / наиболее общий способ устранить рекурсию, в общем случае, заключается в использовании вспомогательного стека - вместо выполнения рекурсивных вызовов вы помещаете их аргументы в стек и выполняете итерацию.Когда вам нужен результат рекурсивного вызова для продолжения, опять же в общем случае, это немного сложнее, потому что вам также нужно будет иметь возможность отправлять "запрос на продолжение" (который будет удален из вспомогательного стека, когда результаты будут известны);однако в этом случае, поскольку все, что вы делаете со всеми результатами рекурсивного вызова, - это суммирование, достаточно сохранить накопитель и каждый раз, когда вы получаете числовой результат вместо необходимости выполнять дополнительные вызовы, добавлять его в накопитель.
Однако это, по сути, является не фиксированный пробел, так как этот стек будет расти.Итак, еще одна полезная идея заключается в:поскольку это чистая функция (без побочных эффектов), каждый раз, когда вы обнаруживаете, что вычислили значение функции для определенного набора аргументов, вы можете запоминать соответствие аргументов-результату.Это ограничит количество звонков.Другим концептуальным подходом , который приводит во многом к тем же вычислениям , является динамическое программирование [[он же DP]], хотя с DP вы часто работаете снизу вверх, "подготавливая результаты для запоминания", так сказать, вместо того, чтобы начинать с рекурсии и работать над ее устранением.
Возьмем, к примеру, восходящий DP для этой функции.Вы знаете, что неоднократно будете сталкиваться с вопросом "сколько способов внести изменения на сумму X с помощью всего лишь самой маленькой монеты" (по мере того, как вы сокращаете количество до X с помощью различных комбинаций монет из оригинала amount), итак, вы начинаете вычислять эти amount значения с простой итерацией (f(X) = X/value если X в точности делится на наименьший номинал монеты value, остальное 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) как указано выше - и с этого момента вам больше не понадобится f (X), так что вы можете использовать повторно это Космос.В общем, для этого потребуется место 2 * amount -- еще не "фиксированное пространство", но приближается...
Чтобы совершить последний прыжок в "фиксированное пространство", спросите себя:тебе нужно быть рядом ВСЕ значения двух массивов на каждом шаге (тот, который вы вычисляли последним, и тот, который вы вычисляете в данный момент), или, только некоторые из этих значений, немного изменив свой цикл ...?
Другие советы
Решение, которое я придумал, состоит в том, чтобы вести учет каждого типа монет, которые вы используете в "кошельке"
Основной цикл работает следующим образом;'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))
Прочитав ответ Алекса Мартелли, мне пришла в голову идея кошелька, но я только собрался воплотить ее в жизнь
Здесь это моя версия функции, использующая динамическое программирование.Вектор размером 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.
Итак, в этот поток, первоначальный задавший вопрос дает обоснованный ответ с помощью модульности.Однако я бы предположил, что его код можно легко оптимизировать, если вы заметите, что 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))
Надеюсь, вы нашли это полезным.
Вы можете решить ее итеративно с помощью динамического программирования за псевдополиномиальное время.
