10. Estructura de control iterativa
Objetivos
- Entender el concepto de estructura iterativa (bucle).
- Tener claro el «patrón» o esquema de un bucle.
- Comprender el flujo de ejecución de un programa con estructuras iterativas.
- Saber reflexionar sobre la condición de final de un bucle.
- Aprender a construir una estructura de control iterativa.
- Conocer las diferentes variantes de la estructura iterativa: while y for.
- Saber resolver problemas sencillos utilizando estructuras iterativas.
- Saber resolver problemas sencillos combinando los tres tipos de estructuras: secuencial, alternativa e iterativa.
- Aplicar la estructura iterativa al recorrido de una secuencia.
Introducción
En esta unidad se presentan las estructuras de control de flujo iterativas que se añaden a las estructuras de control secuencial y alternativa que ya conocemos para controlar dinámicamente la ejecución de un programa. Es lo que es conoce también como bucle o loop. Veremos que con esta estructura, un programa puede ejecutar repetidamente un bloque de instrucciones siempre que se cumpla una determinada condición.
1. Estructura (o composición) iterativa: aproximación intuitiva
Con las estructuras que ya conocemos podemos resolver diversos problemas, pero no otros, para los que necesitamos la estructura iterativa. La estructura iterativa está muy presente en la vida cotidiana. Fijaos en la siguiente instrucción de una receta de cocina: Mientras la salsa no esté suficiente ligada, remover a fuego lento. O en este otro pensamiento: Voy en bici mientras tenga ganas. Se trata, pues, de repetir una misma acción mientras se cumpla una determinada condición. No en vano, el verbo iterar es sinónimo del verbo repetir.
En el diagrama de flujo siguiente se presentan las partes de una estructura iterativa. Las flechas indican el sentido del flujo de ejecución.
En primer lugar se hace la consulta sobre el estado actual o condición (rombo verde) y según el valor resultado de la evaluación (cierto o falso) hay dos posibles caminos a seguir: si la evaluación da cierto se ejecuta el bloque de instrucciones (rectángulo amarillo) y se vuelve a evaluar la condición. Si no, si el resultado es falso, el flujo de ejecución continúa teniendo un solo camino (rombo azul de fin) y se acaba la iteración.
El primer paso es consultar el estado actual o condición. Aquí se evalúa una expresión lógica que da como resultado un valor booleano (verdadero o falso). Según el resultado, o bien se ejecutarán las instrucciones del bucle (cuando el resultado es verdadero) y se volverá al punto de evaluación de la condición, o bien, cuando el resultado es falso, se continuará con la ejecución del resto del programa y se acabará la iteración.
Veamos a continuación algunos ejemplos de uso de la estructura iterativa. Para ilustrar cómo funciona el flujo de ejecución se presenta un diagrama para cada ejemplo.
1.1. Ejemplo 10_01 - Receta de cocina
Para la receta de cocina anterior Mientras la salsa no esté suficiente ligada, remover a fuego lento, si identificamos las partes de la estructura alternativa obtenemos el siguiente diagrama de flujo de ejecución:
Por lo tanto, estaremos removiendo la salsa a fuego lento mientras no esté ligada. Fijaos en que en este ejemplo la condición del mientras está formulada en negativo Mientras no esté ligada...
1.2. Ejemplo 10_02 - Ir en Bici
Si representamos el pensamiento anterior Voy en bici mientras tenga ganas, obtenemos el siguiente diagrama de flujo:
1.3. Ejemplo 10_03 - Pared
Pensemos ahora en el caso de un albañil que va subiendo una pared de ladrillos. Debe ir añadiendo filas de ladrillos hasta que la pared llegue al techo. El proceso sigue el siguiente diagrama de flujo:
2. Codificación estructura iterativa
En este apartado presentamos la codificación de una estructura de control iterativa, en este caso la estructura while que es la más general. Veremos después que admite otras variantes.
| Partes | Codificación en lenguaje algorítmico |
|---|---|
| Consulta sobre el estado actual o condición | while expresión condicional do |
| Qué hacer cuando la condición es Cierta | bloque de instrucciones |
| Marca de fin de estructura iterativa | end while |
2.1. Ejemplo 10_04 - Pared
A continuación tenéis codificado un primer algoritmo tanto en lenguaje algorítmico como en C. Imaginemos que tenemos un robot automático capaz de construir paredes. Supondremos implementada la acción buildWall() que se encarga de hacer la operación necesaria para añadir una fila de ladrillos encima de la pared respectivamente.
algorithm wall
var
hightWall: real;
hightCealing: real;
end var
hightWall:= readReal();
hightCealing:= readReal();
while hightWall < hightCealing do
buildWall();
hightWall:= readReal();
end while
end algorithm
int main(int argc, char** argv) {
float hightWall, hightCealing;
scanf("%f", &hightWall);
scanf("%f", &hightCealing);
while (hightWall < hightCealing) {
buildWall();
scanf("%f", &hightWall);
}
return 0;
}
Analicemos la ejecución de la estructura iterativa:
| # Línea | Código |
|---|---|
| 1 | while hightWall < hightCealing do |
| 2 | bildWall(); |
| 3 | hightWall:= readReal(); |
| 4 | end while |
La línea 1 evalúa la condición:
Caso cierto: si la altura de la pared es inferior a la del techo, entonces la expresión es cierta y se ejecutará la línea 2 de código. Es decir, el robot subirá la pared añadiendo una fila de ladrillos nueva. Una vez ejecutada la acción de la línea 2, el control del programa pasa a la línea 3 del código y se obtiene la nueva altura tras lo cual vuelve de nuevo a la línea 1 (bucle). Fijaos en que la función buildWall() está modificando la altura de la pared y, por tanto, cuando volvamos a ejecutar la línea 1, la altura de la pared ya será diferente.
Caso falso: en caso de que la condición no sea cierta (por tanto, la pared ya toca al techo), el resultado de la expresión es falso y no se ejecutará la línea 2 sino que pasaremos directamente a la línea 4.
2.2. Ejemplo 10_05 - Multiplicación
A continuación tenéis codificado un algoritmo tanto en lenguaje algorítmico como en lenguaje C pera multiplicar dos números enteros cualesquiera (n*m) sin utilizar el operador de multiplicación *. Este es un ejemplo clásico para entender el uso de la estructura iterativa. Si no disponemos del operador * podemos hacer igualmente la multiplicación de dos enteros a partir de la suma. Por eso habrá que sumar m veces un número n. Ex. 2*5= 2+2+2+2+2, sumar cinco veces el número 2.
algorithm multiplicacionEnteros
var
n: integer;
m: integer;
x: integer;
end var
n:= readInteger();
m:= readInteger();
x:=0;
while m ≠ 0 do
x:=x+n;
m:=m-1;
end while
writeInteger(x);
end algorithm
int main(int argc, char** argv) {
int n, m, x;
scanf("%d", &n);
scanf("%d", &m);
x = 0;
while ( m != 0 ) {
x = x + n; // Equivalence in C language: x += n;
m = m - 1; // Equivalence in C language: m--;
}
printf("%d", x);
return 0;
}
En este ejemplo, nos hace falta una variable auxiliar x donde iremos guardando los resultados parciales. Deberemos inicializarla a 0.
2.3. Ejemplo 10_06 - Factorial
En este caso, diseñaremos un algoritmo para resolver un problema matemático, el cálculo del factorial de un número entero positivo. El factorial de un número se calcula así:
factorial(0) = 1 y
factorial(n) = n * factorial(n-1).
Para hacer el cálculo hay que multiplicar todos los números entre 1 y el número del cual queremos calcular el factorial.
algorithm factorial
var
n: integer;
i: integer;
fact: integer;
end var
n:= readInteger();
i:=1:
fact:=1;
while i ≤ n do
fact:=fact*i;
i:=i+1;
end while
writeInteger(fact);
end algorithm
int main(int argc, char** argv) {
int n, i, fact;
scanf("%d", &n);
i = 1;
fact = 1;
while ( i <= n ) {
fact = fact * i;
i = i + 1;
}
printf("%d", fact);
return 0;
}
| # Línea | Código |
|---|---|
| 1 | while i ≤ n do |
| 2 | fact:=fact*i; |
| 3 | i:=i+1; |
| 4 | end while |
Analizando la ejecución de la estructura iterativa, observad que cada vez que se ejecuta la línea 1 el valor de la variable i es diferente. Si ni los valores de i ni los de n se modificaran dentro del bucle, no podríamos salir nunca de la composición.
2.4. La condición de final del bucle
Un aspecto sobre el que hay que poner mucha atención cuando utilizamos estructuras iterativas es asegurarnos que el bucle acabará en algún momento. Si no lo hacemos bien, podría pasar que el bucle fuera infinito y el algoritmo no acabase nunca. Por lo tanto, asegurémonos siempre de que esto no pasará. Hay métodos formales para asegurar que la construcción está bien definida y que el bucle siempre acaba, pero no los estudiaremos aún. De todas maneras, intuitivamente también podemos deducir que el bucle acabará en algún momento. Veámoslo en algunos de los ejemplos que hemos trabajado anteriormente.
Recordemos el algoritmo para calcular el factorial de un número entero positivo.
algorithm factorial
var
n: integer;
i: integer;
fact: integer;
end var
n:= readInteger();
i:=1:
fact:=1;
while i ≤ n do
fact:= fact*i;
i:= i+1;
end while
writeInteger(fact);
end algorithm
int main(int argc, char** argv) {
int n, i, fact;
scanf("%d", &n);
i = 1;
fact = 1;
while ( i <= n ) {
fact = fact * i;
i = i + 1;
}
printf("%d", fact);
return 0;
}
| # Línea | Código |
|---|---|
| 1 | i:=1: |
| 2 | fact:=1; |
| 3 | while i<=n do |
| 4 | fact:=fact*i; |
| 5 | i:=i+1; |
| 6 | end while |
Observando la ejecución del algoritmo vemos que:
- Las instrucciones de dentro del bucle (líneas 4 y 5) se ejecutaran al menos una vez a menos que el número al que se deba calcular el factorial sea 0.
- En cada iteración, es decir, cada vez que entremos dentro del cuerpo del bucle (líneas 4 y 5), la variable i se incrementa en una unidad. Por tanto, cada vez que se ejecuta la línea 3, donde se evalúa la condición, el valor de la variable i es diferente. Concretamente, vale una unidad más. De esta manera, va aumentando su valor desde 1 hasta llegar al valor n. Por lo tanto, el bucle acabará en algún momento, cuando la expresión (i<=n) deje de ser cierta. Esto es, cuando la variable i contenga un valor superior al número n.
Pero, ¿qué pasaría si hubiéramos olvidado incrementar el valor de la variable i dentro del cuerpo del bucle?
| # Línea | Código |
|---|---|
| 1 | i:=1: |
| 2 | fact:=1; |
| 3 | while i<=n do |
| 4 | fact:=fact*i; |
| 5 | end while |
La variable i siempre valdría 1 así que el bucle sería infinito, no acabaría nunca a menos que el valor de la variable n fuera también 1. Vaya, que el algoritmo solo funcionaría en el caso del cálculo del factorial del número 0. Para el resto de números positivos no funcionaría. El programa se quedaría bloqueado en un bucle sin fin. Digamos que se «colgaría» porque no hemos controlado bien el fin del bucle y nos veríamos inmersos en infinitas iteraciones.
Aseguraos pues siempre que en cada iteración (vuelta) del bucle queden menos iteraciones por hacer.
3. Variante de la estructura iterativa
3.1. La construcción while
La construcción while que acabamos de ver, permite expresar cualquier composición de instrucciones que haya que repetir de acuerdo a unas condiciones determinadas. Es, pues, la construcción iterativa más general. Algunos lenguajes, sin embargo, incluyen otras construcciones iterativas que son variantes de la misma y que solo se pueden aplicar a casos muy concretos, siempre que se den determinadas circunstancias. En este apartado veremos también la construcción for.
Recordad que la estructura del while es la siguiente:
| Partes | Codificación en lenguaje algorítmico |
|---|---|
| Consulta sobre el estado actual o condición. | while expresión condicional do |
| Qué hacer cuando la condición es cierta. | bloque de instrucciones |
| Marca de fin de estructura iterativa. | end while |
3.2. La construcción for
La variante for se utiliza cuando hay que repetir un bloque de instrucciones un número conocido de veces. Por ejemplo, en el caso del factorial que hemos visto anteriormente, sabemos que tenemos que repetir un mismo cálculo (fact * i) un número determinado de veces, en este caso desde 1 hasta el número del que queremos calcular el factorial. Si utilizamos la instrucción for la estructura iterativa se simplifica.
[Ejemplo 10_07]
algorithm factorial2
var
n: integer;
i: integer;
fact: integer;
end var
n := readInteger();
fact:=1;
for i:=1 to n do
fact:= fact*i;
end for
writeInteger(fact);
end algorithm
int main(int argc, char** argv) {
int n, i, fact;
scanf("%d", &n);
fact = 1;
for ( i = 1; i <= n; i++ ) {
fact = fact * i;
}
printf("%d", fact);
return 0;
}
| # Línea | Código |
|---|---|
| 1 | for i:=1 to n do |
| 2 | fact:=fact*i; |
| 4 | end for |
Si os fijáis, en el caso de la estructura iterativa for, las líneas de código que hay dentro del bucle son menos. En este caso, solo una, la línea 2. Esto es así porque la estructura for ya se encarga de ir incrementando el valor del índice de la primera línea (en este caso la i desde el valor inicial que se indica en la misma estructura for (1) hasta el valor final (n), que también se indica en la misma línea. Obsérvese también que en este caso, no hay que iniciar antes de la estructura iterativa, la variable i. Por tanto, nos hemos ahorrado dos líneas de código en relación a la resolución del mismo problema con la estructura while.
El esquema de la estructura de control for es, pues, la siguiente:
| Partes | Codificación en lenguaje algorítmico |
|---|---|
| Inicialización de la variable de control e indicación del número de veces que hay que repetir la iteración. | for índice:= valor inicial to valor final do |
| Qué hacer. | bloque de instrucciones |
| Marca de fin de la estructura iterativa. | end for |
Tened en cuenta que, en este caso, la estructura for ya se encarga de ir incrementando el valor del índice en cada iteración.
El C tiene una sintaxis de la composición iterativa for idéntica. Dentro del paréntesis tenemos tres partes separadas por ‘;’ (punto y coma). Cada una de las partes desempeña un papel en la composición.
/* loop body */
}
- expression1: es la parte de inicialización. En este primer segmento asignamos el valor inicial a la variable contador (i = 1).
- expression2: contiene el test de continuidad. Si la evaluación de la expresión 2 es cierta se pasará a ejecutar el cuerpo del bucle. Si resulta falsa se continuará la ejecución con la instrucción inmediatamente posterior al cuerpo de la composición.
- expression3: es la parte de actualización del contador. La expression3 se evaluará cuando se acabe de ejecutar el cuerpo del bucle y antes de pasar a evaluar el test. En esta parte se encuentra la instrucción que modifica la variable contador (i++).
Así pues, siempre que conozcamos el número de iteraciones que habrá que hacer, será más cómodo utilizar la construcción for en lugar de la construcción while, ya que nos ahorramos tener que inicializar la variable índice y también tener que ir incrementando cada iteración. Pero recordad que ¡no todas las iteraciones se pueden representar con una estructura for!
3.2.1. Modificadores de la composición
La forma que hemos visto de la composición iterativa for (que en cada vuelta se incrementa el contador en una unidad) es la más habitual. Pero no responde a todos los planteamientos con los que nos podemos encontrar.
- Queremos simular una cuenta atrás desde un valor determinado hasta 0.
- Queremos hacer la suma de todos los números pares entre dos números entrados.
Está claro que ambos problemas los resolveríamos con algún tipo de composición iterativa pero, a pesar de saber la cantidad de vueltas a realizar, la composición for original no nos es útil para diferentes problemas.
- Si hacemos una cuenta atrás, nos interesaría ir bajando el valor del contador y no subirlo.
- Si queremos sumar pares, iría bien poder incrementar el contador de dos en dos unidades.
La composición for dispone de variantes que facilitan el trabajo.
)))
3.3. Ejemplos
3.3.1. Ejemplo 10_08 - Cuenta atrás
algorithm countDown
var
n: integer;
k: integer;
end var
n := readInteger();
for k:=n to 0 do step -1
writeInteger(k);
end for
end algorithm
int main(int argc, char** argv) {
int n, k;
scanf("%d", &n);
for ( k = n; k > 0; k-- ) {
printf("%d", k);
}
return 0;
}
3.3.2. Ejemplo 10_09 - Sumador de pares
Queremos sumar los números pares comprendidos entre dos números n y m que cumplen que n <= m.
algorithm evenAdd
var
n: integer;
m: integer;
k: integer;
sum: integer;
end var
n := readInteger();
m := readInteger();
if (n mod 2 ≠ 0)
n := n + 1;
end if
sum:= 0;
for k:=n to m do step 2
sum := sum + k;
end for
writeInteger(sum);
end algorithm
int main(int argc, char** argv) {
int n, m, k, sum;
scanf("%d %d", &n, &m);
sum = 0;
if (n % 2 > 0) {
n++;
}
for ( k = n; k <= m; k += 2 ) {
sum = sum + k;
}
printf ("%d", sum);
return 0;
}
3.3.3. Ejemplo 10_10 - Temperatura Media
En la unidad anterior hemos visto la estructura de datos tipo vector. Utilizando esta estructura, escribimos el algoritmo para calcular la temperatura media de una semana:
algorithm meanTemp
var
t: vector[7] of real;
m: real;
end var
t[1]:=readReal();
t[2]:=readReal();
t[3]:=readReal();
t[4]:=readReal();
t[5]:=readReal();
t[6]:=readReal();
t[7]:=readReal();
m:=(t[1] + t[2] + t[3] + t[4] + t[5] + t[6] + t[7]) /7.0;
writeReal(m);
end algorithm
Ahora que conocemos la estructura iterativa while y, aprovechando que el algoritmo repite un conjunto de instrucciones, lo podemos simplificar de la siguiente manera:
algorithm meanTemp
var
t: vector[7] of real;
m: real;
i: integer;
end var
i:=1;
m:=0;
while i ≤ 7 do
t[i]:= readReal();
m:= m+t[i];
i:= i+1;
end while
writeReal(m/7);
end algorithm
int main(int argc, char** argv) {
float t[7];
float m;
int i;
i = 0; // the base index of array is 0 in C language
m = 0;
while ( i < 7 ) { // "<=" is changed by "<" because in C language last element of a N-size array is N-1
scanf("%f", &t[i]);
m = m + t[i];
i = i + 1;
}
printf("%f", m / 7);
return 0;
}
De esta manera, la instrucción para leer la temperatura solo hay que escribirla una vez. Pero, ¿qué pasaría si ahora quisiéramos calcular la temperatura de todo el año? Se debería definir un vector con capacidad para 365 elementos i. El algoritmo prácticamente sería el mismo:
[Ejemplo 10_11]
algorithm meanTemp
var
t: vector[365] of real;
m: real;
i: integer;
end var
i:=1;
m:=0;
while i ≤ 365 do
t[i]:= readReal();
m:= m+t[i];
i:= i+1;
end while
writeReal(m/365);
end algorithm
int main(int argc, char** argv) {
float t[365];
float m;
int i;
i = 0;
m = 0;
while ( i < 365 ) {
scanf("%f", &t[i]);
m = m + t[i];
i = i + 1;
}
printf("%f", m / 365);
return 0;
}
Una mejor opción sería utilizar la estructura for, aprovechando que sabemos cuántos elementos del vector es necesario recorrer. Además, declarando la constante days se puede adaptar el programa con más facilidad. Veámoslo:
[Ejemplo 10_12]
algorithm meanTemp
const
DAYS: integer = 365;
end const
var
t: vector[DAYS] of real;
m: real;
end var
m:=0;
for i:=1 to DAYS do
t[i]:= readReal();
m:= m+t[i];
end for
writeReal(m/DAYS);
end algorithm
#define DAYS 365
int main(int argc, char** argv) {
float t[DAYS];
float m;
int i;
m = 0;
for ( i = 0; i < DAYS; i++ ) {
scanf("%f", &t[i]);
m = m + t[i];
}
printf("%f", m / DAYS);
return 0;
}
Veamos, pues, que la estructura for es muy útil para recorrer los elementos de un vector. Retomaremos este concepto de recorrido más adelante, en una unidad posterior, cuando hablamos de los esquemas algorítmicos de recorrido y de búsqueda.
3.3.4. Ejemplo 10_13 - Ha helado
Para acabar, imaginemos ahora la siguiente situación. Disponemos de un registro de las temperaturas de todo el año, que tenemos almacenadas en un vector, de la misma manera que hemos hecho en el ejemplo anterior. Ahora queremos descubrir si algún día ha helado. Esto equivale a ir comprobando si alguna de les temperaturas es negativa.
algorithm hasFrozen?
var
t: vector[365] of real;
frozen: boolean;
i: integer;
end var
i:=1;
frozen:= false;
while i ≤ 365 and frozen = false do
t[i]:= readReal();
if t[i] ≤ 0 then
frozen := true;
end if
i:= i+1;
end while
writeBoolean(frozen);
end algorithm
typedef enum {FALSE, TRUE} boolean;
int main(int argc, char** argv) {
float t[365];
boolean frozen;
int i;
i = 0;
frozen = FALSE;
while ( i < 365 && frozen == FALSE ) {
scanf("%f", &t[i]);
if ( t[i] < 0 )
frozen = TRUE;
i = i + 1;
}
printf("%d", frozen); // Equivalence in C language: 0 == FALSE, 1 == TRUE
return 0;
}
Fijaos en que cuando encontramos el primer caso de temperatura negativa, ya podemos acabar; no es necesario que sigamos revisando más temperaturas. Solo queremos saber si algún día ha helado, no cuántos o qué días ha helado.
Si quisiéramos saber cuántos días ha helado, entonces tendríamos que revisar todos los elementos del vector y en este caso sería más adecuada una estructura for. Veámoslo:
3.3.5. Ejemplo 10_14 - Cuenta de días
algorithm howManyDaysHasFrozen?
var
t: vector[365] of real;
numDays: integer;
end var
numDays:= 0;
for i:= 1 to 365 do
t[i]:= readReal();
if t[i] ≤ 0 then
numDays:= numDays+1;
end if
end for
writeInteger(numDays);
end algorithm
int main(int argc, char** argv) {
float t[365];
int i, numDays;
numDays = 0;
for ( i = 0; i < 365; i++ ) {
scanf("%f", &t[i]);
if ( t[i] < 0 )
numDays = numDays + 1;
}
printf("%d", numDays);
return 0;
}
Observad que en este ejemplo hemos utilizado la estructura iterativa for y, dentro del cuerpo, la estructura alternativa.
Una vez presentada la estructura de control iterativa, conocemos ya todas las estructuras de control de flujo de la ejecución de un código: secuencial (una instrucción a continuación de otra), alternativa e iterativa. Por tanto, a partir de ahora, utilizando combinaciones de estas tres estructuras de control podemos resolver cualquier problema.
Resumen
En esta unidad hemos definido la estructura iterativa con sus variantes principales. Este tipo de estructura es fundamental para controlar el flujo de ejecución de un programa y completa las estructuras de control de flujo necesarias para resolver cualquier problema y que son tres: secuencial, alternativa e iterativa.
Hemos utilizado el grafismo de los diagramas de flujo para mostrar el funcionamiento de esta estructura de control y hemos dado énfasis en la importancia de asegurar la condición de final el bucle para garantizar que el programa funcionará bien.
Hemos visto diversos ejemplos de estructura alternativa junto con su traducción al lenguaje algorítmico y al lenguaje C considerando diversas posibilidades variantes, desde la construcción while, de uso general, hasta la construcción for, que se puede utilizar en los casos en que conozcamos de entrada el número de iteraciones a hacer.
Finalmente hemos visto algunos ejemplos de uso combinado de las tres estructuras de control de flujo (secuencial, alternativa e iterativa) y de tipos de datos estructurados, como es el caso de los vectores.