Leonardo de Pisa también conocido como fibonacci fue un matematico italiano famoso por introducir el sistema arabigo decimal a europa y por la succecion de fibonacci motivo de este post.
fibonacci describio en 1202 en su libro «Liber Abaci«,la serie como la solución a un problema sobre cría de conejos:
un hombre tenia una pareja de cononejos juntos en un lugar cerrado y desea saber cuantos nacen apartit de ese par en el periodo de un año cuando su naturaleza es parir a otro en un mes y al segundo mes los paridos también
que quiere decir lo anterior, pues que cada mes, cada pareja de conejos maduros tendrán crías, y las crías tardan un mes en madurar y poder tener sus propias crías, este modelo supone que los conejos nunca mueren y por lo cual es una sucesión infinita de números llamados «de fibonacci» que se ve exactamente como la siguiente:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ...
el algoritmo básico (para quien no lo ha visto aun) es el siguiente:
en el mes 0 no hay conejos, al mes 1 tenemos una pareja de conejos, en el segundo mes la primera pareja tiene crías,al tercer mes la primera pareja tiene crías de nuevo y la segunda pareja(que maduro el mes pasado) tienen crías, es decir la suma de los conejos presentes en el mes anterior y en hace dos meses es el numero de conejos presentes en este mes.
¿si la serie de fibonacci trata sobre conejos de que nos sirve en programación?
pues bien la serie tiene bastas aplicaciones en teoría de números y en ciencias de la computación, y lo mas interesante es que es el algoritmo perfecto para aprender recursion:
primero despejaremos del algoritmo que puse algunas lineas antes a los conejos quedando algo asi:
el numero de fibonacci n es igual a la suma de los dos numeros anteriores (n-1 y n-2)
ya teniendo el algoritmo (sin los conejos) podemos definir el caso base de la recursion, es decir el básico en el cual no podemos ir mas para atrás y del cual sabemos sus valores en este caso son 2, los valores cuando n=0 y n=1, y por que son 2 y no un caso base, pues porque segun el algoritmo ocupamos los valores de n-1 y n-2 y dado que solo calcularemos números positivos no podemos obtener el valor de n-1 si n=0 o -2 si n=0 o n=1.
bien, ahora que ya tenemos el caso base lo único que tenemos que aplicar es el algoritmo, lo escribiré en php pero puede ser escrito en prácticamente cualquier lenguaje
php:
1 2 3 4 5 6 7 8 9 | <? function fibo($x){ if($x==1 || $x == 0) return x; return fibo($x-1) + fibo($x-2); } echo fibo(10);//imprime el décimo numero de la serie ?> |
como se habrán dado cuenta (si no, no importa lo explico), la complejidad de este algoritmo es muy alta o(φ^n), si no sabes lo que representa, φ es el numero áureo el cual se trata de un numero irracional que es una proporción «divina» ya que se encuentra en la naturaleza como en las hojas de algunos arboles o en el caparazón de los caracoles ademas de que fue usada en numerosas contrucciones en la antiguedad
otra propiedad interesante cuando se utiliza la variedad recursiva del algoritmo y se puede apreciar en esta imagen:
tal vez no sea muy fácil apreciarlo a simple vista, asi que que pasa si agrupamos con colores las llamadas (recordar que estamos trabajando con un algoritmo recursivo)
entonces ahora claramente podemos ver claramente que para calcular el número fibonacci de 7 debemos llamar a la función con 7 como parametro 1 vez, con el parámetro 6 1 vez, con el 5 dos, el cuatro tres, el tres cinco y así continua, que es lo que sucede, el número de veces que es necesario calcular el valor fibonacci de un número dentro de la serie es igual al valor fibonacci de n donde n es la cantidad de números que ya procesamos, interesante no?
Si conoces alguna otra propiedad interesante de esta sucesión dejala en los comentarios!
mas informacion: Wikipedia
Debe estar conectado para enviar un comentario.