Algoritmos

PSEUDOCÓDIGO

El  pseudocódigo es un lenguaje de especificación de algoritmos (no de programación) basado en un sistema notacional, con estructuras sintácticas y semánticas, similares a los lenguajes procedurales, aunque menos formales que las de éstos, por lo que no puede ser ejecutado directamente por un computador. El pseudocódigo utiliza para representar las sucesivas acciones, palabras reservadas - similares a sus homónimas en los lenguajes de programación-, tales como inicio, fin, parar, si-entonces- sino, mientras-hacer, repetir-hasta, etc. La ventajas del uso del pseudocódigo residen en:

- Su uso en la planificación de un programa; permitiendo que el programador se pueda concentrar en la lógica y en las estructuras de control y no tenga que preocuparse, por ahora de detalles acerca de las reglas sintácticas y semánticas de un lenguaje específico. Consiguientemente es más fácil de modificar, en el caso de que se descubran errores o anomalías en la lógica del algoritmo.

- Aunque el pseudocódigo es independiente del lenguaje de alto nivel que vaya a utilizarse, un algoritmo expresado en pseudocódigo puede ser traducido más fácilmente a muchos de ellos.

Supongamos que tenemos un algoritmo para averiguar si un número es par, que puede ser descrito narrativamente de la siguiente forma: “Si restando consecutivamente dos del número se obtiene el numero 2, es par, si se obtiene otro valor (el 1), entonces es impar”. Este algoritmo escrito en pseudocódigo sería:

leer N

mientras N > 2 hacer

N ß  N - 2

si N = 2 entonces   

escribe “es par”

sino

 escribe “es impar”

fin

Nótese que en este ejemplo hemos utilizado dos estructuras que son muy usadas en programación: mientras-hacer y si-entonces- si_no; y que la escritura del pseudocódigo usa normalmente la indentación (sangría en el margen izquierdo) de diferentes líneas para ayudar a delimitar visualmente cada una de las estructuras utilizadas.

DIAGRAMAS DE FLUJO

Para ganar claridad expositiva se han desarrollado una serie de símbolos gráficos que permiten representar los algoritmos y que son universalmente reconocidos. Veamos algunos ejemplos:

Los organigramas o diagramas de flujo son herramientas gráficas utilizadas tanto para representar algoritmos, como en la ayuda en el diseño de programas. Están compuestos por una serie de símbolos, unidos con flechas, donde cada símbolo representa una acción distinta y las flechas el orden de realización de las acciones. Cada símbolo, por tanto, tendrá al menos una flecha que conduzca a él y una flecha que parta de él, exceptuando el comienzo y final del algoritmo. En la Figura siguiente, se muestran los símbolos utilizados habitualmente en la confección de organigramas, cuyo significado completaremos más adelante.

ESTRUCTURAS DE CONTROL

Los elementos básicos constitutivos de un programa son:

- palabras reservadas (inicio, si-entonces, etc.)

- identificadores (nombres de variables, procedimientos, etc.)

- caracteres especiales (coma, punto y coma, apóstrofo, etc.)

- constantes

- variables

- expresiones

- instrucciones

Sin embargo como hemos visto al diseñar algoritmos para escribir un programa, además de estos elementos básicos, hemos de conocer determinadas estructuras, cuyo objetivo es controlar su ejecución y sin cuya comprensión es imposible programar.

Llamaremos estructuras de control a las acciones que tienen por objeto marcar el orden de realización de los distintos pasos de un programa ó algoritmo. Cada estructura tiene un punto de entrada y uno de salida, lo que facilita la depuración de posibles errores. Estas son de tres tipos:

•  estructuras secuenciales

•  estructuras selectivas

•  estructuras repetitivas

y vamos a estudiarlas con un cierto detalle. El uso de las estructuras de control es una de las características de la programación estructurada que constituye la principal orientación de este texto, aunque otros lenguajes procedurales no estructurados también utilizan estas estructuras.

Estructuras secuenciales

Son aquéllas en las que una acción (instrucción) sigue a otra de acuerdo con su orden de escritura. Las tareas se suceden de tal modo que tras la salida (final) de una se efectúa la entrada (principio) en la siguiente y así sucesivamente hasta el fin del proceso. Su organigrama obedece al esquema de la Figura siguiente:

Las estructuras secuenciales se codifican de forma directa en cualquier lenguaje de programación, pues como sabemos el orden de ejecución de todo programa es precisamente, salvo orden en sentido contrario, de arriba abajo. A pesar de su simplicidad, ya sabemos, que algunos problemas se pueden resolver con la sola utilización de esta estructura, y codificado en los diferentes lenguajes de programación.

Estructuras selectivas

Como hemos tenido ocasión de comprobar, la especificación formal de algoritmos tiene utilidad real, cuando éstos requieren una descripción más complicada que una simple secuencia de instrucciones. Uno de estos casos se produce cuando existen varias alternativas, resultantes de la evaluación de una determinada condición, como ocurre, por ejemplo, al resolver una ecuación de segundo grado, donde el procedimiento a seguir es distinto según el discriminante sea positivo, nulo ó negativo. Las estructuras selectivas en un programa se utilizan para tomar decisiones, de ahí que se suelan denominar también estructuras de decisión o alternativas. En estas estructuras se evalúa una condición, especificada mediante expresiones lógicas, en función de cuyo resultado, se realiza una opción u otra. En una primera aproximación, para esta toma de decisiones, podemos pensar en una variable interruptor o conmutador (switch), que representa un estado y por tanto puede cambiar de valor a lo largo de la ejecución regulando el paso a una u otra parte del programa, lo que supone una bifurcación en el flujo del programa, dependiendo del valor que tome el conmutador. Los interruptores pueden tomar dos valores diferentes, frecuentemente 1 y 0, de ahí su nombre de interruptor (“encendido”/“apagado”, “abierto”/“cerrado”). En la Figura siguiente, si SW es igual a 1, se ejecuta la acción S1; y si SW es igual a 0, se ejecuta la acción S2.

Ejemplo :

Sea un archivo formado por un conjunto de registros constituidos por dos campos, M y N. Se desea listar el campo M de los registros pares y el campo N de los registros impares. Expresar el algoritmo correspondiente en forma de organigrama.

En el ejemplo SW es un interruptor que se inicializa con un valor determinado (0 en este caso) y luego se va modificando su valor alternativamente a medida que se leen los registros. De este modo, cuando SW = 0 se leerán las fichas impares y cuando SW = 1 se leerán las fichas pares.

Alternativas simples (si-entonces/if-then)

La estructura alternativa más sencilla, es la llamada simple y se representa por  si-entonces. Su efecto es el de ejecutar una determinada acción cuando se cumple una cierta condición y en caso contrario seguir el orden secuencial. La selección si-entonces evalúa la condición y de acuerdo con su resultado:

- Si es verdadera, entonces ejecuta una o varias acciones (S1).

- Si es falsa, entonces no hace nada y sigue la ejecución normal del programa, pasando a la instrucción siguiente a la finalización de la estructura selectiva. Para ello es necesario que ésta venga claramente delimitada, cosa que se hace en pseudocódigo con fin_si.

Su expresión en Pseudocódigo (para S1 compuesta de varias acciones) es:

si <condición> entonces

<acciones>

fin_si

En el lenguaje C se escribe así:

if (condicion)

{

S1

S2

...

Sn

};

Alternativas dobles (si-entonces-si_no/if-then-else)

La estructura anterior es muy limitada y muchas veces se necesitará una estructura que permita elegir entre dos opciones o alternativas posibles en función del cumplimiento o no de una condición, que juega el papel de un interruptor. Si la condición es verdadera, se ejecuta la acción o acciones S1, y si es falsa, se ejecuta la acción ó acciones S2, pasando en cualquier caso a la instrucción siguiente a la finalización de la estructura selectiva. El pseudocódigo correspondiente es el siguiente:

si <condición> entonces

<acciones S1>

si_no

<acciones S2>

fin_si

En lenguaje C:

if (condicion)

{

acciones S1

}

else

{

acciones S2

}

Ejemplo:

Informar si un estudiante ha superado o no un determinado examen consistente en 20 preguntas de igual valor y calcular su nota en caso de aprobar.

leer num_correctas

si num_correctas < 10 entonces

escribir “no ha superado Vd. el examen”

faltan  ß  10 - num_correctas

escribir “le faltaron” , faltan

si_no

 nota ß  num_correctas / 2

escribir “aprobó Vd. con un” , nota

fin_si

Alternativas múltiples (según_sea, en_caso_de)

Con frecuencia existen más de dos elecciones posibles (por ejemplo, en la resolución de la ecuación de segundo grado hay tres casos). La estructura de alternativa múltiple evaluará una expresión que podrá tomar n valores (o grupos de valores) distintos e1, e2,....,en. Según el valor que tome la condición, se realizará una de las n acciones posibles, o lo que es lo mismo, el flujo del algoritmo seguirá un determinado camino entre los n posibles.

La estructura de decisión múltiple en pseudocódigo se puede representar de diversas formas, aunque la más simple es la siguiente (donde e1, e2, ....., en son los distintos valores (o grupos de ellos) que puede tomar la evaluación de la expresión que sirve de condición):

según_sea  expresión (E) hacer

            e1:  <acciones S1>

            e2:  <acciones S2>

            ...

            en:  <acción Sn>

fin_según

Ejemplo :

Escribir un algoritmo que permita obtener las raíces reales de la ecuación de segundo grado, ax2 + bx + c.

inicio

leer a,b,c

D ß  b^2-4*a*c

segun_sea D hacer

D<0:   escribir “raíces complejas” {no existen raíces reales}

D=0:   x ß   -b/2a

escribir x , “raiz doble”

D>0:   rc ß  raizcua(D)

x1 ß (-b-rc)/2a

x2 ß (-b+rc)/2a

escribir x1,x2

fin_segun

fin

Para implementar esta estructura de alternativas múltiples hemos de recurrir a estructuras alternativas simples o dobles, adecuadamente enlazadas. Las estructuras de selección si-entonces y si_entonces_sino implican la selección de una de dos alternativas y utilizándolas debidamente, es posible diseñar con ellas estructuras de selección que contengan más de dos posibilidades. Una estructura si-entonces puede contener otra y así sucesivamente cualquier número de veces (se dice que las estructuras están anidadas o en cascada). El esquema es del tipo:

si (condición e1) entonces

<acciones S1>

sino

            si (condición e2) entonces

<acciones S2>

sino

 si (condición e3) entonces

<acciones S3>

sino

...

<acciones Sn>

fin_si

fin_si

fin_si

ESTRUCTURAS REPETITIVAS

El computador está especialmente diseñado para aplicaciones en las que una operación o un conjunto de ellas deben repetirse muchas veces. En este sentido, definiremos  bucle o lazo (loop), como un segmento de un programa cuyas instrucciones se repiten bien un número determinado de veces o mientras se cumpla una determinada condición.

Es imprescindible que se establezcan mecanismos para controlar esta tarea repetitiva, ya que si éstos no existen, el bucle puede convertirse en un proceso infinito. Así, en el bucle representado por el organigrama de la Figura 3.10, se observa que las instrucciones incluidas en él se repiten indefinidamente. El mecanismo de control citado se establece mediante una condición que se comprueba en cada paso o iteración del bucle. En la Figura  se coloca una condición tras la lectura de la variable N (comprobar si su valor es cero), de forma que tenemos la oportunidad de que el bucle deje de ser infinito, ya que podrá interrumpirse cuando la condición sea verdadera.

Los procesos que se repiten varias veces en un programa necesitan en muchas ocasiones contar el numero de repeticiones habidas. Una forma de hacerlo es utilizar una variable llamada contador, cuyo valor se incrementa o decrementa en una cantidad constante en cada repetición que se produzca. La Figura 3.12 presenta un diagrama de flujo para un algoritmo en el que se desea repetir 50 veces un grupo de instrucciones, que llamaremos cuerpo del bucle, donde el contador se representa con la variable CONT. La instrucción que actualiza al contador es la asignación:

 CONT ß  CONT+1.

El contador puede ser positivo (incrementos de uno en uno) o negativo (decrementos de uno en uno). En la Figura, el contador cuenta desde 1 a 50 y deja de repetirse cuando la variable CONT toma el valor 51 y termina el bucle. En la Figura 3.13 se muestra un algoritmo que efectúa la operación de multiplicación n x m, sumando m un número n de veces. En él, el contador se decrementa: comienzaa contar en n y se va decrementando hasta llegar a cero; en ese momento se termina el bucle y se realiza la acción escribir.

Otro tipo de variable, normalmente asociada al funcionamiento de un bucle es un acumulador o totalizador, cuya misión es almacenar una cantidad variable, resultante de operaciones sucesivas y repetidas. Un acumulador realiza una función parecida a la de un contador, con la diferencia de que el incremento o decremento, de cada operación es variable en lugar de constante.

Una  estructura repetitiva es aquella que marca la reiteración de una serie de acciones basándose en un bucle. De acuerdo con lo anterior, esta estructura debe constar de tres partes básicas:

- decisión (para finalizar la repetición)

- cuerpo del bucle (conjunto de instrucciones que se repiten)

- salida del bucle (instrucción a la que se accede una vez  se decide finalizar)

Tomando el caso de la Figura 3.11, donde para obtener la suma de una serie de números, hemos utilizado la estrategia siguiente: tras leer cada número lo añadimos a una variable SUMA que contenga las sucesivas sumas parciales (SUMA se hace igual a cero al inicio). Observemos que el algoritmo correspondiente deberá utilizar sucesivamente instrucciones tales como:

leer número

si N < 0 entonces

   escribir SUMA

si-no

   SUMA  ß SUMA+número

fin-si

que se pueden repetir muchas veces; éstas constituyen el cuerpo del bucle.

Una vez se ha decidido el cuerpo del bucle, se plantea la cuestión de cuántas veces se debe repetir. De hecho conocemos ya la necesidad de contar con una condición para detener el bucle. En el Ejemplo 8, se pide al usuario el número N de números que desea sumar, esto es, el número de iteraciones del bucle.

Usamos un contador de iteraciones, TOTAL, que se inicializa a N y a continuación se decrementa en uno cada vez que el bucle se repite; para ello introducimos una acción más al cuerpo del bucle: TOTAL ß  TOTAL -1. También podríamos inicializar la variable TOTAL en 0 o en 1, e ir incrementándolo en uno, en cada iteración, hasta llegar al número deseado N.

Ejemplo :

Hallar la suma de N números, a través de una estructura repetitiva

algoritmo suma_números

{leer número total de números a sumar en variable N}

TOTAL ß   N

SUMA ß  0   { la suma parcial es 0 al inicio}

{comienzo de bucle}

mientras que TOTAL > 0 hacer

leer número

SUMA ß  SUMA+número

TOTAL ß  TOTAL-1

fin_mientras

{fin del bucle}

escribir “la suma de los” , N , “números es “ , SUMA

Aunque la condición de finalización puede evaluarse en distintos lugares del algoritmo, no es recomendable que ésta se pueda efectuar a mitad del cuerpo del bucle, por lo que es bueno que se produzca al principio o al final del mismo. Según donde se sitúe la  condición de salida, dará lugar a distintos tipos de estructuras repetitivas que analizaremos a continuación: estructura desde-hasta, estructura mientras y estructura repetir-hasta_que.

ESTRUCTURA DESDE-HASTA

Esta estructura consiste en que la condición de salida se basa en un contador que cuenta el número de iteraciones. Por ejemplo, el ejemplo 8 podría hacerse de la siguiente manera:

desde i = 1 hasta N con_incremento 1 hacer

            leer número

            SUMA ß  SUMA + número

fin_desde

donde i es un contador que cuenta desde un valor inicial (1) hasta el valor final (N) con los incrementos que se consideren (de uno en uno en este caso). Esta es la llamada estructura Desde (“for”), que es la más simple desde el punto de vista de la condición de salida, ya que viene predeterminada por el código. Su utilidad reside en el hecho de que, en muchas ocasiones, se conoce de antemano el número de iteraciones. Esta estructura ejecuta las acciones del cuerpo del bucle, un número especificado de veces y de modo automático controla el número de iteraciones. Su formato en pseudocódigo es:

desde v=vi hasta vf hacer

   <acciones>

   .

   .

fin_desde

v: variable índice

vi, vf: valores inicial y final de la variable

La variable índice o de control normalmente será de tipo entero y es normal emplear como identificador, las letras I,J,K como herencia de los índices y subíndices utilizados en cálculo científico. El incremento  de la variable índice es 1 en cada iteración si no se indica expresamente lo contrario. Si debemos expresar incrementos distintos de +1 el formato de la estructura es:

desde v = vi hasta vf inc incremento hacer

   <acciones>  si vi > vf entonces usar

   .  en lugar de  inc incremento

   .  la expresión dec decremento

fin_desde

Obviamente, si el valor inicial de la variable índice es menor que el valor final, los incrementos deben ser positivos, ya que en caso contrario la secuencia de acciones no se ejecutaría. De igual modo si el valor inicial es mayor que el valor final, el incremento debe ser en este caso negativo. Así:

desde I=20 hasta 10 hacer

<acciones>

fin_desde

for(v=vi; v<=vf; vt+=step)

<accion o bloque de acciones >

 (más genéricamente)

for(inicio;condición;actualización)

<accion o bloque de acciones >

ESTRUCTURA MIENTRAS

Cuando la condición de salida del bucle se realiza al principio del mismo, éste se ejecuta mientras se verifica una cierta condición. Es la llamada estructura repetitiva  mientras (“while”); en ella el cuerpo del bucle se repite mientras se cumple una determinada condición. Su pseudocódigo es:

mientras condición hacer

<acciones>

fin_mientras

Cuando se ejecuta la instrucción mientras, la primera cosa que sucede es la evaluación de la condición. Si es falsa, no se ejecuta ninguna acción y el programa prosigue en la siguiente instrucción a la finalización del bucle; si la condición es verdadera, entonces se ejecuta el cuerpo del bucle. No todos los lenguajes incluyen

la estructura mientras.

En lenguaje C:

while (condicion)

<accion>

Obsérvese que en una estructura mientras si la primera evaluación de la condición es  falsa, el cuerpo del bucle nunca se ejecuta. Puede parecer inútil ejecutar el cuerpo del bucle cero veces, ya que no tendrá efecto en ningún valor o salida; sin embargo, puede ser una acción deseada. Por ejemplo el siguiente bucle para procesar las notas de unos examenes contando el número de alumnos presentados dejará de ejecutarse cuando el numero leído sea negativo. Si la primera nota introducida fuera negativa, la acción deseada es, efectivamente, que no se ejecute el bucle ninguna vez.

C  ß 0

leer nota

mientras nota = 0 hacer

{procesar nota}

C  ß C+1

leer nota

fin_mientras

ESTRUCTURA REPETIR-HASTA_QUE

En esta estructura la condición de salida se sitúa al final del bucle; el bucle se ejecuta hasta que se verifique una cierta condición. Es la llamada estructura Repetir-hasta (“repeat-until”). Existen muchas situaciones en las que se desea que un bucle se ejecute al menos una vez, antes de comprobar la condición de repetición. Para ello la estructura repetir-hasta_que se ejecuta hasta que se cumpla una condición determinada que se comprueba al final del bucle. En pseudocódigo se escribe:

repetir

   <acciones>

hasta_que <condición>

do

<accion o bloque>

while (condicion);

(en C se “dice” mientras se cumpla la condición, no hasta que se cumpla)

El bucle repetir-hasta_que se repite mientras la condición sea falsa, justo lo opuesto a la estructura mientras. Sea el siguiente algoritmo:

inicio

            contador ß 1

            repetir

            leer número

            ontador  ß contador+1

            hasta_que contador > 30

            escribir “números leídos: 30”

fin

Este bucle se repite hasta que el valor de variable contador exceda a 30, lo que sucederá después de 30 ejecuciones del mismo. Nótese que si en vez de 30 pusiéramos 0, el cuerpo del bucle se ejecutará siempre al menos una vez.

Ejemplo :

Calcular el factorial de un número N, usando la estructura repetir.

inicio

            leer N

            Factorial  ß1

            I ß  1

            repetir

                        Factorial  Factorial * I

                        I ß  I+1

            hasta_que I > N

            escribir “el factorial del número”, N, “es”, Factorial

fin

Las tres estructuras repetitivas son susceptibles de intercambio entre  ellas, así por ejemplo es posible, sustituir una estructura desde, por una mientras; con incrementos positivos o negativos de la variable índice. En efecto, la estructura desde con incremento positivo es equivalente a la estructura mientras marcada con la A), y la estructura desde con incremento negativo es equivalente a la estructura mientras marcada con la B).

A)                                                                   B)

v ß  vi                                                           v ß  vi

mientras v < = vf hacer                              mientras v > = vf hacer

            <acciones>                                                             <acciones>

v ß  v + incremento                                   v ß  v - decremento

fin_mientras                                                            fin_mientras

Ejemplo 10:

Calcular los factoriales de n números leídos por el teclado.

El problema consiste en realizar una primera estructura repetitiva de n iteraciones del algoritmo de cálculo del factorial, que a su vez se efectúa con una segunda estructura repetitiva.

inicio

leer n  {lectura de la cantidad de números}

desde i = 1 hasta n hacer

leer NUMERO

FACTORIAL ß 1

desde j = 1 hasta NUMERO hacer

ACTORIALß  FACTORIAL *j

fin_desde

escribir “el factorial del número”, NUMERO, “es”, FACTORIAL

fin_desde

fin