18. Esquemas de recorrido y búsqueda
Objetivos
- Aprender a diseñar algoritmos de una manera más eficiente y sistemática, aplicando algoritmos genéricos ya conocidos (esquemas).
- Comprender qué es un esquema y cómo se puede aplicar.
- Conocer el esquema de recorrido aplicado a una secuencia.
- Conocer el esquema de búsqueda aplicado a una secuencia.
- Distinguir entre el esquema de recorrido y el de búsqueda.
- Saber resolver problemas aplicando los esquemas de recorrido y de búsqueda.
Introducción
Con las estructuras que ya conocemos (secuencial, alternativa e iterativa) ya podemos resolver cualquier problema. En esta unidad no se presenta, pues, ninguna estructura del lenguaje algorítmico nueva, sino que conoceremos los esquemas de recorrido y búsqueda; una especie de patrones o estructuras predeterminadas que podemos utilizar para diseñar nuestros algoritmos de manera más sistemática y ganar en eficiencia y fiabilidad.
Un esquema es un algoritmo genérico, una especie de plantilla que nos permite solucionar un tipo de problema específico con las adaptaciones que haga falta para aplicarlo a nuestro caso concreto. Dos de los esquemas más útiles son los esquemas de recorrido y búsqueda. Aplicando estos esquemas podemos resolver, por ejemplo, problemas de tratamiento de secuencias de manera más eficiente y sistemática.
1. Aproximación intuitiva
La idea de recorrido o de búsqueda es muy cotidiana. Por ejemplo, para un consultor, la tarea de corregir la PEC1 del aula consiste en ir corrigiendo una a una todas las PEC1 que han entregado los estudiantes de su aula. Hace un recorrido por todas las PEC, que están ordenadas según algún criterio (por ejemplo orden alfabético o el orden en que las ha recibido) y a cada una de ellas les aplica un mismo tratamiento, corregirlas y evaluarlas. La tarea termina cuando ya están todas corregidas y evaluadas. Está haciendo un recorrido a través de una secuencia de datos de un mismo tipo.
Si una vez publicadas las calificaciones de la PEC1, algunos estudiantes piden al consultor la revisión de su nota, el consultor deberá buscar las PAC de estos estudiantes de entre todas las PEC1 que tiene y, una vez las encuentre, revisarlas. La tarea consiste, pues, en hacer solo el tratamiento (revisar) a algunos elementos del conjunto de PEC, en este caso solo a las PEC de los estudiantes que hayan pedido revisión. Está haciendo una búsqueda (búsqueda de las PEC que hay que revisar) en una secuencia.
Fijémonos ahora en algunos de los ejemplos similares a los que hemos trabajado en las unidades anteriores.
1.1. Ejemplo 18_01
En un algoritmo anterior (que hemos visto en la unidad de estructura iterativa) calculamos la temperatura media de todo el año suponiendo que vamos leyendo por el canal de entrada las temperaturas medias de cada día:
algorithm averageTemp
var
temperature: real;
average: real;
i: integer;
end var
i:=1;
average:=0;
while i ≤ 365 do
temperature:= readReal();
average:=average+temperature;
i:=i+1;
end while
writeReal(average/365.0);
end algorithm
int main(int argc, char** argv) {
float temperature;
float average;
int i;
i = 0;
average = 0;
while (i < 365) {
scanf("%f", & temperature);
average = average + temperature;
i = i + 1;
}
printf("%f", average / 365.0);
return 0;
}
1.2. Ejemplo 18_02
Fijémonos, también, en este otro ejemplo (que hemos visto en la unidad de tablas) donde cargamos los datos de una tabla de recaudaciones de una sala de cine a partir de lo leído por el canal de entrada estándar. Los datos vienen dados como una serie de reales (una secuencia de reales) que podemos leer del canal estándar y en la que el valor -1.0 indica el final de la secuencia.
const
MAX_THEATERS: integer = 20;
END_SEQ: real = -1.0;
end const
type
tTheater = record
collect: vector[MAX_THEATERS] of real;
numTheaters: integer;
end record
end type
action fillTable(inout movieTheater: tTheater);
var
i: integer;
temp: real;
end var
temp:= readReal(); {we read the first number}
movieTheater.numTheaters:=0;
while temp ≠ END_SEQ do
movieTheater.numTheaters:= movieTheater.numTheaters + 1;
movieTheater.collect[movieTheater.numTheaters]:= temp;
temp:= readReal();
end while
end action
#define END_SEQ -1
#define MAX_THEATERS 20
typedef struct {
float collect[MAX_THEATERS];
int numTheaters;
} tTheater;
void fillTable(tTheaters *movieTheater) {
/* var definition */
int i;
float temp;
/* table initialization */
movieTheater->numTheater = 0;
scanf("%f", &temp); /* read the first number */
/* iteration while the read number is not -1 */
while (temp != END_SEQ) {
/*Save the read number in the table*/
movieTheater->collect[movieTheater->numTheater] = temp;
movieTheater->numTheater = movieTheater->numTheater + 1;
scanf("%f", &temp);
}
}
2. Esquema de recorrido
En los dos ejemplos anteriores estamos haciendo un recorrido a través de una serie de datos (una secuencia de datos). En el primer caso, a lo largo de la temperatura de cada uno de los 365 días del año. En el segundo caso, a través de los datos de recaudación de cada una de las salas del cine.
Fijaos en que en ambos ejemplos estamos repitiendo un mismo esquema que podríamos ver así:
- 1er paso. Acceso al primer elemento: acceder al primer día que trataremos.
En el primer ejemplo es el primer día del año, por lo que asignamos el valor 1 a la variable y. En el segundo ejemplo, accedemos a la recaudación de la primera sala, por lo que leemos del canal estándar la primera recaudación.
- 2º paso. Tratamiento inicial: hacer el tratamiento inicial, esto es inicializar las variables que utilizaremos para hacer el tratamiento posterior.
En el ejemplo 1, inicializamos la variable media a 0 y en el segundo, inicializamos la variable que contabiliza el número de salas de cine a 0.
- 3er paso. Último elemento: comprobar si ya hemos tratado todos los datos (si ya hemos llegado al final de recorrido).
En el primer ejemplo, hemos llegado al último elemento cuando estamos en el último día del año, el que hace 365. En el segundo ejemplo hemos llegado al último elemento cuando la entrada del elemento que nos indica que ya no hay más recaudaciones es -1 (esto es una convención que nos determina el propio enunciado del ejemplo).
- 4º. paso. Tratar elemento: aplicar las acciones que sean necesarias para resolver el problema en cada uno de los datos por tratar.
En el primer caso, se trata de leer la temperatura del día en cuestión y sumarla a la variable donde vamos acumulando las temperaturas. En el segundo caso, hay que almacenar la recaudación de la sala e incrementar el número de salas para saber al final cuántas salas tiene el cine. Así vamos almacenando la información que leemos en la estructura de datos cine.
- 5º. paso. Acceso al siguiente elemento: acceder al siguiente dato.
En el primer ejemplo, pasamos al siguiente día del año, por lo que incrementamos en 1 la variable y. En el segundo ejemplo, accedemos a la recaudación de la siguiente sala, por lo que leemos del canal estándar la siguiente recaudación.
- 6º paso. Tratamiento final: terminar de hacer las acciones que queden para resolver el problema.
En el primer ejemplo, se trata de calcular la media y mostrarla por pantalla. En el segundo ejemplo no hay que hacer nada, porque el objetivo de almacenar las recaudaciones ya ha quedado realizado.
Veámoslo esquemáticamente:
| Partes | Ejemplo 18_01 |
|---|---|
| Acceso al primer elemento. | i := 1; |
| Tratamiento inicial. | media := 0; |
| Comprobar si ya hemos llegado al último elemento. | while i ≤ 365 do |
| Tratar el elemento. | temperatura := readReal(); media := media + temperatura; |
| Acceso al siguiente elemento. | i := i + 1 |
| end while | |
| Tratamiento final. | writeReal(media/365.0) |
| Partes | Ejemplo 18_02 |
|---|---|
| Acceso al primer elemento. | temp := readReal(); |
| Tratamiento inicial. | movieTheater.numTheaters := 0; |
| Comprobar si ya hemos llegado al último elemento. | while temp ≠ END_SEQ do |
| Tratar el elemento. | movieTheater.numTheaters := movieTheater.numTheaters + 1; movieTheater.collect[movieTheater.numTheaters] := temp; |
| Acceso al siguiente elemento. | temp := readReal(); |
| end while | |
| Tratamiento final. |
Por lo tanto, siempre que necesitemos hacer un tratamiento por una serie de datos de un mismo tipo que estén estructurados en forma de secuencia, o bien de datos que leemos secuencialmente a través del canal estándar (como sería el caso del ejemplo 1) o datos de una tabla (como sería el caso del ejemplo 2), podemos aplicar directamente el esquema de recorrido y así solo tendremos que pensar sobre el tratamiento que realizaremos con cada uno de los datos, que dependerá del caso específico que resolver porque el algoritmo va pasando de un dato a otro, y ya lo tendremos resuelto.
Este sería el esquema de recorrido. Existen algunas variantes pero este es el patrón más habitual:
algorithm esquemaRecorrido
{acceder_primer_elemento}
{tratamiento_inicial}
while not {último elemento} do
{tratamiento_elemento}
{acceder_siguiente_elemento}
end while
{tratamiento_final}
end algorithm
Fijaos en que:
- Todos los elementos de la secuencia sobre la que hacemos un recorrido son del mismo tipo.
- Procesamos todos los elementos de la secuencia de la misma manera.
- Es necesario que sepamos cómo se acaba la secuencia. Esto a veces ya lo sabemos directamente, como en el ejemplo 1, que sabemos que un año tiene 365 días, o nos lo indica el enunciado, como en el ejemplo 2, donde se nos dice que después de la última recaudación leeremos un -1 (este -1 actúa como marca de fin de secuencia ). En el caso de tratamiento sobre tablas, a veces sabemos la longitud de la tabla (el número de elementos que contiene) y, por tanto, el número de elementos que tratar.
3. Esquema de búsqueda
Para introducir el esquema de búsqueda nos referiremos también a ejemplos que ya hemos visto anteriormente.
3.1. Ejemplo 18_03
Algoritmo que partiendo de un registro de las temperaturas de todo el año, que leemos por el canal estándar, averigua cuál es el primer día que ha helado. Esto equivale a ir comprobando si alguna de las temperaturas que tenemos registradas de todo el año es negativa o lo que es lo mismo, a hacer una búsqueda en la secuencia de temperaturas diarias hasta encontrar el primer valor negativo.
algorithm hasFrozen?
var
t: vector[365] of real;
frost: boolean;
i: integer;
end var
i:=1;
frost:= false;
while i ≤ 365 and frost == false do
t[i]:=readReal();
if t[i] ≤ 0 then
frost:= true;
end if
i:=i+1:
end while
writeBoolean(frost);
end algorithm
typedef enum {FALSE, TRUE} boolean;
int main(int argc, char** argv) {
float t[365];
boolean frost;
int i;
i = 0;
frost = FALSE;
while (i < 365 && frost == FALSE) {
scanf("%f", &t[i]);
if (t[i] < 0 ) {
frost = TRUE;
}
i = i + 1;
}
printf("%d", frost); // Equivalence in C language: 0 == FALSE, 1 == TRUE
return 0;
}
Observad que cuando encontramos el primer caso de temperatura negativa, ya podemos dejar de buscar. No hace falta que sigamos revisando otra temperatura, solo queremos encontrar el primer día que ha helado, no cuántos. Si quisiéramos saber cuántos días ha helado, tendríamos que hacer un recorrido por todas las temperaturas.
En este ejemplo estamos haciendo una búsqueda en un conjunto de datos (una secuencia de datos). Buscamos una temperatura negativa entre las 365 temperaturas registradas de un año.
Para buscar dentro de la secuencia estamos utilizando un mismo esquema, que podríamos representar así:
- 1r paso. Acceder al primer elemento: acceder al primer dato que tratar.
En el caso del primer ejemplo, el primer día del año, por lo que asignamos el valor 1 a la variable y.
- 2º. paso. Tratamiento inicial: hacer el tratamiento inicial, esto es inicializar las variables que utilizaremos para hacer el tratamiento posterior.
En este ejemplo no necesitamos ninguna variable específica para el tratamiento.
Eso sí, habrá que inicializar con el valor falso la variable encontrado que nos servirá para controlar si hemos encontrado el elemento que buscamos.
- 3r. paso. Último elemento: comprobar si ya hemos tratado todos los datos (si ya hemos llegado al final de recorrido).
En el ejemplo, habremos llegado al último elemento cuando estamos en el último día del año, el que hace 365.
- 4º. paso. Actualizar encontrado: hay que comprobar si el elemento que estamos tratando es el elemento que buscamos y actualizar la variable encontrado en consecuencia.
- 5º. paso. Acceder siguiente elemento: acceder al siguiente dato.
Pasamos al siguiente día del año, por lo que incrementamos en 1 la variable y.
- 6º. paso. Tratamiento final: terminar de hacer las acciones que queden por resolver el problema.
En el caso del primer ejemplo, se trata de indicar por pantalla si ha helado o no.
Veámoslo esquemáticamente:
| Partes | Ejemplo 18_03 |
|---|---|
| Acceder al primer elemento. | i := 1; |
| Tratamiento inicial. | no hace falta inicializar ninguna variable; |
| encontrado := false; | |
| Comprobar si ya hemos llegado al último elemento. | while i ≤ 365 and not encontrado do |
| Actualizar encontrado. | t[i] := readReal(); if t[i] ≤ 0 entonces encontrado:= true; |
| if not encontrado then | |
| Acceder al siguiente elemento. | i := i + 1; |
| end if | |
| end while | |
| Tratamiento final. | writeBoolean(encontrado) |
Por tanto, siempre que necesitemos buscar un elemento dentro de un conjunto de datos que leemos secuencialmente a través del canal estándar, como sería el caso del ejemplo o datos de una tabla, podemos aplicar directamente el esquema de búsqueda.
Este sería el esquema de búsqueda. Existen algunas variantes pero esta es la más habitual.
algorithm esquemaBusqueda
var
encontrado: boolean;
end var
{acceder_primer_elemento}
{tratamiento_inicial}
encontrado:= false;
while not {último elemento} and not encontrado do
if {elemento tratado cumple condición} then
encontrado:= true;
else
{acceder al siguiente elemento}
end if
end while
{tratamiento_final}
end algorithm
Fijaos en que:
- A diferencia del esquema de recorrido donde tratamos todos los elementos, en el esquema de búsqueda recorremos únicamente la secuencia hasta encontrar un elemento que cumple una determinada condición.
- El esquema contempla la posibilidad de que la secuencia no contenga el elemento buscado.
- El esquema prevé que la búsqueda termine por alguno de los dos motivos siguientes: o bien encontramos el elemento buscado o bien llegamos al final de la secuencia.
4. Ejercicios de autoevaluación
Una vez vistos los esquemas de búsqueda y recorrido, ya los podemos empezar a aplicar en los próximos algoritmos que tengamos que diseñar. El primer paso para hacerlo es saber si el problema trata secuencias de datos del mismo tipo. Y el segundo paso es averiguar si el problema es un recorrido o una búsqueda.
Los siguientes ejercicios de autoevaluación permiten consolidar estos aspectos.
Preguntas de respuesta única
- ¿Para qué sirven los esquemas algorítmicos?
a. Para sistematizar la resolución de algoritmos.
b. Para ahorrar líneas de código.
c. Para resolver problemas que no pueden resolverse con las estructuras secuencial, alternativa y iterativa.
d. Todas las anteriores.
e. Ninguna de las anteriores.
- Es conveniente aplicar el esquema de recorrido cuando...
a. tenemos que buscar un elemento en una secuencia
b. debemos aplicar un mismo tratamiento a todos los elementos de una secuencia
c. tenemos secuencias de elementos de diferente tipo
d. sabemos el número de elementos de una secuencia
e. todas las anteriores
- Para poder aplicar el esquema de búsqueda hace falta...
a. que la secuencia no esté vacía
b. que haya los elementos buscados en la secuencia
c. que todos los elementos de la secuencia sean del mismo tipo
d. saber desde el inicio el número de elementos de la secuencia
Preguntas de respuesta cierta o falsa
A. Una búsqueda puede terminar siendo un recorrido por toda la secuencia.
B. Una búsqueda finaliza solo cuando se encuentra el elemento buscado.
C. Solo hay una manera de saber si hemos llegado al final de la secuencia.
D. En un recorrido el primer elemento se trata diferente al resto.
E. En un recorrido el último elemento siempre se trata diferente al resto.
F. En un recorrido cada elemento se trata diferente al resto.
Preguntas de decisión sobre búsqueda o recorrido
A continuación, se describen una serie de enunciados. Decidid en cada caso si es necesario hacer un recorrido o una búsqueda. Una vez comprobada la solución, podéis diseñar el algoritmo para practicar la aplicación de los esquemas.
Alg. 1. Calcular la media aritmética de una serie de números reales positivos que leemos por el canal estándar. Para marcar el fin de secuencia, después del último número a considerar, leeremos un número negativo.
Alg. 2. Averiguar si todos los estudiantes de un aula han superado la PEC1. Las calificaciones de los estudiantes están introducidas en una estructura del tipo tabla.
Alg. 3. Contar las ‘a’ de un texto acabado en ‘.’que leemos por el canal estándar.
Alg. 4. Contar el número de caracteres de una frase terminada en ‘.’ que leemos por el canal estándar sin tener en cuenta los espacios en blanco.
Alg. 5. Localizar si una secuencia de enteros es creciente.
Alg. 6. Copiar una frase terminada en ‘.’ eliminando los espacios.
Alg. 7. Detectar si dos frases acabadas en ‘.’ son iguales.
Respuestas
1.a
2.b
3.c
A. Cierto
B. Falso
C. Falso
D. Falso
E. Falso
F. Falso
Alg.1: recorrido
Alg.2: búsqueda
Alg.3: recorrido
Alg.4: recorrido
Alg.5: búsqueda
Alg.6: recorrido
Alg.7: búsqueda
Resumen
En esta unidad hemos visto dos esquemas diferentes que se utilizan para tratar secuencias de datos: el esquema de recorrido y el de búsqueda.