No tengo idea de cómo resolver el ejercicio SICP 1.11

Question

No tengo idea de cómo resolver el ejercicio SICP 1.11

Una función f se define por la regla que f(n) = n si n < 3 y f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) si n > 3. Escriba un procedimiento que calcule f por medio de un proceso recursivo. Escriba un procedimiento que calcule f por medio de un proceso iterativo.

Implementarlo recursivamente es bastante simple. Pero no pude averiguar cómo hacerlo iterativamente. Traté de comparar con el ejemplo de Fibonacci dado, pero no sabía cómo usarlo como analogía. Tan Me rendí (la vergüenza es mía) y busqué en Google una explicación , y encontré 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 llegar de la definición recursiva de la función a esto. No entiendo cómo se pudo formar el código en la cabeza de alguien.

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

23

iteration recursion scheme sicp

Author: Will Ness, 2010-03-02

Source

5 answers

Creo que te estás preguntando cómo uno podría descubrir el algoritmo naturalmente, fuera de un 'patrón de diseño'.

Fue útil para mí mirar la expansión de la f (n) en cada valor 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 f(3), vemos que podemos calcularlo 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), calculamos f(2) y f(1) también, que resulta que necesitamos para calculando [el resto] de f(4).

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

Entonces, para cualquier número n, puedo comenzar calculando f(3), y reutilizar los valores que uso 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)

Ya que vamos a reutilizarlos, vamos a darles un nombre a, b, c. subscriptos con el paso en el que estamos, y caminar 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

Ya que f(n) = n para n

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

A lo largo del cálculo anterior capturamos el estado en el cálculo anterior y lo pasamos al siguiente paso, especialmente:

A_paso = resultado del paso-1

B_step = a_{step - 1}

C _step = b_{step -1}

Una vez que vi esto, entonces subir con la versión iterativa fue sencillo.

13

Author: mwolfetech,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-08-16 01:00:03

Dado que la publicación a la que enlazaste describe mucho sobre la solución, intentaré solo dar información complementaria.

Está tratando de definir una función recursiva de cola en Scheme aquí, dada una definición recursiva (no de cola).

El caso base de la recursión (f(n) = n si n

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

Nota que no he rellenado parámetros para f-iter todavía, porque primero necesita entender qué estado debe pasarse de una iteración a otra.

Ahora, veamos las dependencias de la forma recursiva de f(n). Hace referencia a f (n-1), f(n - 2) y f(n - 3), por lo que necesitamos mantener alrededor de estos valores. Y por supuesto necesitamos el valor de n sí mismo, por lo que podemos dejar de iterar sobre él.

Así es como se llega a la llamada recursiva de cola: calculamos f (n) para usar como f (n-1), rotamos f(n - 1) a f (n - 2) y f(n - 2) a f(n - 3), y cuenta de decremento.

Si esto todavía no ayuda, por favor trate de hacer una pregunta más específica - es realmente difícil de responder cuando escribe "No entiendo" dada una explicación relativamente completa ya.

2

Author: Nicholas Riley,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-03-02 19:51:09

Voy a abordar esto en un enfoque ligeramente diferente a las otras respuestas aquí, centrado en cómo el estilo de codificación puede hacer que el proceso de pensamiento detrás de un algoritmo como este sea más fácil de comprender.

El problema con El enfoque de Bill , citado en su pregunta, es que no está inmediatamente claro qué significado es transmitido por las variables de estado, a, b, y c. Sus nombres no transmiten información, y el post de Bill no describe ninguna invariante o otra regla que obedecen. Me resulta más fácil formular y entender algoritmos iterativos si las variables de estado obedecen algunas reglas documentadas que describen sus relaciones entre sí.

Con esto en mente, considere esta formulación alternativa del mismo algoritmo exacto, que difiere del de Bill solo en tener nombres de variables más significativos para a, b y c y una variable de contador incremental en lugar de una decreciente:

(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 el 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 comienza en 2 y sube a n, incrementándose en 1 en cada llamada a f-iter.
En cada paso a lo largo del camino, hacemos un seguimiento de f(i), f(i-1) y f(i-2), que es suficiente para permitirnos calcular f(i+1).
una Vez i=n, hemos terminado.

1

Author: Mark Amery,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-06-08 21:22:07

Una función f se define por la regla que f(n) = n, if n<3 y f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3), if n > 3. Escriba un procedimiento que calcule f por medio de un proceso recursivo.

Ya está 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 lenguaje . Escribir esto en otro idioma es solo una cuestión de sintaxis. Y por cierto, la definición como usted (mal)cita tiene un error, que ahora es muy evidente y claro.

Escriba a procedimiento que calcula f mediante un proceso iterativo.

Iteración significa ir adelante (hay tu explicación!) a diferencia de la recursión va hacia atrás al principio:

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

Esto describe así las transiciones de estado del problema como

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

Podríamos codificarlo como

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

Pero, por supuesto, nunca se detendría. Así que debemos tener

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 como el código por el que preguntaste, hasta sintaxis.

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

Los casos de esquina y posibles errores off-by-one se dejan fuera como ~~ejercicio~~ tecnicismos no interesantes.

0

Author: Will Ness,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-02-15 18:39:50

score 27 · Accepted Answer

Necesita capturar el estado en algunos acumuladores y actualizar el estado en cada iteración.

Si tiene experiencia en un lenguaje imperativo, imagine escribir un bucle while e información de seguimiento en variables durante cada iteración del bucle. ¿Qué variables necesitarías? ¿Cómo los actualizarías? Eso es exactamente lo que tienes que hacer para hacer un conjunto iterativo (cola-recursivo) de llamadas en Scheme.

En otras palabras, podría ayudar a empezar a pensar en esto como un bucle while en lugar de una definición recursiva. Eventualmente, será lo suficientemente fluido con las transformaciones recursivas -> iterativas que no necesitará ayuda adicional para comenzar.

Para este ejemplo en particular, tienes que mirar de cerca las tres llamadas a funciones, porque no está claro de inmediato cómo representarlas. Sin embargo, aquí está el proceso de pensamiento probable: (en el pseudo-código de Python para enfatizar la imperatividad)

Cada paso recursivo mantiene un registro de tres cosas:

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

Así que necesito tres piezas de estado para rastrear los valores actual, último y penúltimo de f. (es decir, f(n-1), f(n-2) and f(n-3).) Llámalos a, b, c. Tengo que actualizar estas piezas dentro de cada bucle:

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

Entonces, ¿qué 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 calcular 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 sigue siendo un un poco diferente de la versión iterativa del Esquema, pero espero que pueda ver el proceso de pensamiento ahora.