Factorial en PSeInt

Más ejercicios resueltos

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

Calcular el factorial de un número es uno de los problemas clásicos que se suelen analizar cuando se inicia en el mundo del paradigma de programación modular. Es típico que se desarrollen ejemplos de la función factorial en esta fase. En este artículo, analizamos al detalle y paso a paso, algoritmos para el cálculo del factorial en PSeInt presentando 6 alternativas de solución a través de diversas versiones usando estructuras algorítmicas iterativas, la recursión así como la programación dinámica. Si deseas conocer con más detalle la definición del factorial usada en este problema, haz click en el siguiente enlace.

Parte de esta análisis se encuentra sintetizado en el vídeo «Factorial Iterativo en PSeInt» en nuestro canal de YouTube. Te invitamos a que lo visites.

A continuación presentamos las 6 alternativas de solución que nos permitirán entender cómo se calculan los factoriales en PSeInt. Se analizará cada alternativa con sumo detalle. Las versiones que se analizarán son las siguientes:

  • Módulo principal.
  • Versión con instrucción \texttt{Mientras}.
  • Versión con instrucción \texttt{Repetir-Mientras Que}.
  • Versión con instrucción \texttt{Repetir–Hasta Que}.
  • Versión con instrucción \texttt{Para}.
  • Versión recursiva.
  • Versión usando Programación Dinámica.

Módulo principal

Realizaremos el diseño del módulo principal. Este será él mismo para las primeras 5 versiones. Tiene básicamente 3 objetivos:

  •  Leer el dato de entrada.
  • Validar el dato leído.
  • Invocar al módulo que va a realizar el cálculo del factorial.
 
Para la lectura de datos hemos utilizado 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 que en PSeInt se implementa con la estructura de control \texttt{Si..SiNo}. Se emitirá un mensaje informativo si es que el número es menor que 0 pues el factorial no está definido para números negativos o si el número es mayor que 22. Pero, ¿por qué no dejamos que el número n sea mayor que 22? Pues, como ya vimos antes, sucede que los factoriales incrementan su magnitud muy rápido y en PSeInt, en la versión que estamos usando, el factorial de 23 sobrepasa el rango de representación permitido para las variables.
 
Una vez que la variable se ha validado, se procede a invocar al módulo factorial usando como argumento el número \texttt{n} leído. La invocación se realiza al momento de hacer la impresión. En la impresión además, estamos incluyendo al lado del número, el carácter de admiración (!) para que se imprima el número con la notación más conocida para el factorial.
pseudocódigo factorial módulo principal
Módulo principal

Módulo Factorial: versión con instrucción Mientras

Pasaremos ahora a diseñar la primera versión. Esta versión permitirá calcular el factorial de un número en PSeInt usando un ciclo Mientras. Antes de describir la implementación, analizaremos los datos de entrada y de salida de este módulo. El módulo \texttt{factorial} recibe como parámetro el número \texttt{n}. Se asume que este número \texttt{n} es mayor o igual que cero. El módulo retorna la productoria que contiene el factorial del parámetro \texttt{n}.

El siguiente paso a realizar es el control de flujo. La implementación de esta versión se basa en una estructura iterativa con entrada controlada. Diseñaremos el control de flujo usando un contador, al que se le suele denominar variable de control. Hemos nombrado esta variable de control con el identificador \texttt{i}. Como deseamos generar todos los factores de la productoria, inicializamos la variable de control con el valor de 2. La iniciamos en 2  dado que 1 es el elemento neutro para la nultiplicación, por lo tanto multiplicar por 1 no afecta en nada a la productoria. De esta manera nos ahorramos una iteración.

En PSeInt, la entrada controlada se implementa mediante la instrucción \texttt{Mientras}. Colocamos como condición de la iteración \texttt{i<=n}. Esto significa que la iteración se realizará mientras esta condición se cumpla. Como tenemos que garantizar que la iteración finalice en algún instante del tiempo, actualizamos la variable de control. Al finalizar de la iteración, incrementamos su valor en 1. De esta manera en la próxima iteración \texttt{i} contendrá el valor del siguiente factor a utilizar para el cálculo de la productoria.

La productoria se almacena convenientemente en la variable llamada \texttt{productoria}. Inicializamos a la productoria con el valor de 1 por ser el elemento neutro para la multiplicación. Y actualizamos su valor dentro de la iteración. En la actualización simplemente multiplicamos el valor de la \texttt{productoria} por \texttt{i}, nos aseguramos que esta actualización se realice antes de actualizar la variable \texttt{i}.

El valor que retorna este módulo es el que se encuentra en la variable \texttt{productoria}. Esto ha sido definido en la cabecera de la función.

pseudocódigo factorial v1
Módulo Factorial: versión con instrucción Mientras

Módulo Factorial: versión con instrucción Repetir-Mientras Que

Pasaremos ahora a diseñar la segunda versión. Esta versión permitirá calcular el factorial de un número en PSeInt usando un ciclo Repetir Mientras Que. En PSeInt existen dos maneras de implementar la salida controlada, la primera de ellas es mediante la instrucción \texttt{Repetir–Mientras Que}.  

Esta instrucción se caracteriza por repetir el conjunto de instrucciones asociado mientras la condición de iteración se cumpla. Pero, a diferencia de la entrada controlada, en la salida controlada, el control de flujo se gestiona luego de la ejecución del bloque de instrucciones asociado a la estructura iterativa. En términos prácticos, esto significa que en una salida controlada, el bloque de instrucciones se ejecuta siempre por lo menos una vez.

Por esta razón, no podemos inicializar la variable de control \texttt{i}  con el valor de 2 ya que dentro de la iteración la variable \texttt{productoria}  se multiplica por \texttt{i} . Como esto se ejecuta por lo menos una vez, no permitirá calcular el factorial de cero ni de uno, por este motivo, la variable de control \texttt{i}  se debe inicializar con el valor de 1.

pseudocódigo factorial v2
Módulo Factorial: versión con instrucción Repetir-Mientras Que

Módulo Factorial: versión con instrucción Repetir-Hasta Que

Pasaremos ahora a diseñar la tercera versión. Esta versión permitirá calcular el factorial de un número en PSeInt usando un ciclo Repetir Hasta Que. Justamente, la otra manera de implementar la salida controlada en PSeInt es mediante la instrucción \texttt{Repetir–Hasta\ Que}. Esta instrucción se caracteriza por repetir el conjunto de instrucciones asociado hasta que la condición de iteración se cumpla. A diferencia de la instrucción \texttt{Repetir-Mientras\ Que}, esta instrucción para de iterar cuando la condición se cumple e itera cuando la condición no se cumple.

Es muy sencillo transformar el control de flujo de entre ambas estructuras iterativas con salida controlada, basta negar la condición de una para transformarla en la otra. Por este motivo la condición de parada de este ciclo es \texttt{i>n}, la negación de la condición de la versión anterior katex]\texttt{i<=n}[/katex].

pseudocódigo factorial v3
Módulo Factorial: versión con instrucción Repetir-Hasta Que

Módulo Factorial: versión con instrucción Para

A continuación, procederemos a analizar la implementación del cálculo del factorial usando la instrucción Para en PSeInt. La instrucción \texttt{Para} permite ejecutar un conjunto de iteraciones una determinada cantidad de veces, recorriendo una secuencia de números.  Para esto utiliza una variable de control la cual la debemos inicializar con un valor que corresponderá con el inicio de la secuencia. El ciclo terminará cuando la variable de control llegue a un determinado valor que corresponde con el fin de la secuencia el cual también debe ser configurado.

En el caso del cálculo del factorial, la variable de control la hemos denominado \texttt{i} y la inicializamos en 2 . La instrucción iterará hasta que el valor de \texttt{i} sea igual a \texttt{n} y cada vez que se termine la iteración, la variable se incrementa en 1 . La ventaja que ofrece la instrucción \texttt{Para} es que la inicialización de la variable de control, la configuración del valor de parada y el incremento, se configura en un solo lugar de la instrucción, a diferencia de las otras estructuras algorítmicas iterativas.

La iteración producirá diferentes valores de \texttt{i} en cada ciclo, usamos este hecho para generar la productoria deseada. Para esto se inicializa la \texttt{productoria}en 1  y en cada ciclo, se multiplica por el valor de \texttt{i}.

pseudocódigo factorial v4
Módulo Factorial: versión con instrucción Para

Módulo Factorial: versión recursiva

La quinta 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 factorial v5
Módulo Factorial: versión recursiva

Módulo Factorial: versión usando Programación Dinámica

Algoritmos como el cálculo de factorial poseen una característica, para hallar el valor de n!, debe calcularse (n-1)!. Esto se realiza independientemente de la versión y no importa si la versión es iterativa o recursiva.

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 factorial? Pues, en ese caso las soluciones implementadas no serian eficientes. Por ejemplo, imagínese que hacemos las invocaciones a las funciones \texttt{factorial(4)}\texttt{factorial(6)}. En este caso hipotético se calcularían dos veces el \texttt{factorial(4)} lo que es un uso innecesario de tiempo.

¿Cómo evitamos recalcular tantas veces los factoriales? 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 cálculo del factorial. 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 del factorial usando el arreglo inicializado.
 
 
El primer gran cambio que vemos es que no existe un módulo \texttt{factorial}. Entonces ¿cómo se hace para hallar el valor del factorial? Pues en lugar de ello se usa un arreglo, al que convenientemente hemos denominado \texttt{factorial}. Dicho arreglo va a contener el valor de los factoriales de forma que \texttt{factorial[0]} contendrá el valor del factorial de \texttt{0}, \texttt{factorial[1]} contendrá el valor del factorial de \texttt{1} y en general \texttt{factorial[n]} contendrá el valor del factorial de \texttt{n}.

 

Resulta muy sencillo el retornar los factoriales 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 factoriales antes de usar el 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[21]}. Esto significa que el arreglo tendrá 21 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..20]. Creamos un arreglo cuyo máximo índice es el valor de 20 debido a que es el máximo factorial que se puede representar en PSeInt.

pseudocódigo factorial v6 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 con el valor de \texttt{0}. 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 usa el valor anterior.

pseudocódigo factorial v6 inicialización
Inicialización del arreglo

Conclusión

Hemos presentado en este artículo, 6 alternativas de solución al cálculo del factorial usando PSeInt. Se ha utilizado estructuras iterativas con entrada controladasalida controlada, recursión y 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 *