algorithm - Ejemplo de SICP: Contando el cambio, no puede entender

recursion scheme

Question

Soy un principiante siguiendo el curso de SICP en MIT OpenCourseWare utilizando tanto las videoconferencias como el libro disponible en línea. Ayer me encontré con un ejemplo, que pregunta si podemos escribir un procedimiento para calcular la cantidad de formas de cambiar una determinada cantidad de dinero.

Este problema tiene una solución simple como un procedimiento recursivo:

(define (count-change amount)
  (cc amount 5))
(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                     (- kinds-of-coins 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

Si quieres ver más, lo tomé desde aquí .

están calculando el número (N) de formas de cambiar una quatity (A) usando K tipos de monedas al agregar:

1. la cantidad de formas (X) de cambiar A sin monedas del primer tipo.

2. El número de formas (Y) de cambio (A - D), donde D es la denominación de la primera moneda, utilizando TODOS los tipos de monedas K.

El problema es que simplemente no entiendo esto. A continuación, intentan explicar diciendo:

"Para ver por qué esto es cierto, observe que las formas de hacer el cambio se pueden dividir en dos grupos: las que no usan el primer tipo de moneda y las que sí lo hacen. Por lo tanto, el número total de formas de realizar cambios para cierta cantidad es igual a la cantidad de formas de hacer cambios por la cantidad sin usar el primer tipo de moneda, más la cantidad de formas de hacer cambios suponiendo que usamos el primer tipo de moneda. (¿Es la última oración? lo mismo que la suma N = X + Y?) Pero el último número es igual a la cantidad de formas de hacer cambios por la cantidad que queda después de usar una moneda del primer tipo. (Después de usar esta moneda, se refieren a formas de hacer cambios con o sin el primer tipo de moneda?) "

Entiendo cómo implementaron el algoritmo recursivo, pero no puedo ver cómo llegaron allí. El inglés no es mi lengua materna, por lo que podría estar perdiendo algo. Si pudiera explicarme, usando otros términos, la lógica detrás de la solución, realmente lo agradecería. Gracias.

Answer 1

Si pensamos demasiado en la recursividad, ya fallamos. Personalmente, utilizo dos metáforas en las recursiones de pensamiento. Una es del pequeño libro "el pequeño intrigante": The Seventh Commandment - Recur on the subparts that are of the same nature . Otro es el paradigma de dividir-conquistar-combinar para diseñar algoritmos. Básicamente, son lo mismo en cuanto a cómo pensar recursivamente.

1. Divide a las subpartes de la misma naturaleza

El problema tiene dos variables: el número (N) de dinero y los tipos (K) de monedas, por lo tanto, cualquier división debe cumplir con lo siguiente: 1. reducing all variables: both N and K, 2. the subparts are the same nature so each subpart can be solved by the recursion process itself or be can solved directly. 3. all subparts together == the original one part, no more and no less. 1. reducing all variables: both N and K, 2. the subparts are the same nature so each subpart can be solved by the recursion process itself or be can solved directly. 3. all subparts together == the original one part, no more and no less.

La división en la solución divide los problemas originales en dos subpartes: la primera subparte es todas las combinaciones que usan la primera moneda (podemos repetir que todas las combinaciones usan al menos una moneda de la primera moneda en el mismo sentido). La subparte restante es que todas las combinaciones no usan ninguna de la primera moneda. N se reduce en la primera subparte, K se reduce en la segunda parte. Ambas son de la misma naturaleza que pueden resolverse recursivamente y juntas son el problema original.

2. conquistar

En este paso, pienso en los casos base. ¿Cuáles son los casos de base cuando el problema se reduce al mínimo que se puede dar respuestas directamente? En esta solución, hay tres casos base. Primero, el N se reduce a 0. Segundo, el N se reduce al negativo. El tercero es que las monedas se reducen a 0, pero N sigue siendo positivo.

3. combinar

Cómo se combinan los resultados cuando se resuelven las subpartes. En esta solución, son simplemente +.

Además, si somos recursivos en una lista, la división suele ser auto de la lista y cdr de la lista. Por lo general, el coche de la lista se puede resolver directamente si no es una lista. La parte de cdr se debe resolver recursivamente. El caso base es el final de la lista si se cumple.

Por cierto, recomendaría encarecidamente the little schemer para aprender la recursión. Es mucho mejor que cualquier otro en este punto en particular por lo que he leído.

Answer 2

El primer cuadro de código en la respuesta anterior de Will Ness me dio suficiente información para comprender el algoritmo. Una vez que lo entendí, me di cuenta de que probablemente habría llegado muy rápido viendo realmente lo que el algoritmo hace paso a paso.

A continuación se muestra el gráfico de cómo procede el algoritmo para un caso simple. La cantidad es de 6 peniques y tenemos dos tipos de monedas: cinco peniques (índice 2) y un penique (índice 1).

Tenga en cuenta que todos los nodos hoja se evalúan a 0 o 1. Esto es obvio cuando observamos la condición en el procedimiento (uno de estos valores es devuelto, o la función se llama de nuevo). Solo dos nodos hoja evalúan a 1, entonces hay 2 formas de hacer 6 peniques con estos dos tipos de monedas, es decir, 6 centavos, o un centavo y cinco peniques.

Ahora entiendo el algoritmo, pero todavía no veo cómo habría resuelto el algoritmo desde el problema inicial. Quizás, a medida que leo más sobre el libro de SICP, este tipo de solución me parezca más obvio.

                             (cc 6 2)
                                |
                 -----------------------------------
                 |                                 |
              (cc 6 1)                          (cc 1 2)
                 |                                 |
   ------------------                         --------------
   |                |                         |            |
(cc 6 0)=0       (cc 5 1)                  (cc 1 1)     (cc -4 2)=0
                    |                         |
             -------------             -------------
             |           |             |           |
          (cc 5 0)=0  (cc 4 1)      (cc 1 0)=0  (cc 0 1)=1
                         |
               --------------
               |            |
            (cc 4 0)=0   (cc 3 1)
                            |
                     --------------
                     |            |
                  (cc 3 0)=0   (cc 2 1)
                                  |
                           --------------
                           |            |
                        (cc 2 0)=0   (cc 1 1)
                                        |
                                 --------------
                                 |            |
                              (cc 1 0)=0   (cc 0 1)=1

Answer 3

"número (N) de formas ... usando N clases" estas dos Ns claramente no son lo mismo. así que digamos K tipos de monedas.

Tenemos muchas monedas, pero cada moneda es 1, 5, 10, 25 o 50 centavos, en total 5 tipos de monedas. Necesitamos comprar algo por un dólar, 100 centavos. Asume un suministro ilimitado de cada tipo de monedas. ¿Cuántas formas tenemos para llegar a la suma total de 100?

O bien usamos algunas monedas (una o más) de 50 centavos, o no. Si no, todavía tenemos que llegar al 100 con solo 4 tipos de monedas. Pero si lo hacemos, luego de usar una moneda de 50 centavos, la suma total es 100 - 50 = 50 centavos, y aún podemos usar los 5 tipos de monedas para alcanzar la nueva suma total más pequeña:

ways{ 100, 5 } = ways{ 100, 5 - 1 }      ;   never use any 50-cent coins
                 +                       ; OR
                 ways{ 100 - 50,  5 }    ;   may use 50-cent coins, so use one

O en general,

ways( sum, k ) = ways( sum, k - 1 )
                 +
                 ways( sum - first_denomination(k),  k )

Eso es todo al respecto. ¿Ver? La generalización viene naturalmente con la abstracción (reemplazando los valores concretos con símbolos y convirtiéndolos en parámetros en una definición de función).

Entonces tenemos que cuidar los casos base. Si sum = 0 , el resultado es 1: hay una forma de llegar a la suma total de 0 (y es: no tomar monedas).

Si k = 0 , esto significa que no tenemos permitido usar ningún tipo de monedas; en otras palabras, no hay manera de que alcancemos una suma, cualquier suma, sin usar al menos algunas monedas (a menos que la suma sea 0, pero ya hemos manejado ese caso anteriormente). Entonces el resultado debe ser 0.

Lo mismo si sum < 0 , por supuesto. Imposible, es decir, 0 formas de resumirlo, usando cualquier moneda con cualquier denominación positiva.

El punto para la recursividad (estructural) es pensar en lo pequeño, no tratar de ver toda la imagen a la vez, sino quedarse quieto e intentar comprender su situación actual . Es una herramienta mental para abordar su problema, se trata de resolverlo de la forma más fácil y natural, dando un paso tan pequeño como sea posible.

Llamar ( una copia de ) usted mismo es un tecnicismo. Lo principal es el salto de la fe, que se le permite llamarse a sí mismo: suponiendo que ya ha escrito su definición, simplemente usarla era apropiado. Y así es como se escribe . Usted simplemente describe lo que tiene, y cómo está hecho de sus partes.