- Llenándose
- Leída
- Respuesta
Fibonacci con programación dinámica
Los números de Fibonacci son el primer ejemplo clásico de programación dinámica. La recursión simple pide los mismos términos una y otra vez, pero con una tabla que recuerda cada término el trabajo solo crece con n. Elige un término, elige el método ascendente o descendente y avanza paso a paso para ver cómo cada celda se llena una sola vez. Pulsa Reproducir para ver cómo se llena la tabla, o Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto. Elige n, el término que se va a calcular, y el método: Ascendente llena la tabla desde la izquierda, Descendente mantiene la recursión pero mira primero en la tabla, y la fila bajo la tabla pasa a ser la pila de llamadas abiertas. Nuevo ejemplo elige otro n. Con el tablero seleccionado, las flechas avanzan o retroceden un paso, la barra espaciadora reproduce y pausa, e Inicio y Fin saltan al principio y al final.
Cómo funciona
- Escribe n, el término que se va a calcular, y elige Ascendente o Descendente.
- Pulsa Reproducir, o usa Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto.
- Observa cómo cada celda lee las dos celdas anteriores. Con Descendente, la fila bajo la tabla es la pila de llamadas abiertas.
Ascendente y descendente
El método ascendente (bottom-up), también llamado tabulación, empieza con F(0) = 0 y F(1) = 1 y llena la tabla de izquierda a derecha: cada celda nueva es la suma de las dos celdas anteriores. El método descendente (top-down), también llamado memoización, mantiene la definición recursiva: para hallar F(n), pide F(n − 1) y F(n − 2). La diferencia con la recursión simple es que cada llamada mira primero en la tabla y solo calcula un término si su celda sigue vacía. Ambos llenan cada celda una vez y usan n − 1 sumas.
Por qué la recursión simple es tan lenta
Sin tabla, F(n) llama a F(n − 1) y a F(n − 2), ambas llaman a F(n − 3), y así sucesivamente: las llamadas forman un árbol en el que los mismos términos aparecen una y otra vez. El número de llamadas es 2·F(n + 1) − 1, que crece tan rápido como los propios números de Fibonacci: 177 llamadas para F(10), 21.891 para F(20) y más de 331 millones para F(40). Para subproblemas superpuestos como estos existe precisamente la programación dinámica.
Preguntas frecuentes
¿Qué es la programación dinámica?
Una forma de resolver un problema dividiéndolo en problemas más pequeños que se superponen, resolviendo cada uno una sola vez y guardando su respuesta en una tabla. Los números de Fibonacci son el ejemplo más sencillo: cada término se construye a partir de los dos anteriores.
¿Qué diferencia hay entre memoización y tabulación?
La memoización mantiene el código recursivo y guarda cada respuesta la primera vez que se calcula, así que las llamadas posteriores solo la leen. La tabulación llena la tabla en un orden que garantiza que cada respuesta que necesita una celda ya está ahí. Ambas hacen las mismas sumas; la tabulación evita la pila de llamadas, y la memoización solo calcula las celdas que de verdad se necesitan.
¿Cuántas sumas necesita F(n)?
n − 1 con una tabla: una por cada término de F(2) a F(n). Solo se leen los dos últimos términos, así que un programa también puede guardar solo dos números en lugar de toda la tabla.
¿Por qué la aplicación se detiene en n = 40?
F(40) = 102.334.155 todavía cabe bien en la pantalla, y la recursión simple ya necesitaría 331.160.281 llamadas para calcularlo. Los términos mayores crecen rápido: F(78) es el mayor que un número de JavaScript guarda con exactitud.
¿Se envía algo a alguna parte?
No. Todo se calcula en tu navegador, y tus últimos ajustes se quedan en el almacenamiento local de este navegador.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Ir al editor