La Serie de Fibonacci

EL HIJO DE BONACCI:

Leonardo Fibonacci

El matemático italiano Leonardo de Pisa (1170(?)-1250) ha pasado a la historia con el apodo de Fibonacci, contracción de filius Bonacci o hijo de Bonacci. Bonacci era el sobrenombre de su padre, Guglielmo. Debido a que Guglielmo era un agente diplomático, su hijo Leonardo pudo viajar por el cercano oriente, tomando contacto con la matemática árabe. Probablemente la mayor contribución de Fibonacci, sea la introducción del sistema de numeración árabe a Europa. El sistema posicional de los árabes, con 10 símbolos, incluyendo un 0, es muy superior a el sistema romano. Si alguien ha intentado alguna vez realizar operaciones simples de aritmética con números romanos, se habrá dado cuenta de esta importancia. Un sistema posicional simplificado (de hecho el más simple) que incluye al 0, ha permitido el diseño de las computadoras electrónicas en el siglo XX. No fue difícil que los comerciantes de la época se dieran cuenta de la importancia del sistema árabe y lo adoptaran.
EL PROBLEMA DE LOS CONEJOS:
Sin embargo, Fibonacci es más conocido por la llamada serie o sucesión de Fibonacci. La serie surge en diversas fenómenos de la naturaleza. Uno de esos problemas es el estudio de poblaciones de conejos. Es bien sabida la gran fertilidad de estos animales. La formulación del problema de la población es el siguiente:

Una pareja madura de conejos procrea una nueva pareja cada mes, en tanto que una pareja de conejos recién nacidos tarda dos meses en procrear a su vez otra pareja. Si se tiene una pareja de conejos tiernos en un sistema aislado. ¿Cuántas parejas de conejos habrá al cabo de un año?

Al inicio, la población es de 1 pareja.
Al primer mes la pareja tierna habrá madurado, pero no tendrá hijos todavía, por lo tanto de nuevo habrá 1 pareja.
Al segundo mes, tendremos la pareja original madura y una pareja tierna, por lo tanto habrá 2 parejas.
Al tercer mes, la pareja madura habrá procreado nuevamente, en tanto que la otra pareja está alcanzando la madurez. Se tienen 3 parejas.
Para el cuarto mes, se tiene la pareja original, la cual ha tenido de nuevo hijos, sus primeros hijos, ya maduros, que también acaban de tener hijos, y los segundos hijos de los primeros conejos que acaban de alcanzar la madurez. Por lo tanto hay 5 parejas.

Ésto empieza a ser más o menos un lío. Para dejarlo más claro es útil consultar la siguiente figura, que muestra el número de conejos por mes:

El número de parejas de conejos por mes.

¿Cómo podemos saber cuántas parejas habrá en el mes siguiente? Eso depende de cuántas hay en el presente mes y de cuántas hubo en el pasado. Para empezar, el próximo mes van a estar todas las que están ahora, pero también habrá nuevas parejas. ¿Cuántas nuevas parejas habrá? No todas las parejas del presente mes van a procrear para el siguiente, algunas sí, pero las que acaban de nacer necesitan dos meses. ¿Cuáles sí van a procrear? todas las que estaban el mes pasado. Esas ya tienen un mes como mínimo y para el próximo darán origen a una nueva pareja. Es decir, para saber el número del siguiente mes, hay que sumar el número actual más el número del mes pasado. Fíjese que esto se cumple en los primeros meses:

Penúltimo Mes         Último Mes        Mes Actual
      0                   0                  1
      0                   1                  1
      1         +         1        =         2
      1         +         2        =         3
      2         +         3        =         5

De hecho una forma de definir la serie es la siguiente:
LA DEFINICIÓN RECURSIVA
Los números de Fibonacci están definidos como:

, ,

para

Ésta definición es recursiva: para conocer el número de fibonacci actual necesitamos conocer los dos números de fibonacci anteriores. Con ésta fórmula es posible encontrar los primeros 20 números de la sucesión

Fibonacci de: 0 es 0
Fibonacci de: 1 es 1
Fibonacci de 2 es 1
Fibonacci de 3 es 2
Fibonacci de 4 es 3
Fibonacci de 5 es 5
Fibonacci de 6 es 8
Fibonacci de 7 es 13
Fibonacci de 8 es 21
Fibonacci de 9 es 34
Fibonacci de 10 es 55
Fibonacci de 11 es 89
Fibonacci de 12 es 144
Fibonacci de 13 es 233
Fibonacci de 14 es 377
Fibonacci de 15 es 610
Fibonacci de 16 es 987
Fibonacci de 17 es 1597
Fibonacci de 18 es 2584
Fibonacci de 19 es 4181
Fibonacci de 20 es 6765

Observe que este número está creciendo muy rápidamente. Al cabo de un año, hay 144 parejas, a los 20 meses tenemos 6765 parejas de conejos, y en el mes 30 esa cifra llega hasta 832040. Es prácticamente imposible que alguien pueda realmente tener esa cantidad de parejas de conejo. Como modelo poblacional, la sucesión de Fibonacci es mala porque no toma en cuenta varios factores adversos. Por ejemplo, no consideramos el hecho de que la muerte de conejos debe producirse en algún momento. Tampoco se toma en cuenta la limitación de recursos (espacio, agua, alimento) que desde luego limitan el tamaño de la población.
LA SERIE DE FIBONACCI EN LA COMPUTACIÓN
La sucesión de Fibonacci es un problema clásico para estudiantes de computación. En particular es un ejemplo de problema recursivo. En oposición a la iteración (un método directo para solucionar un problema), la recursión es una manera simple de resolver problemas computacionales. Solucionar un problema de forma recursiva es reducir ese problema a casos más simples de sí mismo. Por ejemplo, ¿cuál es el número de Fibonacci 5? La respuesta recursiva es que es el número de Fibonacci 4 + el número de Fibonacci 3, pero ¿cuáles son los números de Fibonacci 4 y 3? respectivamente son número de Fibonacci 3 + número de Fibonacci2 y número de Fibonacci2 + número de Fibonacci1, etc. hasta llegar a los casos bases Fibonacci 0 y Fibonacci 1. Teóricamente, cualquier problema recursivo puede resolverse de manera iterativa, aunque nadie nos dice de qué manera. Ya que en computación, como en la vida misma, hay una gran distancia entre la teoría y la práctica, muchas veces, la recursión es la única forma que tenemos para resolver un problema, si bien se necesitan más recursos (memoria, procesador).
El problema de la serie de Fibonacci también es un ejemplo típico de cómo el tamaño de los tipos de datos es superado muy pronto. Muchos lenguajes de programación clasifican las variables en tipos distintos: enteros, flotantes, etc. Cada uno de éstos tipos tiene asignado un tamaño específico en bits que determinan la cifra máxima que se puede almacenar en dicho espacio de memoria. En el lenguaje Java, por ejemplo, los tipos int tienen un tamaño de 32 bits, (4 bytes) en los cuales se puede almacenar números enteros desde -2147483648 hasta 2147483647 (el bit 32 se reserva para el signo). Como hemos visto, los números en la serie de Fibonacci crecen muy rápidamente con cada ciclo, ésto hace que pronto los tipos de datos sean superados pronto.
El siguiente programa en C++ calcula los números de Fibonacci:

//Calcula la serie de Fibonacci

#include 
using namespace std;
   
/*Prototipo de la funcion fibonacci*/
int fibonacci (int);
   
///////////////////////////////////////////////////////////////////
// MAIN
///////////////////////////////////////////////////////////////////
   
int main()
{
int number, respuesta;
cout <<endl<<endl<< "Este programa calcula el numero de Fibonacci."<<endl;
cout <<"Introduzca un numero: " <> number;

if (0 == number || 1 == number )
cout <<"Fibonacci de: " << number<<" es " << number << endl;
else
{
respuesta = fibonacci (number);
cout<<"Fibonacci de " << number << " es " << respuesta << endl;

}
return 0;

}

/////////////////////////////////////////////////////////////////////
// FUNCION FIBONACCI
/////////////////////////////////////////////////////////////////////
  
int fibonacci (int number)
{
int fib1 = 0, fib2 = 1, fibn = 0, temp;

for ( int n = 2; n <= number; ++n )
   {
   fibn = fib2 + fib1;
   temp = fib2;
   fib2 = temp + fib1;
   fib1 = temp;
   }

return fibn;
}