Fibonacci en Python

Más ejercicios resueltos

Si deseas revisar más ejercicios resueltos, haz click en el siguiente botón. 

A continuación presentamos 4 soluciones diferentes al problema de la la serie de Fibonacci en Python. Si deseas ver el enunciado del problema, haz click en el siguiente enlace. Si deseas entender el diseño algorítmico detrás de las soluciones presentadas, te invitamos a visitar el siguiente enlace.

A continuación presentaremos la implementación de las 4 soluciones propuestas. En primer lugar revisaremos las soluciones usando estructuras algorítmicas iterativas, posteriormente presentamos alternativas de solución usando el paradigma de programación modular. Finalmente, analizamos el problema desde la perspectiva de la programación dinámica.

Versión usando la instrucción while

La primera versión que presentaremos será diseñada usando una estructura algorítmica iterativa con entrada controlada. La analizaremos paso a paso.

Lectura de datos

Y empezamos con el primer paso, la lectura de los datos de entrada. Realizamos la lectura del valor de n.  Para la lectura de datos en Python usaremos la función \texttt{input}. Para leer el valor de n usaremos la variable \texttt{n}. Usamos la función \texttt{int} para transformar la cadena de caracteres en un valor entero a fin de almacenarlo en la variable entera \texttt{n}. Esta variable representará la cantidad de términos que debemos imprimir. Será fundamental para el control de flujo de la iteración.

n=int(input("Ingrese número de términos: ")) 

Validación de datos de entrada

El segundo paso corresponde con la validación de los datos de entrada, para esto usamos la estructura selectiva doble, la cual se implementa en Python a través de la instrucción \texttt{if-else}. Para que podamos realizar la impresión de los términos, pues la cantidad deberá ser mayor que cero. En caso que esto no se cumpla, emitiremos un mensaje informativo al usuario.

n=int(input("Ingrese número de términos: "))
if n<=0:
    print("Debe ingresar un número mayor que cero")
else: 

Impresión de los dos primeros números

Tal como menciona el enunciado, los dos primeros términos de la serie son fijos, por lo tanto usamos una selectiva simple para imprimirlos. En realidad, la primera selectiva (con la condición \texttt{n>=1}) la podemos omitir pues si es que el flujo se dirige hacia el bloque \texttt{else} es por que \texttt{n>0}, entonces siempre se cumplirá que \texttt{n>=1}

n=int(input("Ingrese número de términos: "))
if n<=0:
    print("Debe ingresar un número mayor que cero")
else:
    if n>=1:
        print("{:d} ".format(0) , end="")
    if n>=2:
        print("{:d} ".format(1) , end="") 

Control de flujo para los demás términos de la serie

A partir del tercer término, debemos calcular los mismos usando los dos términos anteriores. El cálculo de términos se repetirá tantas veces como términos falten imprimir. ¿Cuántos términos faltan imprimir? Pues deseamos imprimir n términos y ya se han impreso 2 pues faltan imprimir n-2 términos. Estos son los términos del 3 hasta el n¿Cómo repetimos un cálculo varias veces? Pues a través de una estructura algorítmica iterativa. Por lo tanto controlaremos una iteración para que el flujo se realice n-2 veces.  

Procederemos ahora a realizar el control de flujo de la iteración, usaremos para ello un ciclo iterativo con entrada controlada. Usaremos un control por variable el cual se configura usando los siguientes pasos:

  1. Inicializamos la variable de control. En este caso hemos definido la variable de control \texttt{i} y la hemos inicializado con el valor de \texttt{3}. La inicializamos con este valor pues queremos recorrer el rango [3..n]
  2. Controlamos el flujo usando la variable de control. Como queremos que se impriman \texttt{n-2} términos de la serie, la variable de control \texttt{i} debe actualizarse con  \texttt{n-2} valores, desde \texttt{3}, su valor inicial, hasta \texttt{n}, su valor final. Por lo tanto la condición de repetición será \texttt{i<=n}. Mientras esto sea verdad, se seguirá repitiendo. 
  3. Actualizamos el valor de la variable de control. Debemos cambiar la variable de control para que el ciclo iterativo no se haga infinito. Debemos garantizar que en algún momento en el tiempo, la condición se evalúe como falsa. Por lo tanto debemos incrementar \texttt{i} para que llegue a ser mayor que \texttt{n} y el ciclo termine. Por condiciones del problema, se incrementará en 1 a esta variable.
n=int(input("Ingrese número de términos: "))
if n<=0:
    print("Debe ingresar un número mayor que cero")
else:
    if n>=1:
        print("{:d} ".format(0) , end="")
    if n>=2:
        print("{:d} ".format(1) , end="")
    i=3
    while i<=n:

        i+=1 

Cálculo del término actual de la serie

Vamos a proceder con el cálculo del término actual de la serie y su correspondiente impresión. ¿Donde realizamos el cálculo y la impresión? Dentro de la iteración. Esto debido a que mientras se va a calculando se debe imprimir. ¿Cómo hacemos el cálculo? Pues, para eso se requiere de los dos términos anteriores. Para dicho fin, hemos creado las variables \texttt{anterior}\texttt{actual}.

 La variable \texttt{anterior}, como su nombre lo indica, contiene el valor anterior de la serie de Fibonnaci en relación al termino actual que deseamos calcular. Lo hemos inicializado con el valor de \texttt{0} que corresponde con el primer término de la serie de Fibonacci. La variable \texttt{actual} contiene el valor actual del término que estamos calculando de la serie de Fibonacci. Lo hemos inicializado con el valor de \texttt{1} que corresponde con el segundo término de la serie de Fibonacci. 

Como podrán notar, las variables han sido inicializadas considerando que el término actual es el número 2. Pero, ¿por qué los inicializamos con esos valores? Esto se ha realizado así, pues vamos a calcular de forma repetitiva a partir del tercer termino. La idea es que dentro de la iteración, estos valores se actualice.

Vamos a enfocarnos en este paso en el cálculo o actualización del valor actual del término. Para obtener el valor actual, hemos actualizado el valor de la variable \texttt{actual} con el valor de \texttt{actual+anterior}. Lo que estamos haciendo en realidad es actualizar el valor actual con el valor de los dos términos anteriores. El único detalle es que seguimos utilizando esas mismas variables. No hemos usado variables adicionales.

  • Cuando \texttt{i} tiene el valor de \texttt{3}\texttt{anterior} contiene el valor de \texttt{0}\texttt{actual} el valor de \texttt{1}. Al realizar esta operación \texttt{actual} contendría ahora el valor de \texttt{1}
  • Cuando \texttt{i} tiene el valor de \texttt{4}\texttt{anterior} contendrá el valor de \texttt{1}\texttt{actual} el valor de \texttt{1}. Al realizar la  operación de actualización  \texttt{actual} contendrá el valor de \texttt{2}
  • Cuando \texttt{i} tiene el valor de \texttt{5}\texttt{anterior} contendrá el valor de \texttt{1}\texttt{actual} el valor de \texttt{2}. Al realizar la  operación de actualización  \texttt{actual} contendrá el valor de \texttt{3}.
  • Cuando \texttt{i} tiene el valor de \texttt{6}\texttt{anterior} contendrá el valor de \texttt{2}\texttt{actual} el valor de \texttt{3}. Al realizar la  operación de actualización  \texttt{actual} contendrá el valor de \texttt{5}.
n=int(input("Ingrese número de términos: "))
if n<=0:
    print("Debe ingresar un número mayor que cero")
else:
    if n>=1:
        print("{:d} ".format(0) , end="")
    if n>=2:
        print("{:d} ".format(1) , end="")
    anterior=0
    actual=1
    i=3
    while i<=n:
        actual=actual+anterior
        print("{:d} ".format(actual) , end="")
        i+=1 

Actualización de las variables

El último paso es actualizar la variable \texttt{anterior}. La variable se debe actualizar con el valor de la serie de Fibonacci anterior. Por lo tanto debe actualizarse con el valor de \texttt{actual} antes que se modifique. Pero, ¿cúando hago la actualización? Si la hago antes de actualizar \texttt{actual}, luego perderé el valor de esta variable y fallará el cálculo del término actual. Si lo hago después de actulizar \texttt{actual}, ya no podré actualizar \texttt{anterior} con el valor actual anterior pues justamente acaba de ser cambiado. ¿Qué hacemos entonces? Pues, la solución es copiar el valor de la variable \texttt{actual} antes de hacer la actualización de la misma. De esta forma, el valor estará disponible luego de la actualización. La variable que mantiene la copia la hemos denominado \texttt{copia\_actual}, la actualizamos antes del cálculo del término actual y la usamos luego para actualizar el valor de la variable \texttt{anterior}

n=int(input("Ingrese número de términos: "))
if n<=0:
    print("Debe ingresar un número mayor que cero")
else:
    if n>=1:
        print("{:d} ".format(0) , end="")
    if n>=2:
        print("{:d} ".format(1) , end="")
    anterior=0
    actual=1
    i=3
    while i<=n:
        copia_actual=actual
        actual=actual+anterior
        anterior=copia_actual
        print("{:d} ".format(actual) , end="")
        i+=1 

Versión usando la instrucción for

Esta versión la implementaremos con la instrucción \texttt{for}. La instrucción \texttt{for} en Python realiza una iteración sobre una secuencia de números.  

La variable que contiene el valor de la secuencia en la iteración generalmente se representa con la variable \texttt{i} tal cual como está en nuestro algoritmo. Para generar una secuencia de números, Python ofrece una función de soporte llamada \texttt{range}. En nuestro caso hemos usado \texttt{range(3, n+1)}. El primer parámetro, en este caso \texttt{3}, corresponde con el primer número de la secuencia. El segundo parámetro, en este caso \texttt{n+1}, corresponde con el último parámetro del rango, pero hay que tener en consideración que dentro de la secuencia de números, no se retorna el \texttt{n+1}. En realidad \texttt{range} genera un intervalo semiabierto por la derecha, matemáticamente se suele representar \texttt{[a,b[}\texttt{[a,b)}. Entonces, la función \texttt{range(3, n+1)} retorna una secuencia de números en el rango [3,n+1[, o lo que es lo mismo de [3,n].

n=int(input("Ingrese número de términos: "))
if n<=0:
    print("Debe ingresar un número mayor que cero")
else:
    if n>=1:
        print("{:d} ".format(0) , end="")
    if n>=2:
        print("{:d} ".format(1) , end="")
    anterior=0
    actual=1
    for i in range(3, n+1):
        copia_actual=actual
        actual=actual+anterior
        anterior=copia_actual
        print("{:d} ".format(actual) , end="") 

Versión usando Programación Modular

La serie de Fibonacci es uno de los problemas clásicos en la computación que se analizan cuando se comienzan a revisar las estructuras iterativas y el paradigma de programación modular. En las siguientes secciones presentaremos distintos programas utilizando el paradigma de la programación modular, así como una versión realizada usando la técnica de programación dinámica.

Función principal

Realizaremos la implementación de la función principal. Esta será la misma para la versión recursiva. Tiene básicamente 3 objetivos:

  •  Leer el dato de entrada.
  • Validar el dato leído.
  • Iterar invocar a la función que va a realizar el cálculo del factorial.
 

Para la lectura de datos se utiliza la instrucción \texttt{input}. El dato leído será almacenado en la variable \texttt{n}. La validación la realizaremos con una selectiva doble. Se emitirá un mensaje informativo si es que el número es \texttt{<=0}.

Una vez que se han validado los datos, se procede a invocar a la función \texttt{fibonacci}. La función \texttt{fibonacci} retorna el valor del término de la serie de Fibonacci cuyo número de término se pasa como parámetro.

n=int(input("Ingrese número de términos: "))
if n<=0:
    print("Debe ingresar un número mayor que cero")
else:
     for i in range(1, n+1):
        print("{:d} ".format(fibonacci(i)) , end="") 

Función Fibonacci

La función \texttt{fibonacci} recibe como parámetro el número \texttt{n}. Se asume que este número \texttt{n} es mayor que cero. Este parámetro \texttt{n} indica el número del término que se solicita. La función retorna el n-ésimo término de la serie de Fibonacci.

La función se ha implementado usando la instrucción \texttt{for}.

def fibonacci(n):
    if n<=2:
        return n-1
    anterior=0
    actual=1
    for i in range(3, n+1):
        copia_actual=actual
        actual=actual+anterior
        anterior=copia_actual
    return actual 

Versión recursiva

La siguiente versión a implementar es la versión recursiva. Quizás sea la más simple de entender pues prácticamente es la representación en Python de la definición recursiva. Los algoritmos recursivos suelen ser simples de implementar pero en muchas ocasiones no son tan eficientes como las implementaciones iterativas.

def fibonacci(n):
    if n<=2:
        return n-1    
    return fibonacci(n-1)+fibonacci(n-2) 

Versión usando Programación Dinámica

Algoritmos como la determinación de un término de la serie de Fibonacci, poseen una característica especial, para hallar el valor de fib_n, debe calcularse fib_{n-1} y fib_{n-2}. Las versiones que hemos realizado con programación modular, poseen este problema. Y es un problema que, en algunas ocasiones, genera la utilización de módulos. 

Esto no ofrecería ningún problema si es que la función se ejecuta una sola vez, pero ¿qué pasa cuando en un programa necesitamos invocar varias veces a la función fibonacci? Pues, en ese caso las soluciones implementadas con programación modular no serian eficientes. Por ejemplo, imagínese que hacemos las invocaciones a las funciones \texttt{fibonacci(10)}\texttt{fibonacci(5)}. En este caso hipotético se repetirían muchos cálculos, algunos más de una vez.

¿Cómo evitamos recalcular tantas veces los términos de la serie de Fibonacci? Pues existe una técnicas de programación llamada programación dinámica que justamente busca reducir el tiempo de ejecución de los algoritmos. Esto lo logra reusando resultados obtenidos previamente. Estos resultados suelen ser almacenados en arreglos o matrices. 

Función principal

Vamos a implementar la función principal para el determinación de los términos de la serie de Fibonacci. Hay ligeros cambios en relación a las versiones anteriores. Los dos primeros objetivos son los mismo pero el tercer y cuarto son diferentes.

  •  Leer el dato de entrada.
  • Validar el dato leído.
  • Invocar al módulo que va a realizar la inicialización del arreglo.
  • Retornar el valor de la serie de Fibonacci usando el arreglo inicializado.
 
 
El primer gran cambio que vemos es que no existe una función \texttt{fibonacci}. Entonces ¿cómo se hace para hallar el valor del término de la serie? Pues en lugar de ello se usa un arreglo, al que convenientemente hemos denominado \texttt{fibonacci}. Dicho arreglo va a contener el valor de los términos de la serie de forma que \texttt{fibonacci[1]} contendrá el valor de \texttt{0}, \texttt{fibonacci[2]} contendrá el valor de \texttt{1} y en general \texttt{fibonacci[n]} contendrá el valor de fib_n.

 

Resulta muy sencillo el retornar los términos de la serie pero, ¿cómo se inicializa dicho arreglo? Pues este es en realidad el problema de la programación dinámica. Debemos llenar el arreglo con el valor de los términos de la serie antes de utilizar dicho arreglo. Esta inicialización la debemos hacer una única vez durante todo el programa.

El arreglo ha sido declarado con la instrucción \texttt{numpy.arrage[MAX\_TERMINOS+1]}. Se inicializa con un espacio para 101 elementos. Los índices válido para el arreglo serán [0..100]. Para este problema, no usaremos el índice 0

import numpy
    
MAX_TERMINOS=100
n=int(input("Ingrese número de términos (1﹤=n﹤=100): "))
if n﹤=0:
    print("Debe ingresar un número en el rango [0..100]")
else:
    fibonacci=numpy.arange(MAX_TERMINOS+1)
    inicializar_arreglo(fibonacci, MAX_TERMINOS)
    for i in range(1, n+1):
        print("{:d} ".format(fibonacci[i]) , end="") 

Inicialización del arreglo

A continuación presentamos el algoritmo para inicializar el arreglo. Básicamente lo que hacemos es inicializar el primer elemento (asumiendo el primer elemento el que se encuentra en la posición 1 y no en la 0) con el valor de \texttt{0}, el segundo con el valor de \texttt{1}. Luego en un ciclo iterativo, que en realidad puede ser usando cualquiera de las versiones previamente analizadas, se actualizan los demás elementos del arreglo. En dicha actualización siempre se usan los dos elementos anteriores.

def inicializar_arreglo(fibonacci, n):
    fibonacci[1] = 0;
    fibonacci[2] = 1;
    for i in range(3, n+1):
        fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2] 

Conclusión

Hemos presentado en este artículo, 4 alternativas de solución al clásico problema de la serie de Fibonacci usando Python. Se ha controlado el flujo usando estructuras selectivas e iterativas usando tanto ciclo con entrada controlada como salida controlada. Además se ha presentado versiones de la solución trabajando con el paradigma de programación modular, la  recursión así como la programación dinámica. Podrá descargar la solución propuesta en el repositorio GitHub de iterando++ a través del siguiente enlace

Hemos preparado otros artículos adicionales en donde describimos al detalle la implementación de este problema PSeInt y en otros lenguajes de programación. Te invitamos a leer los siguientes artículos de iterando++

Si te interesa profundizar más en el desarrollo en Python, los dos mejores libros que se han escrito son Learning Python de Mark Lutz y Python Crash Course de Eric Matthes.

Deja una respuesta

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