Unitat Didàctica 5:
En aquesta unitat aprendràs:
En programació, molts problemes aparentment diferents comparteixen en realitat la mateixa estructura lògica fonamental. Un esquema algorítmic és un patró de disseny provat i reutilitzable per resoldre una família concreta de problemes sobre col·leccions o fluxos de dades.
En lloc de reinventar la roda cada vegada, els programadors identifiquem quin esquema s'adapta millor a la situació i l'apliquem amb seguretat. Tots els esquemes iteratius sobre seqüències consten de cinc fases bàsiques:
Davant de qualsevol problema sobre una col·lecció de dades, la primera pregunta que t'has de fer és:
Els esquemes de recorregut examinen cada element d'una seqüència des del primer fins a l'últim sense interrupció.
Un comptador és una variable entera que s'inicialitza a zero i s'incrementa en una quantitat constant (generalment +1) cada vegada que un element compleix una determinada condició.
Un acumulador és una variable que agrega o suma els valors dels elements d'una seqüència. Si l'acumulació és una suma, s'inicialitza a 0 (l'element neutre de la suma); si és un producte, s'inicialitza a 1 (l'element neutre de la multiplicació).
A continuació pots veure en acció tots dos esquemes combinats: comptem quants alumnes han aprovat (comptador) i sumem les seves notes (acumulador) per després calcular la mitjana dels aprovats.
int[] notes = {4, 7, 2, 9, 5, 8};
int aprovats = 0;
int suma = 0;
for (int i = 0; i < notes.length; i++) {
int nota = notes[i];
if (nota >= 5) {
aprovats++;
suma += nota;
}
}
println("Aprovats: " + aprovats);
println("Suma aprovats: " + suma);
La determinació del valor màxim o mínim d'una seqüència és un esquema de recorregut: tret que la col·lecció estigui ordenada, cal examinar obligatòriament tots els elements per assegurar que cap altre supera el candidat actual.
Quan busques el màxim o mínim d'un array, mai inicialitzis el màxim a zero ni a un valor arbitrari! Si tots els números de l'array fossin negatius (per exemple: {-10, -5, -20}), un màxim inicialitzat a 0 retornaria erròniament 0 com a resultat.
La manera correcta i universal és inicialitzar sempre la variable amb el primer element de la seqüència (valors[0]) i començar el bucle des de l'índex 1:
A més del propi valor extrem, sovint necessitem registrar la posició (índex) on s'ha trobat. Observa com s'actualitzen de manera coordinada tant max com posMax:
int[] valors = {12, 45, 67, 23, 89, 34};
int max = valors[0];
int posMax = 0;
for (int i = 1; i < valors.length; i++) {
if (valors[i] > max) {
max = valors[i];
posMax = i;
}
}
println("Maxim: " + max + " a posicio " + posMax);
Una bandera (flag) és una variable booleana que registra si s'ha complert o no una propietat al llarg del recorregut. Es distingeixen dos tipus fonamentals de preguntes lògiques:
true (suposem d'entrada que tots la compleixen). Si en qualsevol moment trobem un sol element que no la compleix, canviem la bandera a false i podem interrompre el bucle.false (suposem que ningú la compleix). En el moment que trobem el primer que la compleix, canviem a true i ens aturem.La cerca seqüencial és l'algorisme de cerca més intuïtiu: recorre els elements un rere l'altre des del principi fins que troba l'element buscat o arriba al final de l'array. És l'únic mètode que podem utilitzar quan les dades no estan ordenades.
Fixa't en l'ús de break per finalitzar immediatament tan bon punt es localitza l'índex:
int[] dades = {14, 25, 8, 42, 19};
int objectiu = 42;
int pos = -1;
for (int i = 0; i < dades.length; i++) {
if (dades[i] == objectiu) {
pos = i;
break;
}
}
println("Trobat a index: " + pos);
Quan tenim una col·lecció de dades prèviament ordenada, no cal examinar els elements d'un en un. La cerca binària aprofita l'ordre aplicant la potent estratègia de divideix i venceràs:
mig = (esquerra + dreta) / 2.esquerra = mig + 1.dreta = mig - 1.esquerra <= dreta. Si es creuen i no l'hem trobat, l'element no és a l'array.Observa en aquest stepper com els límits esq i dre s'acosten ràpidament fins a localitzar el número 23 en només 3 comparacions:
int[] ordenat = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int clau = 23;
int esq = 0;
int dre = ordenat.length - 1;
int trobat = -1;
while (esq <= dre) {
int mig = (esq + dre) / 2;
if (ordenat[mig] == clau) {
trobat = mig;
break;
} else if (ordenat[mig] < clau) {
esq = mig + 1;
} else {
dre = mig - 1;
}
}
println("Index clau: " + trobat);
A cada iteració, la cerca binària descarta la meitat dels elements restants. El seu cost computacional és $O(\log_2 n)$ enfront del cost lineal $O(n)$ de la cerca seqüencial:
Tenir les dades ordenades és el requisit previ per fer cerques ultraràpides. Vegem els tres algorismes clàssics d'ordenació directa que tot programador ha de dominar.
El mètode de la bombolla compara repetidament elements adjacents (veïns) i els intercanvia si estan en l'ordre incorrecte. En cada passada completa pel bucle exterior, el valor més gran restant "flota" fins a la seva posició definitiva al final de l'array, com si fos una bombolla d'aire en l'aigua.
int[] arr = {5, 1, 4, 2, 8};
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
println("Primer: " + arr[0] + ", ultim: " + arr[n - 1]);
L'algorisme de selecció divideix virtualment l'array en dues parts: la subllista d'elements ja ordenats (a l'esquerra) i la subllista d'elements pendents d'ordenar (a la dreta).
A cada iteració, cerca l'element mínim de la part desordenada i l'intercanvia amb el primer element pendent. Té l'avantatge que realitza molts menys intercanvis de memòria que la bombolla:
int[] a = {29, 10, 14, 37, 13};
int n = a.length;
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (a[j] < a[minIdx]) {
minIdx = j;
}
}
int tmp = a[i];
a[i] = a[minIdx];
a[minIdx] = tmp;
}
println("Ordenat primer: " + a[0]);
És la forma natural en què la majoria de persones ordenem les cartes quan juguem a la baralla: mantenim les cartes ordenades a la mà esquerra i, en rebre una nova carta, la desplacem cap enrere comparant-la amb les anteriors fins a trobar el seu lloc exacte.
La fusió o mescla és un esquema que rep dos arrays $A$ i $B$ que ja estan ordenats i construeix un nou array $C$ amb tots els elements de tots dos, també perfectament ordenat.
Utilitza tres punters (i, j, k) que avancen compassadament comparant els elements del capdamunt de cada llista. Funciona en temps estrictament lineal $O(n + m)$ i és el cor del famós algorisme d'ordenació Merge Sort:
| Esquema | Objectiu | Precondició | Complexitat |
|---|---|---|---|
| Recorregut | Comptar, sumar, transformar tots els elements | Cap | $O(n)$ |
| Cerca Lineal | Localitzar element en dades desordenades | Cap | $O(n)$ |
| Cerca Binària | Localitzar element ràpidament | Array ordenat | $O(\log n)$ |
| Bombolla / Selecció | Ordenar arrays | Cap | $O(n^2)$ |
| Mescla (Merge) | Unir dues llistes ordenades | Totes dues ordenades | $O(n + m)$ |
Posa a prova els teus coneixements d'esquemes algorítmics completant els reptes interactius i els projectes d'ordenació i cerca.