Google+ Seguidores

lunes, 20 de agosto de 2018

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:

Resultado de imagen para fibonacci

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:

Que mejor que los ejemplos. A continuación nos enfocaremos en escribir algunos algoritmos para la implementación de la Sucesión de Fibonacci.

Realicemos el primero. Para ello nos apoyaremos en el siguiente pseudocódigo:

función 
si  entonces
devuelve 
en otro caso
devuelve 

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)

21

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 
si  entonces
devuelve 
en otro caso
devuelve 

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 
para  desde  hasta hacer
devuelve 

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)

34

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.

1 comentario :
Write comentarios
  1. El artículo muy bien explicado, principalmente por mostrar tres algoritmos distintos para obtener la sucesión de Fibonacci, solo creo que faltaría adicionar en cada uno de ellos su complejidad algorítmica y dejar bien claro que aunque la recursividad es muy buena en algunos casos y que puede demostrar un nivel avanzado del programador, en este caso no es buena. La mejor opción es la última, es decir la opción iterativa

    ResponderEliminar

Tu comentario es importante y nos motiva a seguir escribiendo...

Powered by Blogger .