PDF de programación - PROGRAMACIÓN (PRG) - Tema 4 - LA ITERACIÓN

PROGRAMACI ÓN

Escuela Universitaria de Informática - Curso 2001-2002

Tema 4. LA ITERACI ÓN

Isabel Galiano, Francisco Marqués y Natividad Prieto

Índice General

1 La iteración como estrategia: sus fases

. . . . . . . . . . . .
1.1 Descubriendo la estructura iterativa del problema.
. . . . . . . . . . . . . . . . . . .
1.2 Eligiendo las variables de la iteración.
1.3 Valores iniciales.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4 Transformando el Criterio de Repetición de la iteración en una condición
Java. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5 Transformando el Cuerpo de la iteración en un bloque Java. . . . . . . .
1.6 Conclusiones.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 La instrucción de repetición while

2.1 Esquema Iterativo para el bucle while. . . . . . . . . . . . . . . . . . . .
2.2 Ejemplos de utilización de la instrucción while
. . . . . . . . . . . . . .

3 La instrucción de repetición for

. . . . . . . . . . . . . . . . . . . .
3.1 Bucles de conteo: la alternativa for.
3.2 Ejemplos de utilización de la instrucción for.
. . . . . . . . . . . . . . .
3.3 Sintaxis de la instrucción for. . . . . . . . . . . . . . . . . . . . . . . . .

4 La instrucción do ...while

5 Introducción al coste: conteo de instrucciones

5.1 El coste temporal de los programas.
. . . . . . . . . . . . . . . . . . . .
5.2 La complejidad temporal definida por conteo de pasos. . . . . . . . . . .
5.3 El coste como una función de la talla del problema. . . . . . . . . . . . .
5.4 Comparación de los costes de los algoritmos . . . . . . . . . . . . . . . .

6 Ejercicios

2
3
4
5

5
6
7

8
8
9

12
12
16
17

18

19
20
21
21
22

23

1

1 LA ITERACI ÓN COMO ESTRATEGIA: SUS FASES

2

1 La iteración como estrategia: sus fases

El factor común de los programas escritos hasta el momento es que sólo hacen lo que
hacen una única vez; el programa adivinanza sólo permite adivinar un número; el
programa ValidarFecha sólo permite validar una fecha; el programa intercambio sólo
permite intercambiar una única vez el valor de dos variables.

Ahora bien, solucionado un problema una vez, código correspondiente incluido, sería
deseable poder reutilizar dicha solución muchas más, tantas como fuera necesario; ¿por
qué no poder jugar a adivinar un número hasta que nos cansemos o ValidarFecha tantas
fechas como sea necesario? Evidentemente, la respuesta no es repetir la ejecución de
adivinar hasta que nos cansemos o ValidarFecha tantas veces como sea necesario.

Para poder repetir de forma controlada una instrucción o un bloque de instrucciones
de un programa, esto es para poder iterar, cualquier lenguaje de programación propor-
ciona al menos una instrucción iterativa o bucle. Por su naturaleza, las partes principales
de un bucle -o de la iteración que representa- son dos :

• Cuerpo: instrucción o bloque de instrucciones que se repiten;
• Criterio de Repetición: condición que controla la ejecución de una nueva repeti-

ción.

El tipo de bucle que ejemplifica con mayor claridad la función iterativa es el llamado

bucle ”while”. En Java, su forma general es:

while (CriteriodeRepetición) Cuerpo

Nótese que CriteriodeRepetición y Cuerpo son las mismas construcciones que

están presentes en la instrucción if que se estudió en el tema precedente.

La ejecución de la instrucción while procede como sigue:

1. se evalúa la condición CriteriodeRepetición;

2. si CriteriodeRepetición == false, el bucle termina;

3. si CriteriodeRepetición == true, el Cuerpo del bucle se ejecuta o, dicho de
otra forma, se entra en el bucle; tras la ejecución del Cuerpo se vuelve al paso 1.

Al igual que las condicionales, la instrucción while permite alterar el flujo de un pro-
grama.

No sólo los ejemplos con los que iniciábamos este apartado hacen explícita la necesi-
dad de iterar. En realidad, cualquier programa de cierta entidad contiene como mínimo
un bucle, más o menos sofisticado; está demostrado que toda la computación se puede
realizar sólo con iteración y con un conjunto muy pequeño de operaciones elementales.
Por ejemplo, las operaciones aritméticas ”*” y ”/” se pueden implementar, siempre con-
tando con la iteración, como sumas repetidas y restas repetidas, respectivamente. Aún
más, las operaciones aritméticas ”+” y ”-” son a su vez programables con incrementos
y disminuciones en 1 repetidos.

1 LA ITERACI ÓN COMO ESTRATEGIA: SUS FASES

3

Ahora bien, toda la potencia y expresividad que proporciona la iteración obligan a
un uso cuidadoso; piénsese, por ejemplo, que un bucle incorrecto puede serlo no sólo
porque no calcule el resultado esperado sino también porque no termine (bucle infinito).
Por tanto, dada la frecuencia con la que se usan los bucles y el cuidado que requiere su
construcción, conviene introducir una estrategia que, independientemente del lenguaje
de programación que se utilice, se pueda emplear con éxito para construir cualquier
tipo de bucle. Esta estrategia Iterativa consta de distintas fases, que se presentan a
continuación y se ejemplifican para la resolución del siguiente problema:

• diséñese un programa que, sin utilizar la operación ”*”, calcule el producto de

dos números enteros no negativos, a y b.

1.1 Descubriendo la estructura iterativa del problema.

Tras la lectura del enunciado, somos capaces de crear un esqueleto del programa Java
multiplicar cuyos datos son a y b, de tipo entero, y cuyo resultado es producto,
también de tipo entero. Nótese que sólo serán datos válidos aquellos que, siendo enteros,
son positivos o cero. A partir de aquí, y por eso hemos hablado de un esqueleto de
programa, la tarea básica que nos resta es determinar cuál es la(s) instrucción(es) a
realizar para calcular producto a partir de a y b, sin utilizar el operador ”*”.

....
class multiplicar {

public static void main(String args[]) {

...
//declaración e inicialización de variables dato y resultado
int a = Teclado.readint(), b = Teclado.readint(), producto;
if ( a>=0 && b>=0) {

// multiplicar a y b dejando el resultado en producto,
// sin usar el operador "*"

} else System.out.println("Lo siento, datos no válidos");

}

}

En primer lugar, y a partir del enunciado del problema, debemos plantearnos si
en multiplicar hay que utilizar un bucle; esto es, ¿se puede expresar a * b como el
resultado de la repetición, controlada, de una cierta operación? En efecto, sabemos que
el producto de dos números es una suma repetida:

a * b == producto == 0 + b + ... + b ”producto es 0 sumado a b, a veces”.
El uso de ”0” en la definición de la multiplicación nos permite contemplar el caso

particular a == 0; 0 se suma a b ninguna vez, con lo que 0 * b == 0.

Esta definición informal es lo suficientemente clara como para poner de manifiesto:
• que el Cuerpo de la iteración es una suma repetida;

1 LA ITERACI ÓN COMO ESTRATEGIA: SUS FASES

4

• que el Criterio de Repetición de la iteración es que hay que seguir sumando mien-
tras el número de repeticiones realizadas sea distinto de a; así, cuando el bucle
termine, producto == a * b

• que inicialmente, antes de la primera repetición, producto vale 0.
A partir de esta definción, podemos completar nuestro programa multiplicar como

sigue:

....
class multiplicar {

....
if ( a>=0 && b>=0) {

// multiplicar a y b dejando el resultado en producto,
// sin usar el operador "*"

// inicialización de producto
producto = 0;

// forma general del while
while (CriteriodeRepetición) Cuerpo;

System.out.println("El producto es "+producto);
} else System.out.println("Lo siento, datos no válidos");

...

Este esqueleto de programa incorpora ya la inicialización de producto. Sin embargo,
su bucle es, sólo, la forma general del while. Los restantes pasos de la estrategia
Iterativa refinarán esta primer solución hasta transformarla en un código Java totalmente
operativo.

1.2 Eligiendo las variables de la iteración.

Para expresar el Criterio de Repetición informal podemos utilizar un contador del
número de repeticiones que se van haciendo. Así, necesitamos definir una variable
contador, cont, de tipo entero, en el esqueleto de multiplicar; para recalcar que cont
está asociada al bucle, es aconsejable que su declaración se realice en el mismo bloque
donde se encuentra el while.

Además de llevar la cuenta del número de repeticiones, también es necesario llevar
la cuenta del resultado de la suma más reciente o, lo que es lo mismo, acumular el
resultado de las sumas realizadas hasta una repetición dada. Para ello no hace falta
definir una nueva variable puesto que esta cuenta la puede llevar la variable producto.
Veámoslo:

• tras la primera repetición habremos sumado una vez b a 0, con lo que cont==1

y producto == 1 * b == (0 + b);

1 LA ITERACI ÓN COMO ESTRATEGIA: SUS FASES

5

• tras la segunda repetición habremos sumado dos veces b a 0, con lo que cont==2

y producto == 2 * b == (0 + b) + (0 + b);

• y así sucesivamente hasta que tras la última repetición, en la que cont==a,

producto == a * b == (0 + b) + ... + (0 + b) ”a veces”.

A partir de su valor inicial 0, repetición tras repetición, se acumula sobre la va-
riable producto el resultado de las sumas realizadas, y sólo contendrá el resultado del
programa, a * b, cuando la iteración termine.

Esta descripción de producto, como variable acumulador de las sumas realizadas
hasta una repetición dada, hace explícita la estrecha relación que existe entre cont y
producto:

producto == cont * b

”producto es 0 sumado a b, cont veces”

Si esta relación deja de mantenerse en cualquier momento de la ejecución de la
iteración diseñada, ésta será incorrecta. Por tanto, los valores que se den y el uso que se
haga de ambas variables deben mantener inalterada esta relación, repetición a repetición.
Dicho esto, en lo que resta nos dedicaremos a dar valor