Sucesión de Fibonacci

En matemáticas, la sucesión de Fibonacci (a veces mal llamada serie de Fibonacci) es la siguiente sucesión infinita de números naturales:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, …

La sucesión comienza con los números 1 y 1, y a partir de estos, «cada término es la suma de los dos anteriores», es la relación de recurrencia que la define.

A los elementos de esta sucesión se les llama números de Fibonacci. Esta sucesión fue descrita en Europa por Leonardo de Pisa, matemático italiano del siglo XIII también conocido como Fibonacci. Tiene numerosas aplicaciones en ciencias de la computación, matemáticas y teoría de juegos.

La sucesión fue descrita por Fibonacci como la solución a un problema de la cría de conejos: «Cierto hombre tenía una pareja de conejos en un lugar cerrado y deseaba saber cuántos se podrían reproducir en un año a partir de la pareja inicial teniendo en cuenta que de forma natural tienen una pareja en un mes, y que a partir del segundo se empiezan a reproducir».

Los números de Fibonacci quedan definidos por la ecuación:

fn = f n-1 + f n-2

partiendo de dos primeros valores predeterminados:

f 0 = 0
f 1 = 1

se obtienen los siguientes números:

f 2= 1
f 3= 2
f 4 = 3
f 5 = 5
f 6 = 8
f 7 = 13
f 8 = 21
para n = 2, 3, 4, 5, …
 
Algoritmos de Cálculo

Para calcular el n-ésimo elemento de la sucesión de Fibonacci existen varios algoritmos (métodos). La definición misma puede emplearse como uno, aquí expresado en pseudocódigo:

Algoritmo 1

Este algoritmo es muy lento. Por ejemplo, para calcular f50 este algoritmo requiere efectuar 20.365.011.073 sumas.

Un método más práctico evitaría calcular las mismas sumas más de una vez. Considerando un par (i, j) de números consecutivos de la sucesión de Fibonacci, el siguiente par de la sucesión es (j, i+j), de esta manera se divisa un algoritmo donde sólo se requiere considerar dos números consecutivos de la sucesión de Fibonacci en cada paso. Este método es el que usaríamos normalmente para hacer el cálculo a lápiz y papel. El algoritmo se expresa en pseudocódigo como:

Algoritmo 2

Esta versión requiere efectuar sólo n sumas para calcular fn, lo cual significa que este método es considerablemente más rápido que el algoritmo 1. Por ejemplo, el algoritmo 2 sólo se requiere efectuar 50 sumas para calcular f50.

Un algoritmo todavía más rápido de tipo Divide y Vencerás, el cual queda como sigue:

Algoritmo 3

A pesar de lo engorroso que parezca, este algoritmo permite reducir enormemente el número de operaciones que se necesitan para calcular números de Fibonacci muy grandes. Por ejemplo, para calcular f100, en vez de hacer las 573.147.844.013.817.084.100 sumas del algoritmo 1 o las 100 sumas con el algoritmo 2, el cálculo se reduce a tan sólo 9 multiplicaciones matriciales.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *