Estructuras de Control Lissette Alvarez Abril-Julio, 2004

1

Estructura general de un programa

Un programa puede considerarse como una secuencia de acciones (instrucciones) que manipulan un conjunto de datos para que realice una tarea espec´ıfica. En general, un programa est´a formado por dos bloques: 1. Bloque de declaraciones.

En este bloque se especifican todos los objetos que utilizar´a el programa

(constantes, variables, tablas, registros, archivos, etc.).

Las declaraciones se utilizan en aquellos

lenguajes de programaci´on que no tienen declaraci´on expl´ıcita de los objetos. Su misi´on consiste en indicar al procesador que reserve espacio en la memoria para un objeto del programa, indicando asimismo su nombre, tipo y caracter´ısticas. 2. Bloque de instrucciones. Lo constituye el conjunto de operaciones y la secuencia de instrucciones que se han de realizar para la obtenci´on de los resultados deseados. Dentro de ´este bloque se diferencian tres partes fundamentales: (a) Entrada de datos: conformada por todas las instrucciones que toman datos de un dispositivo externo, almacen´andolos en la memoria central para que puedan ser procesados. (b) Proceso: formado por las instrucciones que modifican/procesan los datos, dejando ´estos disponibles en la memoria central. (c) Salida de resultados: conjunto de instrucciones que toman los datos finales de la memoria central y los env´ıan a los dispositivos externos. A fin de facilitar los c´omputos y la programaci´on, Octave/Matlab tiene declaraci´on expl´ıcita de objetos, siendo posible prescindir del bloque de declaraciones.

En consecuencia, los algoritmos estudiados en este

curso s´olo desarrollar´an el bloque de instrucciones. Las instrucciones pueden ser: 1

1. b´asicas (primitivas). Las instrucciones b´asicas son aquellas que ejecuta el procesador de modo inmediato. Las principales son asignaci´on, entrada y salida: (a) Instrucci´on de asignaci´on: consiste en calcular/indicar el valor de una expresi´on y almacenarlo en una variable1 . (b) Instrucci´on de entrada: toma un dato de un dispositivo de entrada y lo almacena en una variable. (c) Instrucci´on de salida: toma el valor de una expresi´on o variable y lo lleva a un dispositivo externo. 2. de control. Este tipo de instrucciones controlan la ejecuci´on de otras instrucciones. Existen varios tipos: un una condici´on. (a) Selectivas (alternativas): controlan la ejecuci´on de unas u otras instrucciones seg´ (b) Saltos: alteran la secuencia normal de ejecuci´on de un programa u ´nicamente en el caso de cumplimiento de una condici´on asociada a la propia instrucci´on umero finito de veces, una o varias instrucciones. (c) Iterativas: repiten, un n´ 3. compuestas.

Son aquellas que el procesador no puede ejecutar directamente, sino que realiza una

llamada a un subprograma, subrutina o p´arrafo.

1.1

Pseudoc´ odigo

Es un lenguaje de especificaci´on de algoritmos muy parecido a la mayor´ıa de los actuales lenguajes de programaci´on, lo que facilita su traducci´on al lenguaje en s´ı. El pseudoc´odigo utilizar unas pocas palabras clave o palabras especiales que indican la evoluci´on del algoritmo. El pseudoc´odigo tiene algunas ventajas sobre otras t´ecnicas de dise˜ no de algoritmos: • La modificaci´on es muy sencilla si nos equivocamos en la l´ogica del programa • Es independiente del lenguaje de programaci´on que se utilice: un algoritmo escrito en pseudoc´odigo es f´acilmente traducible a muchos lenguajes de programaci´on.

1 Variable:

objeto que almacena valores o datos que pueden cambiar durante la ejecuci´ on del programa.

Ocupa espacio

en memoria, por lo tanto, se localiza en una posici´ on de memoria y tiene asociado un nombre (identificador) que se utiliza en lugar de la posici´ on de memoria.

2

2

Instrucciones B´ asicas

2.1

Inicio y Fin

Delimitan el comienzo y el final de un algoritmo, de la siguiente manera: Inicio .. . ALGORITMO .. . f in Tambi´en, en vez de inicio y fin se puede utilizar ”empezar” y ”fin”, pero siempre quedando clara la intenci´on. En Octave/Matlab las palabras ”inicio” y ”fin” deben ser colocadas a modo de comentarios, para una buena documentaci´on: %Inicio .. . %Fin

2.2

Asignaciones

Cuando se quiere asignar un valor a una variable, la asignaci´on se ajusta al siguiente patr´on: variable ←− valor o expresi´on Ejemplo 2.1. I

←− 3

x ←− 5ˆ(1/2) z

←− y + 1

Observaciones: • La parte izquierda de la asignaci´on siempre es una variable. • Las expresiones representan operaciones que pueden evaluarse. 3

• En Octave/Matlab las asignaciones tienen la misma sintaxis, cambiando el s´ımbolo por =.

Las

asignaciones del ejemplo se implementar´ıan de la siguiente manera:

2.3

I

= 3;

x

= 5ˆ(1/2);

z

= y + 1;

Lectura

Una acci´on de lectura se ajusta al siguiente patr´on: LEER(variable) Ejemplo 2.2. LEER(x) LEER (x, matrizA) Observaciones: • El argumento de la acci´on LEER siempre debe ser una variable. • Se pueden leer varios datos, colocando la lista de variables separadas por comas. • El valor le´ıdo se almacena directamente en la variable que se indica. • La acci´on LEER es otra forma de dar valor a una variable. • La implementaci´on de la instrucci´on LEER en Octave/Matlab depende, b´asicamente, del dispositivo desde donde se leer´a la variable. Si el valor es ingresado por el usuario a trav´es del teclado el comando correspondiente es input: x = input(’ texto ’); Entre las comillas debe escribirse un texto que indique claramente al usuario la informaci´on que debe introducir. Si el valor debe leerse de un archivo en formato ASCII (por ejemplo) se utiliza el comando load con la sintaxis load nombre archivo. En sesiones posteriores estudiaremos este comando m´as a fondo.

4

2.4

Escritura

Una acci´on de escritura se ajusta al siguiente patr´on: ESCRIBIR(variable o expresi´on) Ejemplo 2.3. ESCRIBIR(x) ESCRIBIR(x + y) Observaciones: • El argumento de la acci´on ESCRIBIR puede ser una variable o expresi´on. • Se pueden escribir varias expresiones, se˜ nalando la lista de expresiones separadas por comas. • Los comandos deOctave/Matlab que corresponden a la acci´on ESCRIBIR son, entre otros, disp y fprintf2 . Los ejemplos ser´ıan implementados de la forma: disp(x); fprintf(’El resultado es %1.5d’,x+y); Ejemplo 2.4. Elabore el algoritmo de un programa que convierta grados a radianes. Inicio LEER(grados) radianes ←− grados / 180 ESCRIBIR (radianes) FIN La implementaci´on en Octave/Matlab corresponder´ıa a: % Inicio grados = input(’Introduzca el valor de los grados’); radianes = grados / 180; disp(radianes); % FIN 2 En

la ventana de comandos e Octave/matlab teclee help disp o help fprintf para obtener mayor informaci´ on acerca

de estas instrucciones

5

Problemas Propuestos 2.5. Para los siguientes planteamientos elabore el algoritmo e implemente el programa en Octave/Matlab. 1. Solicite al usuario dos n´ umeros, A y B, y muestre el resultado de elevar A a B. umero introducido por el usuario. 2. Calcule la longitud de la circunferencia que tenga por radio un n´ 3. Intercambie el valor de dos variables num´ericas.* 4. Dada una cantidad en grados, determine el n´ umero de vueltas y el ´angulo correspondiente en el c´ırculo trigonom´etrico. Grados = 390 Vueltas = 1 ´ Angulo = 30 5. Dada una cantidad (v´alida) de d´ıas, determine su equivalente en a˜ nos y meses. Asuma que todos los a˜ nos tienen 365 d´ıas y los meses 30. 6. Dadas las pendientes M1 y M2 y los cortes con el eje Y B1 y B2 de dos rectas L1 y L2 (L1: Y = M 1 ∗ X + B1; L2: Y = M 2 ∗ X + B2), determine en punto de intersecci´on entre las dos rectas. Asuma que M 1 6= M 2. 7. Determinar el ´area de la base y el volumen de un cilindro conocidos su radio y su altura. 8. Calcule el ´area de un tri´angulo en funci´on de las longitudes de sus lados. (Si a, b, c son las longitudes de los lados de un tri´angulo, su ´area viene dada por la expresi´on A= donde p =

p

p (p − a) (p − b) (p − c)

a+b+c . 2

9. Realice la conversi´on de grados Celsius (o C) a grados Fahrenheit (o F ). ¿C´omo ser´ıa el algoritmo que realizase la conversi´on contraria, es decir, de o F a o C?. La f´ormula de conversi´on viene dada por la expresi´on F = 95 C + 32 10. Convertir coordenadas cartesianas en esf´ericas y viceversa.

6

3

Estructuras de Control Las estructuras de control tienen una finalidad bastante definida: se˜ nalar orden en que tienen que sucederse los pasos de un algoritmo. Si un programa muestra un mensaje en la pantalla que pregunta al usuario ”¿Desea seguir adelante?”, obviamente, de la respuesta del usuario depender´a la siguiente acci´on del programa. El programador debe escribir el c´odigo para las dos posibilidades (s´ı y no), aunque cuando el programa est´e funcionando, s´olo se elegir´a una.

3.1

Selectivas Las estructuras selectivas se utilizan para tomar decisiones (por eso tambi´en se llaman estructuras de decisi´on o alternativas). El mecanismo de acci´on eval´ ua una condici´on, y, a continuaci´on, en funci´on del resultado, se lleva a cabo una opci´on u otra.

Es importante asentar esta idea:

el programa est´a dise˜ nado para evaluar una condici´on, y actuar en consecuencia, seg´ un que la condici´on sea verdadera o falsa. 3.1.1

Selecci´ on Simple ”Si ... entonces ...” Se eval´ ua una condici´on y si ´esta resulta verdadera entonces se ejecuta una o varias instrucciones. La sintaxis b´asica es: SI

(condici´on) entonces instrucciones

F IN SI Es importante cerrar el SI (FINSI), ya que, si no se cumple la condici´on, el programa continua en la instrucci´on que sigue a FINSI. umero, de forma que tras leer el n´ umero introducido Ejemplo 3.1. Se desea calcular la ra´ız cuadrada de un n´ por el usuario, es necesario validarlo, -esto es, verificar que cumple las hip´ otesis-. En nuestro caso, hay que verificar que el n´ umero sea no negativo. INICIO LEER ( numero ) SI (numero ≥ 0) entonces

7

ra´ız =

√

numero

FINSI ESCRIBIR (raiz) FIN En Octave/Matlab la instrucci´on que corresponde a las alternativas simples es ”IF (condici´ on) ... 3.1.2

END”. En el caso de Octave tambi´en es v´alida la instrucci´on.”IF (condici´ on) ...

ENDIF”.

Selecci´ on Doble. ”Si... entonces ... sino ...”. Lo m´as frecuente es encontrar situaciones donde si una condici´on se cumple se ejecuta un grupo de instrucciones, pero si no se cumple, deben ejecutarse otras.

La instrucci´on ”Si ...

entonces ... Sino...” facilita este tipo de programaci´on. La estructura que le corresponde es: SI

(condici´on) entonces instrucciones 1

SIN O instrucciones 2 F IN SI Con esta estructura puede mejorarse el algoritmo del ejemplo anterior, se˜ nalando ”error” si el usuario ingresa valores negativos. Ejemplo 3.2. Se desea calcular la ra´ız cuadrada de un n´ umero... INICIO LEER ( numero ) SI (numero ≥ 0) entonces √ ra´ız = numero SINO ESCRIBIR (”Error. ¡Debe ingresar valores positivos!”) FINSI ESCRIBIR (ra´ız) FIN

8

El comando de alternativas dobles para Octave/Matlab ”IF (condici´ on) ...

ELSE ...

END.”. En el caso de Octave tambi´en es v´alida la instrucci´on.”IF (condici´ on) ...

ELSE ...

ENDIF”. 3.1.3

Selecci´ on M´ ultiple Tambi´en hay programas que nos llevan a considerar alternativas con varias opciones posibles. Hay dos formas de escribir esto en pseudoc´odigo. La primera de ellas modifica la estructura de selecci´on doble: SI

(condici´on1) entonces intrucciones 1

SI (condicion2) entonces instrucciones 2 .. . SI (condicion k) entonces instrucciones k F IN SI La instrucci´on ”IF(condicion1) instrucciones 1 ELSEIF(condicion2) instrucciones 2 ... ELSEIF(condicion K) instrucciones k END.’’ corresponde a selecciones multiples en Octave/Matlab.

Nuevamente, el ambiente Octave

podemos intercambiar END por ENDIF. La segunda: OPCION es particularmente u ´til cuando se elabora un men´ u.

La OPCION

toma distintos valores y seg´ un la respuesta del usuario ejecuta las acciones bajo dicha opci´on. LEER (opcion) 9

OPCION (valor 1): intrucciones 1 (valor 2): instrucciones 2 : (valor k): instrucciones k {las acciones que toque} en otro caso instrucciones k + 1 FINOPCION La opci´on ”en otro caso” no es m´as que una alternativa en caso que ell usuario seleccione alguna opci´on no contemplada entre las que se ofrece.

Ejemplo 3.3. El usuario ingresa dos valores y se desea elaborar un menu cuyas opciones sean calcular multiplicaci´ on, division de ambos n´ umeros y salir del programa. Asuma que el segundo n´ umero siempre es distinto de cero. Inicio ESCRIBIR (Ingrese dos numeros: ) LEER (x, y) ESCRIBIR (Menu de opciones.) ESCRIBIR (1. Multiplicacion.) ESCRIBIR (2. Division.) ESCRIBIR (3. Salir del programa.) LEER(opcion) OPCION 1: mult = x ∗ y ESCRIBIR (mult) 2: div = x/y ESCRIBIR (div) 10

3: SALIR en otro caso: ESCRIBIR (Debe escoger una opci´on entre 1 y 3) FIN OPCION En Octave/Matlab la instrucci´on que corresponde a OPCION es SWITCH (expresi´ on) case (valor 1) instrucciones 1 case(valor2) instrucciones 2 : otherwise instrucciones end La implementaci´on del ejemplo anterior ser´ıa: % Inicio x=input(’Por favor ingrese un numero’); y=input(’Ingrese un numero distinto de cero’); disp(’Menu de opciones’); disp(1.

Multiplicaci´ on.);

disp(2.

Division.);

disp(3.

Salir del programa.);

opcion=input(Seleccione una opci´ on’); SWITCH (opci´ on) case 1: mult = x ∗ y; disp (mult) case 2: div = x/y disp (div) case 3:

11

break; otherwise disp(’Seleccione una opci´ on entre 1 y 3’) end

3.2

Repetitivas

Las estructuras repetitivas, que tambi´en reciben el nombre de bucle (loop, en ingl´es) controlan un conjunto de instrucciones que deben repetirse cierto n´ umero de veces, mientras se cumple una condici´on que ha de ser claramente especificada. La condici´on podr´a ser verdadera o falsa, y se comprobar´a en cada paso o iteraci´on del bucle. Todo bucle consta de tres partes b´asicas, a saber: • Decisi´on: donde se eval´ ua la condici´on y, en caso de ser cierta, se ejecuta el cuerpo del bucle. • Cuerpo del bucle: son las instrucciones que se ejecutar´an repetidamente, un n´ umero determinado de veces, cuando la decisi´on es verdadera. • Salida del bucle: es la condici´on que indica cu´ando terminan las iteraciones.

B´asicamente, existen tres tipos de estructuras repetitivas: 1. ”Mientras...” (while), 2. ”Repetir... hasta...” (do... until) 3. ”Desde” (for). Una forma de controlar un bucle es mediante una variable llamada contador cuyo valor se incrementa o decrementa en una cantidad constante en cada repetici´on que se produzca. Tambi´en, los bucles suelen utilizar otro tipo de variables llamadas acumulador, cuya misi´on es almacenar una cantidad variable resultante de operaciones sucesivas y repetidas. Es como un contador, con la diferencia que el incremento/decremento es variable.

12

3.2.1

MIENTRAS (while)

En este tipo de estructura, el cuerpo del bucle se repite MIENTRAS se cumple una determinada condici´on. La sintaxis b´asica es: M IEN T RAS (condici´on - expresi´on l´ogica) hacer instrucciones F IN M IEN T RAS Ejemplo 3.4. Dado un n´ umero entero N calcular la suma de todos los n´ umeros entre 1 y N.. INICIO LEER(N ) I ←− 1; SU M A ←− 0 MIENTRAS (I ≤ N ) SU M A ←− SU M A + I; I ←− I + 1; FINMIENTRAS FIN Frecuentemente se utiliza el bucle while para validar los datos de entrada de un programa. Veamos el siguiente: Ejemplo 3.5. Solicitar al usuario un valor positivo y validarlo. INICIO LEER(x) Contador ←− 0; MIENTRAS (x < 0) hacer LEER(x) Cont ←− Cont + 1 FINMIENTRAS FIN En los ejemplos las la variable I y Cont son contadores y la variable SU M A es un acumulador. ¿Qu´e cree Ud. que pasar´ıa si se omitiera la l´ınea I ←− I + 1 en del cuerpo del bucle? Observaciones: 13

• Ya que primero se comprueba la condici´on y luego se ejecuta el cuerpo del bucle, esta construcci´on implica que el cuerpo del bucle puede realizarse 0, 1 ´o m´as veces. • La estructura correspondiente en Octave/Matlab es: while (condici´ on) instrucciones end

La implementaci´on de ambos ejemplos queda como sigue: Ejemplo 3.4 %Inicio x=input(’Por favor, ingrese el valor de x:

’);

Cont=0; suma=0; while (x HACER instrucciones F IN DESDE

o DESDE

< valor inicio > : < decremento > : < valor f inal > HACER instrucciones F IN DESDE

El incremento es opcional. Si no se coloca, el bucle aumenta de uno en uno -de forma autom´atica- el valor del contador. Si se desea decrementar la variable es necesario colocar el valor del decremento (−1). Retomando el ejemplo 3.4: INICIO LEER(N ) SU M A ←− 0 DESDE I = 1 : N SU M A ←− SU M A + I; FINDESDE FIN Observaciones: • El contador siempre se inicializa -autom´aticamente- en el valor inicial indicado en la estructura. • El comando de Octave/Matlab para esta estructura es: for contador = inicio :

espaciado :

instrucciones end

15

fin

El programa en Octave/Matlab para el ejemplo es: %Inicio N=input(’Por favor, ingrese un valor para N: ’); suma=0; for i=1:N suma = suma + i; end3 IMPORTANTE: Las estructuras no utilizan ”;” al final de la l´ınea!!!

3.3

Saltos

Otro tipo de instrucciones nos permiten salir de un bucle en ejecuci´on o ir al ciclo siguiente sin terminar el actual. La instrucci´on break detiene la ejecuci´on de un bucle while y for. Debe escribirse -´ unicamente- en el cuerpo del bucle. Octave/Matlab ejecuta la instrucci´on que se encuentra inmediatamente despu´es del bucle y continua el programa. La instrucci´on continue salta las instrucciones siguientes del bucle -en un paso k, digamos-y continua con la siguiente iteraci´on -paso k+1 del bucle-. Debe escribirse en el cuerpo del bucle y se utiliza s´olo en estructuras iterativas.

3 En

Octave pueden utilizarse, alternativamente, las palabras endfor, endif y endwhile para cerrar los ciclos for, if y while

respectivamente.

16

4

Bucles Anidados

Es posible construir un programa donde se aniden los bucles; esto es, ejecutar un bucle dentro de otro, siempre que el bucle interno est´e totalmente contenido dentro del bucle externo, si no, el algoritmo no es v´alido. El caso t´ıpico de bucle anidado es la asignaci´on de valores a una matriz. Supongamos que se desea leer los valores de una matriz de orden mxn. (m y n dados por el usuario). El pseudoc´odigo que resuelve el planteamiento es: INICIO HACER LEER(m, n) HASTA QUE ((m > 0) & (n > 0)) DESDE i = 1 : m HACER DESDE j = 1 : n HACER LEER A(i, j) FINDESDE -jFINDESDE -iFIN Y la implementaci´on correspondiente: %Inicio do m=input(’Por favor introduzca el n´ umero de filas: n=input(’y el n´ umero de columnas:

’);

until ((m > 0) & (n > 0)) disp(’Introduzca los valores por filas.’); for i = 1 : m for j = 1 : n A(i,j)=input( ’’); end end %Fin

17

’);

5

Problemas propuestos

Para los siguientes planteamientos elabore el algoritmo el implemente el programa en Octave/Matlab. umeros introducidos por teclado es mayor que un tercer n´ umero, tambi´en 1. Indique si la suma de dos n´ introducido por teclado. 2. Calcule las ra´ıces de un polinomio de segundo grado. 3. Redondee un n´ umero al n´ umero entero m´as cercano. 4. Dados n numeros cuente la cantidad de numeros positivos, negativos y cero. 5. Escribir un programa que, tras pedir al usuario un n´ umero, le informe de si es par, impar o no entero. 6. Dados tres n´ umeros reales determine el mayor y el menor de ellos. 7. Dados dos n´ umeros reales, A y B, determine (sin realizar la operaci´on aritm´etica) el signo de la suma, el producto y la resta de A+-*B. 8. Determine si un a˜ no es o no bisiesto. Son bisiestos los a˜ nos que sean m´ ultiplos de 4, salvo los que finalizan en 00, que s´olo lo ser´an cuando tambi´en sean m´ ultiplos de 400. 9. Determine al valor absoluto de un n´ umero ingresado por el usuario. umeros reales LS y LI que representan los l´ımites superior e inferior de un intervalo, respecti10. Dos n´ vamente. Dado un n´ umero n determine si dicho n´ umero pertenece al intervalo. En caso contrario, indique si est´a a la derecha o izquierda del intervalo. 11. Pedir un n´ umero al usuario y mostrar su tabla de multiplicar del 1 al 10. 12. Mostrar los mil primeros n´ umeros pares. (utilizando while y for) 13. Escribir un programa que calcule las N primeras fracciones del tipo 1i , i = 1, 2, ..., N , tras pedir N al usuario. umeros enteros, hasta que el cuadrado sea 14. Escribir un programa que calcule los cuadrados de los n´ mayor o igual que 2100. 15. Eval´ ue las siguientes expresiones, donde i y n son dados por el usuario: (a)

n P 1 i=1

i

18

(b) (c)

n √ P i=1 n P i=1

µ (d)

3x2 −2x+8 x2 −16

n P

i=1

(e) (f) (g) (h)

x2 − 4

¶ 1 n+i

µ

n P

log

i=1 n P i=1 n P i=1 n Q

− log (n) ³ ´i ¶ i+1 i−1

2i+1 −2i i+1

(−1)

i+1 1 2i

n (n + 1)

i=1

16. Calcule el factorial de un n´ umero. umeros, escriba su multiplicaci´on y luego pregunte si quiere repetir el proceso. 17. Dados dos n´ 18. Lea un vector de orden n y calcule su norma eucl´ıdea. La norma eucl´ıdea de un vector x = (x1 , x2 , ...xn ) viene dada por la f´ormula

q 2 2 2 (x1 ) + (x2 ) + · · · + (xn )

19. Convertir un n´ umero entero dado en base 10 a base binaria. 20. Calcule los n primeros n´ umeros de la serie Fibonacci. La serie de Fibonacci se genera de la siguiente manera: F0

=

1

F1

= 1

Fn

=

Fn−1 + Fn−2 ; n ≥ 2

21. Para una matriz A, cuadrada, de 10 x 10 elementos, muestre los siguientes resultados: umero de elementos distintos de cero. (a) N´ (b) La suma de los elementos situados encima de la diagonal principal, es decir, los elementos A(i, j) tales que i < j. (c) El producto de los elementos de la diagonal principal (A(1, 1) ∗ A(2, 2) ∗ · · · A(10, 10)). 22. Dada una secuencia de N n´ umeros enteros determine: 19

(a) Cantidad de n´ umeros positivos (b) Suma de los n´ umeros positivos (c) Promedio de los n´ umeros positivos (d) Cantidad de n´ umeros negativos (e) Suma de los n´ umeros negativos (f) Promedio de n´ umeros negativos 23. Dado un n´ umero indique si es o no primo. 24. Dada una matriz de orden mxn determine (a) Suma de los elementos de cada fila. (b) Suma de los elementos de cada columna. 25. Se dice que un vector v = (v1 , v2 , ..., vn ) es una mochila perfecta si cada elemento del vector es mayor que la suma de todos los anteriores. Lea un vector de orden n e indique si es o no una mochila perfecta.

20