Fibonacci por Fórmula

Problema: Dada la serie de Fibonacci, se desea averiguar que numero ocupa la n-esima posición.

Ejemplos:

1. Si n = 0. Salida = El termino 10 de la sucesión es: 0.

2. Si n = 10. Salida = El termino 10 de la sucesión es: 55.

3. Si n = 16. Salida = El termino 16 de la sucesión es: 987.

4. Si n = 45. Salida = El termino 16 de la sucesión es: 1134903170.

Idea del algoritmo:

La sucesión de Fibonacci es una sucesión infinita de números naturales que tiene la particularidad de aparecer frecuentemente en la naturaleza. Para obtener un determinado termino de la sucesión se deben sumar los 2 términos inmediatamente anteriores a este. Dado un n que indicara la posición que queremos averiguar, calcularemos el n-esimo termino utilizando la formula:

T(n) = ƒ(n) = ( ((1+√5)/2)^n - ((1-√5)/2)^n ) / √5

siendo T(n) el termino en la posición n.

Código

Disponible en Enciclopedia Algoritmos C++, Fibonacci con Formula.

Ejemplo de uso

Disponible en Fibonacci con formula

Complejidad: -

En Ideone

Problemas en sitios jueces que se pueden resolver con búsqueda lineal de un elemento en un vector.

Colaborador autor del artículo:

• https://es.wikipedia.org/wiki/Sucesi%C3%B3n_de_Fibonacci
• https://quantdare.com/numeros-de-fibonacci/