SICP rendere possibile il cambiamento

Question

; 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.

Answer 1

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 tre più piccole monete - h (X) = g (X) + g (X-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 '...?

Answer 2

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

Answer 3

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 .

Answer 4

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.

Answer 5

È possibile risolverlo in modo iterativo con la programmazione dinamica nel tempo pseudo-polinomiale.