UNIDAD ACADMICA PROFESIONAL TIANGUISTENCO UNIVERSIDAD AUTNOMA DEL ESTADO DE MXICO

Apuntes:

Algortmica
Impartido en semestre 2011B CARRERA: Ingeniera de Software Elaborado por: Dra. Yulia Nikolaevna Ledeneva

Santiago Tianguistenco, Agosto de 2011

UNIDAD ACADMICA PROFESIONAL TIANGUISTENCO UNIVERSIDAD AUTNOMA DEL ESTADO DE MXICO

II. Estructuras bsicas de control y tipos de datos simples

2.1 Estructuras de control. Los algoritmos definidos hasta este punto se ejecutan de modo secuencial, es decir, una secuencia despus de otra. La ejecucin comienza con la primera sentencia del algoritmo y sigue hasta la ltima sentencia, cada una de las cuales se ejecuta una sola vez. Esta forma de programacin es adecuada para la resolucin de problemas sencillos. Sin embargo, para la resolucin de problemas de tipo general se necesita la capacitad de controlar cules son las sentencias que se ejecutan en qu momentos. Las estructuras o construcciones de control controlan la secuencia o flujo de ejecucin de las sentencias. Las estructuras de control permiten combinar instrucciones o sentencias individuales en una simple unidad lgica con un punto de entrada y un punto de salida. Las estructuras de control se dividen en tres grandes categoras en funcin del flujo de ejecucin: secuencia seleccin repeticin (iteracin). Una sentencia compuesta es un conjunto de sentencias encerradas entre llaves ({ y }) que se utiliza para especificar un flujo secuencial. { instruccinA; instruccinB; }

El control fluye de la instruccinA a la instruccinB, y as sucesivamente. Sin embargo, existen problemas que requieren etapas con dos o ms opciones o alternativas a elegir en funcin del valor de una condicin o expresin.

UNIDAD ACADMICA PROFESIONAL TIANGUISTENCO UNIVERSIDAD AUTNOMA DEL ESTADO DE MXICO

2.1.2 Estructuras de seleccin.

La sentencia SI (en ingls IF) La sentencia SI tiene dos alternativas. El formato ms sencillo tiene la siguiente sintaxis: SI (Condicin) ENTONCES Accin FINSI La secuencia SI funciona de la siguiente manera. Cuando se alcanza la sentencia SI dentro de un programa, se evala la Condicin entre parntesis que viene a continuacin de SI. Si Condicin es verdadera, se ejecuta Accin (en su formato ms simple, Accin es una sentencia simple, y en los restantes formatos, es una sentencia compuesta). En cualquier caso la ejecucin del programa contina con la siguiente sentencia del programa. Diagrama de flujo de una sentencia bsica SI:

Un segundo formato de la sentencia SI es la sentencia SI-SINO (en ingls IF-ELSE). La ejecucin de esta sentencia consiste en evaluar primero la Condicin. Si sta es verdadera (TRUE), se ejecuta la Accin A. En otro caso, si la Condicin es falsa (FALSE), se ejecuta la Accin B. Siempre se ejecuta alguna accin, o bien A o bien B, pero nunca ambas. SI Condicin ENTONCES Accin A SINO Accin B

UNIDAD ACADMICA PROFESIONAL TIANGUISTENCO UNIVERSIDAD AUTNOMA DEL ESTADO DE MXICO

FINSI En ingls: IF Condicin THEN Accin A ELSE Accin B ENDIF

El diagrama de flujo correspondiente es:

La sentencia SEGUN La sentencia de seleccin mltiple se utiliza para ejecutar distintas sentencias en funcin de los distintos valores que pueda tomar una expresin. El esquema de esta sentencia es: SEGUN Expresin HACER Lista de valores: Accin A Lista de valores: Accin B DE OTRO MODO: Accin por defecto FINSEGUN

UNIDAD ACADMICA PROFESIONAL TIANGUISTENCO UNIVERSIDAD AUTNOMA DEL ESTADO DE MXICO

En ingls: CASE Expresin OF Lista de valores: Accin A Lista de valores: Accin B ELSE Accin por defecto FINCASE

Para ejecutar esta sentencia, se evala primero la expresin. A continuacin, se inspeccionan las distintas listas de valores, hasta encontrar una con un valor que coincida con el resultado de la expresin. La Accin, correspondiente a ese valor, se ejecuta. Si el resultado de la expresin no aparece en ninguna de las listas, se ejecuta la accin por defecto. El siguiente ejemplo muestra el cdigo para un trozo de programa que escribe el nombre del da de la semana almacenado en la variable Dia: SEGUN Dia HACER 1 : ESCRIBE (Lunes); 2 : ESCRIBE (Martes); 3 : ESCRIBE (Miercoles); 4 : ESCRIBE (Jueves); 5 : ESCRIBE (Viernes); 6 : ESCRIBE (Sbado); 7 : ESCRIBE (Domingo); DE OTRO MODO: ESCRIBE (Error: da no vlido); FINSEGUN A cada caso se puede asociar ms de un valor. Esto puede hacerse de tres formas: Separando distintos valores con comas (por ejemplo, 1,2,3) Escribiendo dos valores separados por dos puntos. En este caso se est especificando un rango de valores (por ejemplo, 1..5) Combinando estas dos formas (por ejemplo, 1, 3..4)

UNIDAD ACADMICA PROFESIONAL TIANGUISTENCO UNIVERSIDAD AUTNOMA DEL ESTADO DE MXICO

La siguiente sentencia escribe si el nmero almacenado en la variable Dia corresponde a un da laborable o no: SEGUN Dia HACER 1..5 : ESCRIBE (Laborable); 6 : ESCRIBE (Depende); 7 : ESCRIBE (Festivo); DE OTRO MODO: ESCRIBE (Error: da no vlido) FINSEGUN Algunas reglas relativas a esta sentencia son: La alternativa DE OTRO MODO puede no aparecer, pero si el resultado de la expresin no coincide con ninguno de los casos, el programa acabar con un error. Un mismo valor nunca puede aparecer en distintas alternativas. El tipo de la expresin a evaluar no puede ser FLOTANTE o CADENA. Debe de ser ENTERO, CARACTER, BOOLEANO. Los distintos valores en las alternativas son expresiones constantes (no pueden intervenir variables). El tipo de la expresin y de los distintos valores debe coincidir.

2.1.3 Estructuras de iteracin.

Las estructuras de seleccin, estudiadas en el tema anterior, no son suficientes para describir cualquier algoritmo. Es habitual que ciertas partes de un algoritmo deban repetirse varias veces con objeto de resolver un problema. La repeticin es un concepto importante a la hora de describir algoritmos. Los lenguajes de programacin disponen de una serie de sentencias que

UNIDAD ACADMICA PROFESIONAL TIANGUISTENCO UNIVERSIDAD AUTNOMA DEL ESTADO DE MXICO

permiten repetir varias veces algunos segmentos del programa. A este tipo de sentencias se les denomina sentencias iterativas (o sentencias de repeticin). Bucles (Ciclos) Un bucle es un segmento de algoritmo que se repite varias veces. Podemos distinguir dos tipos de bucles: Bucles deterministas: son aquellos para los cuales el nmero de repeticiones es conocido a priori. Ejemplo: Supongamos que tenemos una computadora que slo es capaz de sumar una unidad a un nmero. Escribir un algoritmo que lea un nmero del teclado, le sume diez y muestre el resultado por pantalla. Un posible algoritmo que utiliza un bucle determinista para resolver este problema es el siguiente: 1. Leer un nmero desde el teclado 2. Repetir 10 veces 2.1. Sumar uno al valor del nmero 3. Escribir el valor del nmero Bucles no deterministas o indeterministas: son aquellos para los cuales no se conoce a priori el nmero de veces que se van a repetir. El bucle se repite hasta que se alcanza cierta condicin. La condicin es conocida a priori, pero no sabemos cuntas veces es necesario repetir el bucle para que la condicin se alcance. Ejemplo: Escribir un algoritmo que lea nmeros desde teclado hasta que se lea un valor cero. El algoritmo debe calcular la suma total de los nmeros ledos y mostrar el resultado por pantalla. Un algoritmo que utiliza un bucle no determinista para resolver este problema es el siguiente: 1. Guardar el valor cero en la variable suma 2. Leer un nmero desde el teclado 3. Mientras que el valor del nmero ledo sea distinto de cero 3.1. Sumar el valor del nmero ledo a la variable suma 3.2. Volver a leer el nmero desde el teclado 4. Escribir el valor de la variable suma

UNIDAD ACADMICA PROFESIONAL TIANGUISTENCO UNIVERSIDAD AUTNOMA DEL ESTADO DE MXICO

En este caso, no sabemos a priori cuntas veces se repetirn los pasos 3.1 y 3.2. Sin embargo, sabemos que dichos pasos dejarn de repetirse en el momento en que se lea un valor cero desde el teclado. Conocemos a priori la condicin pero no el nmero de repeticiones.

La sentencia PARA (en ingls FOR) La sentencia PARA permite repetir, un nmero de veces conocido a priori, una serie de instrucciones. La forma ms simple que toma esta sentencia es la siguiente: Pseudocdigo
Herramienta PSeInt

PARAVariable = Valor_inicial HASTA PARA Variable <- Valor_inicial HASTA Valor_final HACER <a> CON PASO 1 FINPARA Valor_final HACER <a>

PARA Variable = Valor1 HASTA Valor2 HACER Acciones En ingls: FOR Variable = Valor1 TO Valor2 DO Acciones ENDFOR

Las palabras PARA (FOR), HASTA (TO), DO (HACER) y FINPARA (ENDFOR) son palabras reservadas del lenguaje y delimitan cada una de las partes de la sentencia. La variable que aparece a la izquierda del signo de asignacin se llama variable de control del bucle. El valor de esta variable se modifica en cada repeticin del bucle. El conjunto de acciones que aparecen entre las palabras HACER y FIN constituyen el cuerpo del bucle. El significado de la sentencia PARA es el siguiente: se ejecutan las acciones entre las palabras HACER y FIN tantas veces como indique la expresin (Valor2-Valor1+1). La primera vez que se ejecuten estas acciones, el valor de la variable de control es Valor1. La segunda vez que se ejecuten las acciones, el valor de la variable de control es Valor1+1. El valor de la variable de control es incrementado en una unidad tras cada repeticin, de modo que la ltima vez que se ejecuten las acciones el valor de la variable de control es Valor2.

UNIDAD ACADMICA PROFESIONAL TIANGUISTENCO UNIVERSIDAD AUTNOMA DEL ESTADO DE MXICO

El diagrama de flujo que representa la sentencia PARA depende del signo de la expresin constante Paso:

(a)

(b)

Figura 4. (a) Bucle PARA con paso positivo; (b) Bucle PARA con paso negativo.

Ejemplo: El cuerpo del siguiente bucle se ejecuta cero veces, ya que la condicin de salida es cierta la primera vez. PARA i = 1 HASTA 0 HACER Escribe i; FINPARA Ejemplo: El cuerpo del siguiente bucle se ejecuta dos veces (con valores para la variable i de uno y tres) ya que la condicin de salida es cierta la tercera vez. PARA i = 1 HASTA 4 POR 2 HACER ESCRIBE i; FINPARA

UNIDAD ACADMICA PROFESIONAL TIANGUISTENCO UNIVERSIDAD AUTNOMA DEL ESTADO DE MXICO

Ejemplo: El cuerpo del siguiente bucle se ejecuta diez veces (con valores para la variable i entre uno y diez) ya que el valor para la expresin que aparece tras la palabra TO es calculado una nica vez y no se vuelve a calcular tras cada repeticin. Fin = 5; PARA i = 1 HASTA 2*Fin HACER ESCRIBE i; FINPARA Algunas consideraciones sobre la sentencia PARA son las siguientes: El tipo de la variable de control puede ser bsico (excepto REAL y LONGREAL), enumerado o subrango (ver tema sobre tipos definidos por el programador). Ejemplo: El siguiente bucle muestra por pantalla todas las letras maysculas (excepto la letra ee mayscula que est fuera del rango [A..Z] en la tabla ASCII). PARA Letra = A HASTA Z HACER ESCRIBE Letra; FINPARA Los tipos de las expresiones Valor1 y Valor2 deben ser compatibles con el tipo de la variable de control. El tipo de la expresin constante Paso debe ser entero. La variable de control no puede ser: 1) Una componente de una variable estructurada (ver tema sobre arreglos). 2) Una variable annima (ver tema sobre punteros). 3) Una variable importada de otro mdulo (ver tema sobre mdulos). 4) Un parmetro formal (ver tema sobre subprogramas). El programador no debe escribir en el cuerpo del bucle ninguna sentencia que modifique el valor de la variable de control. El valor de la variable de control est indefinido tras la finalizacin del bucle PARA. Ejemplo: No sabemos qu valor se escribe por pantalla tras del siguiente bucle. PARA i = 1 HASTA 10 HACER ... FINPARA; ESCRIBE i;

UNIDAD ACADMICA PROFESIONAL TIANGUISTENCO UNIVERSIDAD AUTNOMA DEL ESTADO DE MXICO

La sentencia MIENTRAS (WHILE) La sentencia MIENTRAS permite repetir, mientras que sea cierta una condicin, una serie de instrucciones. La sentencia MIENTRAS debe utilizarse exclusivamente para expresar bucles indefinidos. La forma que toma esta sentencia es la siguiente: MIENTRAS Condicin HACER Acciones FINMIENTRAS (En ingls) WHILE Condicin DO Acciones ENDWHILE Las palabras MIENTRAS (WHILE), HACER (DO) y FINMIENTRAS (ENDWHILE) son palabras reservadas del lenguaje y delimitan cada una de las partes de la sentencia. La condicin que aparece entre las palabras MIENTRAS y HACER es denominada condicin de permanencia del bucle. La condicin de permanencia debe ser una expresin de tipo booleano. El conjunto de acciones que aparecen entre las palabras HACER y FIN constituyen el cuerpo del bucle. El diagrama de flujo correspondiente a esta sentencia es el siguiente:

Figura 5. La sentencia MIENTRAS (WHILE).

UNIDAD ACADMICA PROFESIONAL TIANGUISTENCO UNIVERSIDAD AUTNOMA DEL ESTADO DE MXICO

Obsrvese que la condicin se vuelve a evaluar, para cada repeticin del bucle, antes de ejecutar el cuerpo. Se permanece dentro del bucle mientras que la condicin sea cierta (es por esto que la condicin se llama de permanencia). Podra ocurrir que el cuerpo del bucle no llegara a ejecutarse, en caso de que la condicin fuese falsa la primera vez que se comprueba. Ejemplo: Escribir un programa que, dado un nmero natural Tope, calcule el mnimo valor de tal que 0 + 1 + 2 + ... + (N - 1) + N >= Tope. Un posible algoritmo para resolver este problema es el siguiente: 1. Leer del teclado el valor de la variable Tope 2. Guardar el valor cero en la variable Suma 3. Guardar el valor cero en la variable 4. Mientras que el valor de la variable Suma sea menor al de la variable Tope 4.1. Sumar uno a la variable 4.2. Sumar a la variable Suma 5. Escribir el valor de la variable

UNIDAD ACADMICA PROFESIONAL TIANGUISTENCO UNIVERSIDAD AUTNOMA DEL ESTADO DE MXICO

La sentencia REPETIR (en ingls REPEAT) La sentencia REPEAT permite repetir una serie de instrucciones hasta que cierta condicin sea cierta. La sentencia REPEAT debe utilizarse exclusivamente para expresar bucles indefinidos. La forma que toma esta sentencia es la siguiente: REPETIR Acciones HASTA Condicin En ingls: REPEAT Acciones UNTIL Condicin Las palabras REPEAT y UNTIL son palabras reservadas del lenguaje y delimitan cada una de las partes de la sentencia. La condicin que aparece tras la palabra UNTIL es denominada condicin de salida del bucle. La condicin de salida debe ser una expresin de tipo booleano. El conjunto de acciones que aparecen entre las palabras REPEAT y UNTIL constituyen el cuerpo del bucle. El diagrama de flujo correspondiente a esta sentencia es el siguiente:

Figura 6. La sentencia REPETIR (REPEAT). Obsrvese que la condicin se vuelve a evaluar, para cada repeticin del bucle, despus de ejecutar el cuerpo. Se sale del bucle una vez que la condicin sea cierta (es por esto que la condicin se llama de salida). El cuerpo del bucle se ejecuta al menos una vez.