Fibonacci en PSeInt

Más ejercicios resueltos

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

A continuación presentamos 6 soluciones diferentes al problema de la la serie de Fibonacci en PSeInt. Si deseas ver el enunciado del problema, haz click en el siguiente enlace.

A continuación presentaremos el diseño algoritmo de las 6 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 Mientras

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 esto usamos la instrucción \texttt{Leer} asignando el valor leído en la variable \texttt{n}. Esta variable representará la cantidad de términos que debemos imprimir. Será fundamental para el control de flujo de la iteración.

pseudocódigo fibonacci con mientras paso 1
Lectura de datos

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 PSeInt a través de la instrucción \texttt{Si-SiNo}. 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.

pseudocódigo fibonacci con mientras paso 2
Validación de datos de entrada

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{SiNo} es por que \texttt{n>0}, entonces siempre se cumplirá que \texttt{n>=1}

pseudocódigo fibonacci con mientras paso 3
Impresión de los dos primeros números

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.
pseudocódigo fibonacci con mientras paso 4
Control de flujo para los demás términos de la serie

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}.
pseudocódigo fibonacci con mientras paso 5
Cálculo del término actual de la serie

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}

pseudocódigo fibonacci con mientras paso 6
Actualización de las variables

Versión usando la instrucción Para

La instrucción \texttt{Para} es una estructura iterativa que permite repetir un bloque de instrucciones. Para esto le indicamos a la instrucción que requeremos iniciar con el valor de 3 (\texttt{i<-3}), al finalizar la iteración, esta valor lo incrementamos en 1 (\texttt{Con Paso 1}), mientras \texttt{i} sea igual a \texttt{n}. Por lo demás el diseño algorítmico es similar.

pseudocódigo fibonacci con para
Versión usando la instrucción Para

Versión usando la instrucción Repetir-Mientras Que

Ahora veamos una versión en la cual usamos la estructura iterativa con salida controlada. En PSeInt la implementamos con la instrucción \texttt{Repetir-Mientras\ Que}. En este algoritmo también usaremos la variable  \texttt{i} para el control de flujo. Inicializamos la variable de control \texttt{i} con el valor de 2. A diferencia de la versión anterior, no podemos inicializar \texttt{i} con el valor de 3 ya que al realizarse un control en la salida, la iteración debe necesariamente ejecutarse por lo menos una vez.

Esta estructura algorítmica iterativa, siempre imprime por lo menos una término. Y, ¿qué término es ese? Pues, el término 2. Por ese motivo, solamente se ejecuta si es que \texttt{n>=2}. La lógica del algoritmo es muy similar al anterior.

pseudocódigo serie de fibonacci con repetir-mientras
Versión usando la instrucción Repetir-Mientras Que

Versión usando la instrucción Repetir-Hasta Que

Usamos otra forma de la estructura con salida controlada, en este caso la instrucción \texttt{Repetir-Hasta\ Que}. Esta instrucción itera y para cuando la condición de salida es verdadera. En realidad el único cambio que hay en relación a la versión anterior es que la condición de este ciclo es la negación de la condición de la versión anterior. Por lo demás, es la misma lógica computacional.

pseudocódigo serie de fibonacci con repetir-hasta
Versión usando la instrucción Repetir-Hasta Que

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 pseudocódigos utilizando el paradigma de la programación modular, así como una versión realizada usando la técnica de programación dinámica.

Módulo principal

Realizaremos el diseño del módulo principal. Este será él mismo para la versión recursiva. Tiene básicamente 3 objetivos:

  •  Leer el dato de entrada.
  • Validar el dato leído.
  • Iterar e invocar al módulo que va a realizar el cálculo del factorial.
 
Para la lectura de datos se utiliza la instrucción \texttt{Leer}. 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 al módulo \texttt{fibonacci}. El módulo \texttt{fibonacci} retorna el valor del término de la serie de Fibonacci cuyo número de término se pasa como parámetro.
pseudocódigo fibonacci - módulo principal
Módulo principal

Módulo Fibonacci

El módulo \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. El módulo retorna el n-ésimo término de la serie de Fibonacci.

El módulo se ha implementado con una iterativa con salida controlada. Es muy similar a la versión iterativa presentada anteriormente. Analice con cuidado esta versión con la anterior y notará la diferencia. Como siempre comentamos, existen muchas maneras de llegar a la misma solución.

pseudocódigo fibonacci - módulo fibonacci iterativo
Módulo Fibonacci

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 PSeInt 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.

pseudocódigo fibonacci - módulo recursivo
Versión recursiva

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. 

Módulo principal

Vamos a diseñar el módulo 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 un módulo \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 algoritmo.

El arreglo ha sido declarado con la instrucción \texttt{Dimension fibonacci[80]}. Esto significa que el arreglo tendrá 80 elementos. Como tenemos configurada la opción en PSeInt \texttt{Utilizar índices en arreglos y cadenas en base 0}, los índices válido para el arreglo serán [0..79]. Para este problema, no usaremos el índice 0. Creamos un arreglo cuyo máximo índice es el valor de 79 debido a que es el máximo término que Fibonacci que se puede representar en PSeInt.

pseudocódigo fibonacci - programación dinámica- módulo principal
Módulo principal

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.

pseudocódigo fibonacci - programación dinámica- inicialización
Inicialización del arreglo

Conclusión

Hemos presentado en este artículo, 6 alternativas de solución al clásico problema de la serie de Fibonacci usando PSeInt. 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 en lenguajes de programación. Te invitamos a leer los siguientes artículos de iterando++

Si te interesa profundizar más sobre diseño algorítmico, te recomendamos el libro Foundations of Programming Languages de Kent D. D. Lee. En este libro encontrarás además información detallada sobre la programación orientada a objetos, funcional y lógica.

Deja una respuesta

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