Ni idea de cómo resolver SICP ejercicio 1.11

https://stackoverflow.com/questions/2365993

23-09-2019
|

Pregunta

A f función es definida por la regla de que si f(n) = n n < 3 y f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) si n > 3. Escribir un procedimiento que calcula f por medio de un proceso recursivo. Escribir un procedimiento que calcula f por medio de un proceso iterativo.

La aplicación de forma recursiva es bastante simple. Pero no podía encontrar la manera de hacerlo de forma iterativa. Probé la comparación con el ejemplo de Fibonacci dado, pero que no sabía cómo usarlo como una analogía. Así que me di por vencido (la culpa es mía) y Googled para una explicación , y me encontré con esto:

(define (f n)
   (if (< n 3)
       n
       (f-iter 2 1 0 n)))

(define (f-iter a b c count)
   (if (< count 3)
       a
       (f-iter (+ a (* 2 b) (* 3 c))
               a
               b
               (- count 1))))

Después de leerlo, entiendo el código y cómo funciona. Pero lo que no entiendo es el proceso necesario para obtener de la definición recursiva de la función a esto. No entiendo cómo el código podría haber formado en la cabeza de alguien.

Podría explicar el proceso de pensamiento necesario para llegar a la solución?

Solución

Se necesita para capturar el estado en algunos acumuladores y actualizar el estado en cada iteración.

Si usted tiene experiencia en un lenguaje imperativo, imaginar escribir un bucle while y seguimiento de la información en las variables durante cada iteración del bucle. ¿Qué variables necesitaría? ¿Cómo actualizar que ellos? Eso es exactamente lo que tiene que hacer para que un conjunto iterativo (recursiva de cola) de las llamadas en el esquema.

En otras palabras, podría ayudar a empezar a pensar en esto como un bucle while en lugar de una definición recursiva. Con el tiempo usted será lo suficientemente fluida con recursivas -.> Transformaciones iterativos que no necesitará ayuda adicional para empezar

En este ejemplo en particular, usted tiene que mirar de cerca las tres llamadas a la función, porque no es inmediatamente claro cómo representar ellos. Sin embargo, aquí está el proceso de pensamiento probable: (en Python pseudo-código para enfatizar la imperatividad)

Cada paso recursivo hace un seguimiento de tres cosas:

f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3)

Así que necesito tres piezas de estado para realizar un seguimiento de la corriente, los valores penúltimos de f pasado y. (Es decir, f(n-1), f(n-2) and f(n-3).) Llame a ellos a, b, c. Tengo que actualizar estas piezas dentro de cada bucle:

for _ in 2..n:
    a = NEWVALUE
    b = a
    c = b
return a

¿Cuál es NEWVALUE? Bueno, ahora que tenemos representaciones de f(n-1), f(n-2) and f(n-3), es sólo la ecuación recursiva:

for _ in 2..n:
    a = a + 2 * b + 3 * c
    b = a
    c = b
return a

Ahora todo lo que queda es averiguar los valores iniciales de a, b and c. Pero eso es fácil, ya que sabemos que f(n) = n if n < 3.

if n < 3: return n
a = 2 # f(n-1) where n = 3
b = 1 # f(n-2)
c = 0 # f(n-3)
# now start off counting at 3
for _ in 3..n:
    a = a + 2 * b + 3 * c
    b = a
    c = b
return a

Eso es todavía un poco diferente de la versión iterativa Esquema, pero espero que se puede ver el proceso de pensamiento ahora.

Otros consejos

creo que usted está preguntando cómo se podría descubrir el algoritmo de forma natural, fuera de un 'patrón de diseño'.

Fue muy útil para que mire la expansión de la f (n) en cada valor de n:

f(0) = 0  |
f(1) = 1  | all known values
f(2) = 2  |

f(3) = f(2) + 2f(1) + 3f(0)
f(4) = f(3) + 2f(2) + 3f(1)
f(5) = f(4) + 2f(3) + 3f(2)
f(6) = f(5) + 2f(4) + 3f(3)

Mirando más de cerca a f (3), vemos que podemos calcular inmediatamente a partir de los valores conocidos. ¿Qué necesitamos para calcular f (4)?

Necesitamos al menos calcular f (3) + [el resto]. Pero a medida que calculamos f (3), se calcula f (2) y F (1), así, que nos ha tocado necesidad para el cálculo de [el resto] de f (4).

f(3) = f(2) + 2f(1) + 3f(0)
            ↘       ↘
f(4) = f(3) + 2f(2) + 3f(1)

Por lo tanto, para cualquier número n, que puede comenzar mediante el cálculo de f (3), y la reutilización de los valores que utilizo para calcular f (3) para calcular f (4) ... y el patrón continúa ...

f(3) = f(2) + 2f(1) + 3f(0)
            ↘       ↘
f(4) = f(3) + 2f(2) + 3f(1)
            ↘       ↘
f(5) = f(4) + 2f(3) + 3f(2)

Dado que vamos a volver a utilizarlos, les permite dar un nombre a, b, c. subíndice con el paso estamos en, y paseo a través de un cálculo de f (5):

  Step 1:    f(3) = f(2) + 2f(1) + 3f(0) or f(3) = a₁ + 2b₁ +3c₁

donde

a ₁ = f (2) = 2,

b ₁ = f (1) = 1,

c ₁ = 0

desde f (n) = n para n <3.

Así:

f (3) = a ₁ + 2b ₁ + 3c ₁ = 4

  Step 2:  f(4) = f(3) + 2a₁ + 3b₁

Así que:

a ₂ = f (3) = 4 (calculado anteriormente en la etapa 1),

b ₂ = a ₁ = f (2) = 2,

c ₂ = b ₁ = f (1) = 1

Así:

f (4) = 4 + 2 * 2 + 3 * 1 = 11

  Step 3:  f(5) = f(4) + 2a₂ + 3b₂

Así que:

a ₃ = f (4) = 11 (calculado anteriormente en la etapa 2),

b ₃ = a ₂ = f (3) = 4,

c ₃ = b ₂ = f (2) = 2

Así:

f (5) = 11 + 2 * 4 + 3 * 2 = 25

En todo el estado que captura cálculo anterior en el cálculo anterior y pasar al siguiente paso, particularily:

a _paso = resultado de la etapa - 1

b _paso = a _{paso - 1}

c _paso = b _{paso -1}

Una vez que vi esto, a continuación, dar con la versión iterativa fue sencillo.

Desde la entrada que describe vinculado a mucho de la solución, voy a tratar sólo para dar información complementaria.

Usted está tratando de definir una función recursiva de cola en el esquema aquí, dada una (no-cola) definición recursiva.

El caso base de la recursión (f (n) = n si n <3) es manejado por ambas funciones. No estoy realmente seguro de por qué el autor hace esto; la primera función simplemente podría ser:

(define (f n)
   (f-iter 2 1 0 n))

La forma general sería:

(define (f-iter ... n)
   (if (base-case? n)
       base-result
       (f-iter ...)))

Tenga en cuenta que no siga los pasos de parámetros para f-iter todavía, porque primero tiene que entender cuáles son las necesidades del estado que se transmite de una iteración a otra.

Ahora, vamos a ver las dependencias de la forma recursiva de f (n). Hace referencia f (n - 1), f (n - 2), y f (n - 3), de modo que necesitamos para mantener en torno a estos valores. Y, por supuesto, tenemos que el valor de n en sí, por lo que podemos dejar de iterar sobre ella.

Así que esa es la forma en que ocurrió la llamada recursiva de cola: nos f cómputo (n) a utilizar como f (n - 1), f Girar (n - 1) a f (n - 2) y f (n - 2) a f (n -. 3), y el recuento de decremento

Si esto no ayuda, por favor intente hacer una pregunta más específica -. Que es muy difícil de responder cuando se escribe "No entiendo" dado una explicación relativamente exhaustiva ya

Me voy a entrar en esto en un enfoque ligeramente diferente a las otras respuestas aquí, se centró en cómo el estilo de programación puede hacer que el proceso de pensamiento detrás de un algoritmo como esto más fácil de comprender.

El problema con el enfoque de Bill , citado en su pregunta , es que no está claro de inmediato lo que significa es transportado por las variables de estado, a, b y c. Sus nombres no transmiten información, y después de Bill no describe ningún invariante u otra norma que obedezcan. Me resulta más fácil tanto para formular y entender los algoritmos iterativos si las variables de estado obedecen algunas reglas documentados que describen sus relaciones entre sí.

Con esto en mente, considere esta formulación alternativa de exactamente el mismo algoritmo, que se diferencia de Bill sólo en tener nombres de las variables más significativas para a, b y c y una variable contador incremental en lugar de un decremento uno:

(define (f n)
    (if (< n 3)
        n
        (f-iter n 2 0 1 2)))

(define (f-iter n 
                i 
                f-of-i-minus-2
                f-of-i-minus-1
                f-of-i)
    (if (= i n)
        f-of-i
        (f-iter n
                (+ i 1)
                f-of-i-minus-1
                f-of-i
                (+ f-of-i
                   (* 2 f-of-i-minus-1)
                   (* 3 f-of-i-minus-2)))))

De repente, la corrección del algoritmo - y el proceso de pensamiento detrás de su creación - es fácil de ver y describir. Para calcular f(n):

Tenemos una variable de contador i que se inicia a los 2 y sube a n, incrementando en 1 en cada llamada a f-iter.
En cada paso en el camino, hacemos un seguimiento de f(i), f(i-1) y f(i-2), que es suficiente que nos permita calcular f(i+1).
Una vez i=n, hemos terminado.

A f función es definida por la regla de que f(n) = n, if n<3 y f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3), if n > 3. Escribir un procedimiento que calcula f por medio de un proceso recursivo.

es ya escrito:

f(n) = n,                                  (* if *)  n < 3
     = f(n - 1) + 2f(n - 2) + 3f(n - 3),   (* if *)  n > 3

Lo creas o no, hubo una vez tal idioma. Para escribir esto en otro idioma es sólo una cuestión de sintaxis. Y, por cierto, la definición a medida que los (mal) citar que tiene un error, que ahora es muy evidente y clara.

escribir un procedimiento que calcula f por medio de un proceso iterativo.

ir hacia adelante ( no su explicación) en oposición a la recursividad de ir hacia atrás en un primer momento:

f(n)   =  f(n - 1) + 2f(n - 2) + 3f(n - 3) 
       =  a        + 2b        + 3c
f(n+1) =  f(n    ) + 2f(n - 1) + 3f(n - 2)
       =  a'       + 2b'       + 3c'          a' = a+2b+3c, b' = a, c' = b
......

Esta describe así transiciones de estado del problema como

 (n, a, b, c)  ->  (n+1, a+2*b+3*c, a, b)

podría codificar como

g (n, a, b, c) = g (n+1, a+2*b+3*c, a, b)

pero por supuesto que no parar nunca. Así que hay que tener lugar

f n = g (2, 2, 1, 0)
  where
  g (k, a, b, c) = g (k+1, a+2*b+3*c, a, b),    (* if *) k < n
  g (k, a, b, c) = a,                           otherwise

y esto ya es exactamente igual que el código que le preguntará sobre, hasta sintaxis.

Contar hasta n es más natural aquí, siguiendo nuestro paradigma de "ir hacia adelante", pero la cuenta atrás a 0 como el código usted cita hace es, por supuesto, totalmente equivalente.

Los casos de esquina y los posibles errores off-by-one se quedan fuera tan ~~Ejercicio~~ tecnicismos no interesantes.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow