Sucesión de Fibonacci con Python - Algoritmos implementados en Python

Introducción:

Hola amigos de Internet. Les doy la bienvenida a Mi Diario Python, el mejor lugar para Aprender a programar en Python. En este articulo nos dedicaremos a conocer la Sucesión de Fibonacci y realizaremos algunas implementaciones de los algoritmos utilizados para generar esta sucesión.

Sucesión de Fibonacci:

La sucesión de Fibonacci es la siguiente sucesión infinita de números naturales:

 ...

La sucesión comienza con los números 0 y 1, y a partir de estos cada termino es la suma de los dos anteriores.

En la siguiente imagen, podemos observar un poco del proceso de la secuencia:

A los elementos de esta sucesión se les llama números de Fibonacci. Esta fue descrito en Europa por Leonardo de Pisa, también conocido como Fibonacci.

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

Partiendo de dos valores:

Se obtienen:

Para

Algoritmos:

función {displaystyle {rm {fib}}(n),}

si {displaystyle n<2,} entonces

devuelve {displaystyle n,}

en otro caso

devuelve {displaystyle {rm {fib}}(n-1)+{rm {fib}}(n-2),}

Como podemos observar, aquí hay una propiedad muy interesante. La cual es la recursión, la cual se produce cuando una función se llama así misma en su cuerpo.

Creo que ahora podemos empezar a escribir el código:

def fib(n):
    if n < 2:
        return n
    else:
        # fn = fn-1 + fn-2
        return fib(n-1) + fib(n-2)
    
fib(8)

Y el resultado cuando n = 8, es 21. Si lo calculamos, veremos que es correcto.

Si quieres la sucesión con una longitud determinado, podemos utilizar un bucle:

for x in range(10):
    print(fib(x))

0
1
1
2
3
5
8
13
21
34

Increíble ¿No lo crees?

Pero por que llegar hasta aquí. Veamos otras maneras de implementar este algoritmo:

Podemos encontrar otra formula que nos permite generar esta sucesión.

Sí, lo se, da miedo ¿Verdad? No te preocupes. Esta muy fácil.

Lo único que debemos tener en cuenta es que: 

También tenemos el pesudocódigo:

función {displaystyle {rm {fib}}(n),}

si {displaystyle n<2,} entonces

devuelve {displaystyle n,}

en otro caso

{displaystyle varphi gets {rm {(({1+{sqrt {5}}})div {2})}}}

{displaystyle jgets {rm {((varphi ^{n}-left(1-varphi right)^{n}}})div ({sqrt {5}}))}

devuelve {displaystyle j,}

En Python, nos quedaría algo así:

# sqrt para calcular raices cuadradas
from math import sqrt 

def fib(n):
    if n < 2:
        return n
    else:
        u = ((1+sqrt(5))/2)
        j = ((u**n-(1-u)**n)/sqrt(5))
        # round nos permite redondear numeros flotantes
        return round(j)

fib(9)

34

Y el resultado es satisfactorio. Como pueden observar, en este ejemplo hago uso del método round, el cual nos permite redondear números flotantes. De no utilizar round el resultado seria algo así:

34.00000000000001

Podemos realizar un algoritmo más sencillo, para aquellos que recién empiezan en el ámbito de la programación:

El pseudocódigo es el sigueinte:

función {displaystyle {rm {fib}}(n),}

{displaystyle agets 0}

{displaystyle bgets 1}

{displaystyle c}

para {displaystyle k,} desde

{displaystyle 0,} hasta

{displaystyle n,}hacer

{displaystyle cgets b+a}

{displaystyle agets b}

{displaystyle bgets c}

devuelve {displaystyle a,}

En Python, nos quedaría algo así:

def fib(n):
    a = 0
    b = 1
    
    for k in range(n):
        c = b+a
        a = b
        b = c
        
    return a

fib(9)

Puedes escoger la opción que prefieras. Espero que te sea de mucha ayuda.

¿Alguna duda? No dudes en dejar tu comentario.

Mi nombre es Luis, y fue un placer compartir mis conocimientos con todos ustedes :D.