18. Esquemes de recorregut i cerca
Objectius
- Aprendre a dissenyar algorismes d’una manera més eficient i sistemàtica, aplicant algorismes genèrics ja coneguts (esquemes).
- Comprendre què és un esquema i com es pot aplicar.
- Conèixer l’esquema de recorregut aplicat a una seqüència.
- Conèixer l’esquema de cerca aplicat a una seqüència.
- Distingir entre l’esquema de recorregut i el de cerca.
- Saber resoldre problemes aplicant els esquemes de recorregut i de cerca.
Introducció
Amb les estructures que ja coneixem (seqüencial, alternativa i iterativa) ja podem resoldre qualsevol problema. En aquesta unitat no es presenta, doncs, cap estructura del llenguatge algorísmic nova, sinó que coneixerem els esquemes de recorregut i cerca; una espècie de patrons o estructures predeterminades que podem utilitzar per a dissenyar els nostres algorismes de manera més sistemàtica i guanyar en eficiència i fiabilitat.
Un esquema és un algorisme genèric, una mena de plantilla que ens permet solucionar un tipus de problema específic amb les adaptacions que calgui per a aplicar-ho al nostre cas concret. Dos dels esquemes més útils són els esquemes de recorregut i cerca. Aplicant aquests esquemes podem resoldre, per exemple, problemes de tractament de seqüències de manera més eficient i sistemàtica.
1. Aproximació intuïtiva
La idea de recorregut o de cerca és molt quotidiana. Per exemple, per a un consultor, la tasca de corregir la PEC1 de l’aula consisteix a anar corregint una per una totes les PEC1 que han lliurat els estudiants de la seva aula. Fa un recorregut per totes les PEC, que estan ordenades segons algun criteri (per exemple, ordre alfabètic o l’ordre en què les ha rebut) i a cadascuna d’elles els aplica un mateix tractament, corregir-les i avaluar-les. La tasca acaba quan ja estan totes corregides i avaluades. Està fent un recorregut a través d’una seqüència de dades d’un mateix tipus.
Si una vegada publicades les qualificacions de la PEC1, alguns estudiants demanen al consultor la revisió de la seva nota, el consultor haurà de buscar les PEC d’aquests estudiants d’entre totes les PEC1 que té i, una vegada les trobi, revisar-les. La tasca consisteix, doncs, a fer solament el tractament (revisar) a alguns elements del conjunt de PEC, en aquest cas només a les PEC dels estudiants que hagin demanat revisió. Està fent una cerca (cerca de les PEC que cal revisar) en una seqüència.
Fixem-nos ara en alguns dels exemples similars als que hem treballat en les unitats anteriors.
1.1. Exemple 18_01
En un algorisme anterior (que hem vist en la unitat d’estructura iterativa) calculem la temperatura mitjana de tot l’any suposant que anem llegint pel canal d’entrada les temperatures mitjanes de cada dia:
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);
return 0;
}
1.2. Exemple 18_02
Fixem-nos, també, en aquest altre exemple (que hem vist en la unitat de taules) on carreguem les dades d’una taula de recaptacions d’una sala de cinema a partir del que s’ha llegit pel canal d’entrada estàndard. Les dades venen donades com una sèrie de reals (una seqüència de reals) que podem llegir del canal estàndard i en la qual el valor -1.0 indica el final de la seqüència.
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->numTheaters = 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->numTheaters] = temp;
movieTheater->numTheaters = movieTheater->numTheaters _ 1;
scanf("%f", &temp);
}
}
2. Esquema de recorregut
En els dos exemples anteriors estem fent un recorregut a través d’una sèrie de dades (una seqüència de dades). En el primer cas, al llarg de la temperatura de cadascun dels 365 dies de l’any. En el segon cas, a través de les dades de recaptació de cadascuna de les sales del cinema.
Fixeu-vos en què en tots dos exemples estem repetint un mateix esquema que podríem veure així:
- 1r pas. Accés al primer element: accedir al primer dia que tractarem.
En el primer exemple és el primer dia de l’any, per la qual cosa assignem el valor 1 a la variable y. En el segon exemple, accedim a la recaptació de la primera sala, per la qual cosa llegim del canal estàndard la primera recaptació.
- 2n pas. Tractament inicial: fer el tractament inicial, això és, inicialitzar les variables que utilitzarem per a fer el tractament posterior.
En l’exemple 1, inicialitzem la variable mitjana a 0 i en el segon, inicialitzem la variable que comptabilitza el nombre de sales de cinema a 0.
- 3r pas. Últim element: comprovar si ja hem tractat totes les dades (si ja hem arribat al final de recorregut).
En el primer exemple, hem arribat a l’últim element quan estem en l’últim dia de l’any, el que fa 365. En el segon exemple hem arribat a l’últim element quan l’entrada de l’element que ens indica que ja no hi ha més recaptacions és -1 (això és una convenció que ens determina el propi enunciat de l’exemple).
- 4t pas. Tractar element: aplicar les accions que siguin necessàries per a resoldre el problema en cadascuna de les dades per tractar.
En el primer cas, es tracta de llegir la temperatura del dia en qüestió i sumar-la a la variable on anem acumulant les temperatures. En el segon cas, cal emmagatzemar la recaptació de la sala i incrementar el nombre de sales per a saber al final quantes sales té el cinema. Així anem emmagatzemant la informació que llegim en l’estructura de dades cinema.
- 5è pas. Accés al següent element: accedir a la següent dada.
En el primer exemple, passem al següent dia de l’any, per la qual cosa incrementem en 1 la variable y. En el segon exemple, accedim a la recaptació de la següent sala, per la qual cosa llegim del canal estàndard la següent recaptació.
- 6è pas. Tractament final: acabar de fer les accions que quedin per a resoldre el problema.
En el primer exemple, es tracta de calcular la mitjana i mostrar-la per pantalla. En el segon exemple no cal fer res, perquè l’objectiu d’emmagatzemar les recaptacions ja ha quedat realitzat.
Vegem-ho esquemàticament:
| Parts | Exemple 18_01 |
|---|
| Accés al primer element. | i := 1; |
| Tractament inicial. | mitjana := 0; |
| Comprovar si ja hem arribat a l’últim element. | while i <= 365 do |
| Tractar l’element. | temperatura := readReal(); mitjana := mitjana _ temperatura; |
| Accés al següent element. | i := i _ 1 |
| end while | |
| Tractament final. | writeReal(mitjana/365.0) |
| Parts | Exemple 18_02 |
|---|
| Accés al primer element. | temp := readReal(); |
| Tractament inicial. | movieTheater.numTheaters := 0; |
| Comprovar si ja hem arribat a l’últim element. | while temp ≠ END_SEQ do |
| Tractar l’element. | movieTheater.numTheaters := movieTheater.numTheaters _ 1; movieTheater.collect[movieTheater.numTheaters] := temp; |
| Accés al següent element. | temp := readReal(); |
| end while | |
| Tractament final. |
Per tant, sempre que necessitem fer un tractament per una sèrie de dades d’un mateix tipus que estiguin estructurades en forma de seqüència, o bé de dades que llegim seqüencialment a través del canal estàndard (com seria el cas de l’exemple 1) o dades d’una taula (com seria el cas de l’exemple 2), podem aplicar directament l’esquema de recorregut i així solament haurem de pensar sobre el tractament que realitzarem amb cadascuna de les dades, que dependrà del cas específic que cal resoldre, perquè l’algorisme va passant d’una dada a una altra, i ja ho tindrem resolt.
Aquest seria l’esquema de recorregut. Hi ha algunes variants però aquest és el patró més habitual:
algorithm esquemaRecorregut
{accedir_primer_element}
{tractament_inicial}
while no {últim element} do
{tractar_element}
{accedir_següent_element}
end while
{tractament_final}
end algorithm
Fixeu-vos que:
- Tots els elements de la seqüència sobre la qual fem un recorregut són del mateix tipus.
- Processem tots els elements de la seqüència de la mateixa manera.
- És necessari que sapiguem com s’acaba la seqüència. Això de vegades ja ho sabem directament, com en l’exemple 1, que sabem que un any té 365 dies, o ens ho indica l’enunciat, com en l’exemple 2, on se’ns diu que després de l’última recaptació llegirem un -1 (aquest -1 actua com a marca de finalització de seqüència). En el cas de tractament sobre taules, de vegades sabem la longitud de la taula (el nombre d’elements que conté) i, per tant, el nombre d’elements que cal tractar.
3. Esquema de cerca
Per a introduir l’esquema de cerca ens referirem també a exemples que ja hem vist anteriorment.
3.1. Exemple 18_03
Algorisme que partint d’un registre de les temperatures de tot l’any, que llegim pel canal estàndard, esbrina quin és el primer dia que ha gelat. Això equival a anar comprovant si alguna de les temperatures que tenim registrades de tot l’any és negativa o, el que és el mateix, a fer una cerca en la seqüència de temperatures diàries fins a trobar el primer valor negatiu.
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
#include <stdbool.h>
int main(int argc, char** argv) {
float t[365];
bool 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;
}
Observeu que quan trobem el primer cas de temperatura negativa, ja podem deixar de buscar. No cal que seguim revisant una altra temperatura, solament volem trobar el primer dia que ha gelat, no quants. Si volguéssim saber quants dies ha gelat, hauríem de fer un recorregut per totes les temperatures.
En aquest exemple estem fent una cerca en un conjunt de dades (una seqüència de dades). Busquem una temperatura negativa entre les 365 temperatures registrades d’un any.
Per a buscar dins de la seqüència estem utilitzant un mateix esquema, que podríem representar així:
- 1r pas. Accedir al primer element: accedir a la primera dada que cal tractar.
En el cas del primer exemple, el primer dia de l’any, per la qual cosa assignem el valor 1 a la variable y.
- 2n pas. Tractament inicial: fer el tractament inicial, això és, inicialitzar les variables que utilitzarem per a fer el tractament posterior.
En aquest exemple no necessitem cap variable específica per al tractament.
Això sí, caldrà inicialitzar amb el valor fals la variable trobat que ens servirà per a controlar si hem trobat l’element que busquem.
- 3r pas. Últim element: comprovar si ja hem tractat totes les dades (si ja hem arribat al final del recorregut).
En l’exemple, haurem arribat a l’últim element quan estiguem en l’últim dia de l’any, el que fa 365.
- 4t pas. Actualitzar trobat: cal comprovar si l’element que estem tractant és l’element que busquem i actualitzar la variable trobat en conseqüència.
- 5è pas. Accedir següent element: accedir a la següent dada.
Passem al següent dia de l’any, per la qual cosa incrementem en 1 la variable y.
- 6è pas. Tractament final: acabar de fer les accions que quedin per a resoldre el problema.
En el cas del primer exemple, es tracta d’indicar per pantalla si ha gelat o no.
Vegem-ho esquemàticament:
| Parts | Exemple 18_03 |
|---|---|
| Accedir al primer element. | i := 1; |
| Tractament inicial. | no cal inicialitzar cap variable; |
| trobat := false; | |
| Comprovar si ja hem arribat a l’últim element. | while i <= 365 and not trobat do |
| Actualitzar trobat. | t[i] := readReal(); if t[i] <= 0 llavors trobat:= true; |
| if not trobat then | |
| Accedir al següent element. | i := i _ 1; |
| end if | |
| end while | |
| Tractament final. | writeBoolean(trobat) |
Per tant, sempre que necessitem buscar un element dins d’un conjunt de dades que llegim seqüencialment a través del canal estàndard, com seria el cas de l’exemple o dades d’una taula, podem aplicar directament l’esquema de cerca.
Aquest seria l’esquema de cerca. Hi ha algunes variants però aquesta és la més habitual.
algorithm esquemaCerca
var
trobat: boolean;
end var
{accedir_primer_element}
{tractament_inicial}
trobat:= false;
while no {últim element} and not trobat do
if {element tractat compleix condició} then
trobat:= true;
else
{accedir al sigüent element}
end if
end while
{tractament_final}
end algorithm
Fixeu-vos que:
- A diferència de l’esquema de recorregut on tractem tots els elements, en l’esquema de cerca recorrem únicament la seqüència fins a trobar un element que compleix una determinada condició.
- L’esquema contempla la possibilitat que la seqüència no contingui l’element buscat.
- L’esquema preveu que la cerca acabi per algun dels dos motius següents: o bé trobem l’element buscat o bé arribem al final de la seqüència.
- Una cerca pot arribar a ser un recorregut quan l’element que busquem és l’últim o no existeix.
4. Exercicis d’autoavaluació
Una vegada vistos els esquemes de cerca i recorregut, ja els podem començar a aplicar en els propers algorismes que hàgim de dissenyar. El primer pas per a fer-ho és saber si el problema tracta seqüències de dades del mateix tipus. I el segon pas és esbrinar si el problema és un recorregut o una cerca.
Els següents exercicis d’autoavaluació permeten consolidar aquests aspectes.
Preguntes de resposta única
- Per a què serveixen els esquemes algorísmics?
a. Per a sistematitzar la resolució d’algorismes.
b. Per a estalviar línies de codi.
c. Per a resoldre problemes que no poden resoldre’s amb les estructures seqüencial, alternativa i iterativa.
d. Totes les anteriors.
e. Cap de les anteriors. - És convenient aplicar l’esquema de recorregut quan...
a. hem de buscar un element en una seqüència.
b. hem d’aplicar un mateix tractament a tots els elements d’una seqüència.
c. tenim seqüències d’elements de diferent tipus.
d. sabem el nombre d’elements d’una seqüència.
e. Totes les anteriors. - Per a poder aplicar l’esquema de cerca cal...
a. que la seqüència no estigui buida.
b. que hi hagi els elements buscats en la seqüència.
c. que tots els elements de la seqüència siguin del mateix tipus.
d. saber des de l’inici el nombre d’elements de la seqüència.
Preguntes de resposta certa o falsa
A. Una cerca pot acabar sent un recorregut per tota la seqüència.
B. Una cerca finalitza solament quan es troba l’element buscat.
C. Solament hi ha una manera de saber si hem arribat al final de la seqüència.
D. En un recorregut el primer element es tracta diferent de la resta.
E. En un recorregut l’últim element sempre es tracta diferent de la resta.
F. En un recorregut cada element es tracta diferent de la resta.
Preguntes de decisió sobre cerca o recorregut
A continuació, es descriuen una sèrie d’enunciats. Decidiu en cada cas si és necessari fer un recorregut o una cerca. Una vegada comprovada la solució, podeu dissenyar l’algorisme per a practicar l’aplicació dels esquemes.
Alg. 1. Calcular la mitjana aritmètica d’una sèrie de nombres reals positius que llegim pel canal estàndard. Per a marcar la fi de seqüència, després de l’últim nombre a considerar, llegirem un nombre negatiu.
Alg. 2. Esbrinar si tots els estudiants d’una aula han superat la PEC1. Les qualificacions dels estudiants estan introduïdes en una estructura del tipus taula.
Alg. 3. Comptar les ‘a’ d’un text acabat en ‘.’ que llegim pel canal estàndard.
Alg. 4. Comptar el nombre de caràcters d’una frase acabada en ‘.’ que llegim pel canal estàndard sense tenir en compte els espais en blanc.
Alg. 5. Localitzar si una seqüència d’enters és creixent.
Alg. 6. Copiar una frase acabada en ‘.’ eliminant els espais.
Alg. 7. Detectar si dues frases acabades en ‘.’ són iguals.
Respostes
1.a
2.b
3.c
A. Cert
B. Fals
C. Fals
D. Fals
E. Fals
F. Fals
Alg.1: recorregut
Alg.2: cerca
Alg.3: recorregut
Alg.4: recorregut
Alg.5: cerca
Alg.6: recorregut
Alg.7: cerca
Resum
En aquesta unitat hem vist dos esquemes diferents que s’utilitzen per a tractar seqüències de dades: l’esquema de recorregut i el de cerca.