Para quienes estamos relacionados con la Programación y las Ciencias de la Computación, alguna vez nos hemos que tenido que topar opn la serie de Fibonacci, ya sea para programarla o para estudiar su comportamiento. Cada número de esta famosa serie se obtiene de la suma de los dos anteriores.
La serie de Fibonacci tiene muchas aplicaciones, no solo en la computación sino también en ciencias que en las cuales las matematicas aparentemente no tienen mucho que ver.
Me tomo por sorpresa leer acerca de ésta (y otras cosas mas) en el libro: El código da Vinci de Dan Brown, por que es utilizada para encriptar un mensaje. No solo se trata de la serie de Fibonacci sino también del numero Phi = 1.618 llamado también la divina proporción. Algunas cuestiones matematicas estan muy relacionadas con la naturaleza las cuales se debe tener en cuenta al momento de pintar un cuadro.
Escribiré un post acerca de este interesante libro cuado termine de leerlo. Mientras tanto…
Sabemos que generar estos números es sencillo de programar. Debido a que los valores de la serie se hacen grandes muy grandes, el reto es generar la mayor cantidad de numeros de Fibonacci. Los tipos de datos números en los lenguajes de programación (int, double, float) tienen sus límites y el asunto es romper esos límites.
El siguiente es un programa es la forma recursiva de obtener el numero N de la serie de Fibonacci:
unsigned long Fibonacci(unsigned int n)
{
if ((n == 0) || (n == 1))
{
return 1;
}
else
{
return (Fibonacci(n -1 ) + Fibonacci(n - 2));
}
}
Puede que el programa sea dañino para la salud del Sistema Operativo, por ello también les escribí una versión no recursiva.
unsigned long Fibonacci(unsigned int n)
{
if ((n == 0) || (n == 1))
{
return 1;
}
unsigned long last = 1;
unsigned long curr = 1;
unsigned long tmp = 0;
while(n > 2)
{
tmp = curr;
curr = curr + last;
last = tmp;
n--;
}
return curr;
}
Con la primera función el calculo del numero 30 de Fibonacci demorará a l rededor de 5 segundos, para el numero 40 demorará unos minutos dependiendo del procesador que tengan. Si utilizan una cray esto sucederá un unos cuantos milisegundos. Hay quienes dicen que una cray se sale de un bucle infinito en 6 segundos.
Con el segundo programa logré calcular el numero 47 (2971215073), a partir del numero 48 empieza el desbordamiento. Existen otras formas de obtener el esto de números.
El programa para probar cualquiera de las dos formas es:
int main(int argc, char* argv[])
{
if(argc <= 1)
{
cout<<"Modo de uso :"<<endl;
cout<<"\t"<<argv[0]<<" N "<<endl<<endl;
return 1;
}
cout<<Fibonacci(atoi(argv[1]));
cout<<endl;
return 0;
}
Si tienen problemas para compilar no olviden agregar el parámetro –lstdc++ al gcc (linux)
