SICP hacer cambios

Question

Por lo tanto; Soy un aficionado que está tratando de trabajar a través de SICP ( es gratis! ) y hay un procedimiento de ejemplo en el primer capítulo que está destinado a contar las posibles maneras de hacer el cambio con las monedas de américa; (Cambio de decisiones 100) => 292. Se implementó algo como:

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

De todos modos; este es un procedimiento recursivo-árbol, y el autor "deja como un desafío" encontrar un procedimiento iterativo para resolver el mismo problema (es decir, el espacio fijo). No he tenido suerte calcular esto o la búsqueda de una respuesta después de frustrarse. Me pregunto si es un pedo cerebral de mi parte, o si el autor de atornillado conmigo.

Answer 1

La forma más sencilla / más general para eliminar la recursividad, en general, es el uso de una pila auxiliar - en lugar de hacer las llamadas recursivas, se presiona sus argumentos en la pila, y repetir. Cuando se necesita el resultado de la llamada recursiva a fin de proceder, de nuevo en el caso general, eso es un poco más complicado porque usted también va a tener que ser capaz de empujar una "solicitud de continuación" (que se desprenderá del auxiliar pila cuando se conocen los resultados); Sin embargo, en este caso, ya que todo lo que estamos haciendo con todos los resultados de llamada recursiva es una suma, que es suficiente para mantener un acumulador y, cada vez que se obtiene como resultado un número en lugar de una necesidad de hacer más llamadas, añadirlo a la acumulador.

Sin embargo, esto, de por sí, es no espacio fijo, ya que la pila crecerá. Así que otra idea útil es: ya que esta es una función pura (sin efectos secundarios), cada vez que se encuentra el tener calcula el valor de la función de un determinado conjunto de argumentos, puede memoize la correspondencia argumentos en los resultados. Esto limitará el número de llamadas. Otro enfoque conceptual que lleva a muchos de los mismos cálculos es [[también conocido como DP]], aunque con DP suele trabajar de abajo hacia arriba "preparación de los resultados que se memoized", por así decirlo, en lugar de comenzar con una recursividad y trabajando para eliminarla.

Tome abajo hacia arriba DP sobre esta función, por ejemplo. Usted sabe que va a terminar en repetidas ocasiones con "cuántas maneras de hacer el cambio de una cantidad X con sólo la moneda más pequeña" (como usted cosas cortar abajo a X con diferentes combinaciones de monedas de la amount el original), por lo que se inicia el cálculo de los valores amount con un simple iteración (f (X) = X / value si X es exactamente divisible por el valor más pequeño value-moneda, más 0; aquí, value es 1, por lo que f (x) = x para todo x> 0). Ahora continúa calculando una nueva función g (x), maneras de hacer el cambio de X con los dos monedas más pequeñas: una vez más una iteración simple para aumentar X, con g (x) = f (x) + g (X - value) para la value de la segunda moneda más pequeña (que será una iteración simple, porque en el momento en que estás calculando g (X) que ya ha calculan y f (x almacenado) y all g (Y) para Y tres monedas más pequeñas - h (x) = g (x) + g (X-value) que el anterior - y de de ahora no será necesario f (X) más, por lo que puede volver a utilizar que espacio. En total, esto tendría que 2 * amount espacio - no "espacio fijo" todavía, pero, cada vez más cerca ...

Para dar el salto final al "espacio fijo", pregúntese: ¿necesita para mantener alrededor de todos valores de dos matrices en cada paso (el que computarizada última y la que está Actualmente la informática), o bien, solamente algunos de esos valores, reordenando su bucle un poco ...?

Answer 2

La solución que se me ocurrió es llevar la cuenta de cada tipo de moneda que está utilizando en un 'monedero'

El bucle principal funciona así; 'Denom es la denominación actual,' cambiado es el valor total de las monedas en el monedero, 'dada es la cantidad de cambio que necesito hacer y' clara hasta a la toma todas las monedas más pequeñas que una denominación dada a cabo de la bolsa .

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

Después de leer la respuesta de Alex Martelli se me ocurrió la idea monedero pero sólo llegué a hacer que funcione

Answer 3

Aquí es mi versión de la función, utilizando programación dinámica . Un vector de tamaño n + 1 se inicializa a 0, a excepción de que el elemento de orden 0 es inicialmente 1. Entonces para cada posible moneda (el exterior hacer circular), cada elemento de vector (hacer el interior circular) a partir de la k-ésima , donde k es el valor de la moneda, se incrementa en el valor en el actual índice menos 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

Puede ejecutar este programa en http://ideone.com/EiOVY .

Answer 4

Por lo tanto, en este hilo , el autor de la pregunta original de la pregunta se le ocurre una respuesta de sonido a través de la modularización. Yo sugeriría, sin embargo, que su código fácilmente puede optimizarse si se observa que cc-pennies es totalmente superflua (y, por extensión, también lo es cc-nothing)

Ver, el problema con la forma en que está escrito cc-pennies es que, porque no hay menor denominación ir, todo lo que hará mediante la imitación de la estructura de los procedimientos de alta denominación se iterar desde (- amount 1) a 0, y lo hará este cada vez que se le pasa una cantidad del procedimiento cc-nickels. Así, en el primer paso, si se intenta 1 dólar, obtendrá una amount de 100, por lo que se evalúa como (- amount 1) 99, lo que significa que va a someterse a 99 ciclos superfluos del ciclo cc-pennies y cc-nothing. Entonces, monedas de cinco centavos que pasarán 95 como la cantidad, por lo que obtener 94 ciclos más desperdiciados, así sucesivamente y así sucesivamente. Y eso es todo, incluso antes de mover el árbol de monedas de diez centavos, o cuartos o medias de dólares.

En el momento en que llegue a cc-pennies, que ya sabe lo que desea es hasta el acumulador por uno, así que te sugiero esta mejora:

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

Esperamos que haya encontrado esto útil.

Answer 5

Puede resolverlo de forma iterativa con la programación dinámica en tiempo pseudo-polinomial.