En la entrada anterior hablamos sobre qué es la programación dinámica, cuándo usarla y qué tipos de enfoques existen: top-down (memoización) y bottom-up (tabulación). Ahora vamos a centrarnos en cómo aplicar este conocimiento Resolviendo fibonacci en C, y por qué elegimos el enfoque de tabulación iterativa en el lenguaje C.
En C, es común usar el enfoque iterativo para evitar la sobrecarga de la recursión. Vamos a construir un array donde cada posición fib[i] almacenará el resultado de F(i). Comenzamos llenando los casos base fib[0] y fib[1], luego iteramos calculando cada fib[i] como la suma de los dos anteriores. Finalmente devolvemos fib[n] como resultado.
Resolviendo fibonacci en C
La sucesión de Fibonacci se define así:
- F(0) = 0
- F(1) = 1
- F(n) = F(n-1) + F(n-2), para n ≥ 2
Queremos calcular el término F(n) de forma eficiente. La versión recursiva directa es muy simple de implementar, pero ineficiente: recalcula muchos valores una y otra vez, lo que hace que el tiempo de ejecución crezca exponencialmente. En C, además, la recursión profunda puede generar problemas de desbordamiento de pila.
Por eso, usamos programación dinámica para optimizar el cálculo.
¿Qué enfoque usamos en C?
Elegimos el enfoque bottom-up (tabulación), por varias razones:
1. Evita recursión: En C, la recursión profunda puede ser peligrosa (desbordamientos de pila). La versión iterativa es más segura.
2. Control total sobre la memoria: En C, gestionamos la memoria directamente. La tabulación nos permite crear un array que almacene los resultados de los subproblemas.
3. Eficiencia clara: Calculamos cada número una sola vez, en orden creciente, y siempre tenemos disponibles los resultados anteriores cuando los necesitamos.
Implementación en C (tabulación bottom-up)
En C, es común usar el enfoque iterativo para evitar la sobrecarga de la recursión. Vamos a construir un array donde cada posición fib[i] almacenará el resultado de F(i). Comenzamos llenando los casos base fib[0] y fib[1], luego iteramos calculando cada fib[i] como la suma de los dos anteriores. Finalmente devolvemos fib[n] como resultado.
#include <stdio.h>
long fibonacci(int n) {
// Manejar directamente los casos base
if (n < 2) {
return n;
}
// Array para almacenar resultados de Fibonacci desde 0 hasta n
long fib[n + 1];
fib[0] = 0;
fib[1] = 1;
// Calcular iterativamente desde 2 hasta n
for (int i = 2; i <= n; ++i) {
fib[i] = fib[i-1] + fib[i-2];
}
// El resultado deseado es fib[n]
return fib[n];
}
int main() {
int n = 10;
long resultado = fibonacci(n);
printf("Fib(%d) = %ld\n", n, resultado);
return 0;
}Si ejecutamos este programa, mostrará por ejemplo Fib(10) = 55. La función fibonacci utiliza programación dinámica: cada valor se calcula una vez y se guarda en el array fib. El algoritmo itera n-1 veces, por lo que su complejidad es O(n), mucho más eficiente que la solución recursiva exponencial. Además, el código es sencillo: seguimos directamente la definición de Fibonacci llenando la tabla de abajo arriba.
Nota: En C, hemos creado un array automático de tamaño n+1. Esto funciona correctamente siempre que n no sea demasiado grande. En problemas reales, podríamos usar memoria dinámica (malloc) o arreglos estáticos de tamaño fijo máximo para manejar valores mayores, pero el concepto de tabulación permanece igual.