Los números de Fibonacci Fk son una sucesión de números naturales definidos de la siguiente manera:
F0 = 0,
F1 = 1,
Fk = Fk−1 + Fk−2, cuando k≥2
En palabras simples, la sucesión de Fibonacci comienza con 0 y 1, y los siguientes términos siempre son la suma de los dos anteriores.
En la siguiente tabla, podemos ver los números de Fibonacci desde el 0-ésimo hasta el duodécimo.
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | ... |
| Fn | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | 144 | ... |
La sucesión puede utilizarse, de forma parecida, para contar el número de distintas rutas que puede seguir una abeja que va recorriendo las celdillas hexagonales de un panal.
Objetivo
Dado un número N obtener el número de Fibonacci n-ésimo.La solución recursiva en Perl
La serie de Fibonacci puede definirse en forma recursiva, y es natural pensar una solución recursiva como eśta:
#!/usr/bin/perl
use strict;
use warnings;
print "Serie Fibonacci\n";
print "Por favor, ingrese n: ";
my $n = <stdin>;
chomp($n);
my $valor= fibonacci($n);
print "El valor F($n) es $valor \n";
sub fibonacci{
my $n= shift;
# F0 = 0,F1 = 1,
if ($n<=1){ return $n; }
return fibonacci($n-1) + fibonacci($n-2);
}
Pero si estudiamos lo que pasa con éstas llamadas recursivas vemos que se llaman múltiples veces con los mismos argumentos. Esto es ineficiente, además las múltiples llamadas son exponenciales, por ejemplo fibonacci(5) llama a fibonacci(4) y fibonacci(3); pero fibonacci(4) también llama a fibonacci(3) y a fibonacci(2); pero cada fibonacci(3) llama a fibonacci(2) y así hasta llegar al caso base.
La solución con memoización en Perl
La solución más obvia es ir guardando los resultados parciales en un array para poder utilizarlos luego. Cada resultado parcial es la respuesta a un subproblema del problema inicial.#!/usr/bin/perl
use strict;
use warnings;
print "Serie Fibonacci\n";
print "Por favor, ingrese n: ";
my $n = <stdin>;
chomp($n);
my @serie;
$serie[0]= 0;
$serie[1]= 1;
my $valor= fibonacci($n);
print "El valor F($n) es $valor \n";
sub fibonacci{
my $n= shift;
if (defined($serie[$n])){ return $serie[$n]; }
$serie[$n]= fibonacci($n-1) + fibonacci($n-2);
return $serie[$n];
}
Uno podría pensar que la memoización es la manera más conveniente de resolver un problema de recursividad múltiple. Sin embargo, una función recursiva gasta un poco de memoria y tiempo en cada llamada recursiva. Por esta razón, la programación dinámica prescinde de la recursividad y resuelve el problema exclusivamente con la iteración.
La solución con programación dinámica en Perl
En general los pasos necesarios para resolver un problema con la programación dinámica son las siguientes:- Encontrar una definición recursiva para el problema (incluyendo los casos base)
- Inicializar la estructura de memoria (normalmente un vector o una matriz)
- Llenar el resultado para los casos base
- Usar bucles para calcular el resultado para otros casos, empleando la definición recursiva (estrategia bottom-up)
La idea es llenar el vector o matriz de resultados de abajo arriba, empezando por los casos base. Al resolver un subproblema se aplica la misma idea recursiva para obtener el resultado. Sin embargo, si los subproblemas recursivos ya han sido resueltos no es necesario hacer ninguna llamada recursiva, sino que el resultado se puede calcular directamente a partir de los resultados guardados en memoria.
#!/usr/bin/perl
use strict;
use warnings;
print "Serie Fibonacci\n";
print "Por favor, ingrese n: ";
my $n = <stdin>;
chomp($n);
my $valor= fibonacci($n);
print "El valor F($n) es $valor \n";
sub fibonacci{
my $n= shift;
my @serie;
$serie[0]= 0;
$serie[1]= 1;
for (my $i= 2; $i <= $n; $i++){
$serie[$i] = $serie[$i-2] + $serie[$i-1];
}
return $serie[$n];
}
