5.1. Método general.
Ejemplo. Cálculo de los números de Fibonacci.
Con divide y vencerás.
Fibonacci (n: integer)
Si nɚ Devolver n
Sino Devolver Fibonacci (n-1) + Fibonacci (n-2)
- Problema: Muchos cálculos están repetidos, tiempo de ejec. exponencial.
- Solución: Calcular los valores de menor a mayor empezando por 0, e ir guardando los resultados en una tabla.
Con programación dinámica.
Fibonacci (n: integer)
T[0]:= 0; T[1]:= 1;
for i:= 2 to n do
T[i]:= T[i-1] + T[i-2];
Devolver T[n];
- Se utiliza la misma fórmula que en la versión anterior, pero de forma más inteligente. El tiempo de ejecución es ?(n).