SICP rendere possibile il cambiamento
-
18-09-2019 - |
Domanda
; Sono un hobbista che sta cercando di lavorare attraverso SICP ( è gratis! ) e non v'è una procedura di esempio, nel primo capitolo, che ha lo scopo di contare i possibili modi per rendere il cambiamento con le monete americane; (Cambio-maker 100) => 292. E 'implementato qualcosa di simile a:
(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))
In ogni caso; questa è una procedura albero ricorsiva, e l'autore "lascia come una sfida" trovare una procedura iterativa per risolvere lo stesso problema (cioè lo spazio fisso). Non ho avuto fortuna capire questo fuori o trovare una risposta dopo sempre frustrati. Mi chiedo se è una scoreggia cervello da parte mia, o se l'autore del avvitamento con me.
Soluzione
Il / modo più semplice più generale di eliminare la ricorsione, in generale, è quello di utilizzare uno stack ausiliario - invece di fare le chiamate ricorsive, si spinge i loro argomenti nello stack, e iterare. Quando è necessario il risultato della chiamata ricorsiva al fine di procedere, di nuovo nel caso generale, questo è un po 'più complicato, perché si sta anche andando ad avere per essere in grado di spingere un "richiesta di continuazione" (che prende il suo ausiliario pila quando i risultati sono noti); tuttavia, in questo caso, dal momento che tutto si sta facendo con tutti i risultati di chiamata ricorsiva è un riepilogo, è sufficiente a mantenere un accumulatore e, ogni volta che si ottiene come risultato un numero invece di una necessità di fare di più chiamata, aggiungerlo alla accumulatore.
Tuttavia, questo, di per sé, è non spazio fisso, dal momento che la pila crescerà. Così un'altra idea utile è: dal momento che si tratta di una funzione di puro (senza effetti collaterali), ogni volta che vi trovate a dover calcolato il valore della funzione per un certo insieme di argomenti, puoi Memoize la corrispondenza argomenti-risultato. Ciò limiterà il numero di chiamate. Un altro approccio concettuale che porta a molto gli stessi calcoli è programmazione dinamica [[aka DP]], anche se con DP si lavora spesso bottom-up "preparando risultati da memoized", per così dire, piuttosto che partire con una ricorsione e lavorando per eliminarlo.
Prendere bottom-up DP su questa funzione, per esempio. Sai che dovrai più volte finisce con "quanti modi per fare il cambiamento per la quantità X con appena la moneta più piccolo" (come le cose cercare di ridurre al X con varie combinazioni di monete dalla amount
originale), in modo da iniziare il calcolo quei valori amount
con una semplice iterazione (f (X) = X
/ value
se X
è esattamente divisibile per il valore più piccolo value
-moneta, altrimenti 0
; qui, value
è 1, quindi f (X) = X per ogni X> 0). Ora si prosegue calcolando una nuova funzione g (X), modi per rendere il cambiamento per X con due più piccole monete: ancora una volta un semplice iterazione per aumentare X, con g (x) = f (x) + g (X - value
) per la value
del secondo più piccolo moneta (si tratterà di un semplice iterazione perché per il momento si sta calcolando g (X) che hai già calcolate e memorizzate f (X) e tutti g (Y) per Y value
) come sopra - e da ora in poi non avrà bisogno di f (X) più, in modo da poter riutilizzare che spazio. Tutto sommato, questo avrebbe bisogno di spazio 2 * amount
- non "spazio fisso" ancora, ma, avvicinandosi ...
Per fare il salto finale per "spazio fisso", chiedetevi: avete bisogno di mantenere intorno tutti valori di due array ad ogni passo (quello che lo scorso computerizzata e quello che sei al momento di calcolo), o, solo alcuni di quei valori, riordinando il vostro loop un po '...?
Altri suggerimenti
La soluzione mi è venuta è quella di tenere il conto di ogni tipo di moneta che si sta utilizzando in un 'borsa'
Il ciclo principale funziona come questo; 'Denom è la denominazione corrente,' cambiato è il valore totale delle monete nella borsa, 'data è la quantità di cambiamento che ho bisogno di fare e' clear-up-to prende tutte le monete più piccole di un dato denominazione fuori dalla borsa .
#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))
Dopo aver letto la risposta di Alex Martelli mi è venuta l'idea di borsa, ma appena ricevuto intorno per farlo funzionare
Qui è la mia versione della funzione, utilizzando la programmazione dinamica . Un vettore di dimensione n + 1 è inizializzato a 0, tranne che l'elemento di indice 0 è inizialmente 1. Allora per ogni possibile moneta (l'esterno do loop), ciascun elemento del vettore (l'interno fanno loop) partendo dal k'th , dove k è il valore della moneta, viene incrementato dal valore di corrente dell'indice k meno.
(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
È possibile eseguire questo programma a http://ideone.com/EiOVY .
Quindi, in questa discussione , il richiedente originale della questione esce con una risposta sonora via modularizzazione. Vorrei suggerire, tuttavia, che il suo codice può essere facilmente ottimizzata se si nota che cc-pennies
è del tutto superfluo (e, per estensione, così è cc-nothing
)
Vedere, il problema con il modo in cui cc-pennies
è scritto è che, perché non c'è nessuna denominazione più bassa per andare, tutto quello che farà imitando la struttura delle procedure di taglio più elevate è un'iterazione giù da (- amount 1)
a 0
, e lo farà ogni volta che si passa una quantità dalla procedura cc-nickels
. Così, al primo passaggio, se si tenta 1 dollaro, si otterrà un amount
di 100, in modo (- amount 1)
restituisce 99
, che significa che potrete subire 99 cicli superflui del ciclo cc-pennies
e cc-nothing
. Poi, monetine passeranno si 95
come quantità, in modo da ottenere 94 cicli più sprecati, così via e così via. E questo è tutto prima ancora di spostare l'albero a monetine, o quarti, o mezze dollari.
Con il tempo si arriva a cc-pennies
, si conosce già si vuole solo l'accumulatore per uno, in modo da suggerirei questo miglioramento:
(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))
Spero che hai trovato questo utile.
È possibile risolverlo in modo iterativo con la programmazione dinamica nel tempo pseudo-polinomiale.