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:
Podem ampliar la cerca lineal per localitzar un patró: una seqüència d'elements que ha d'aparéixer en el mateix ordre i en posicions consecutives dins d'un altre array. Provem cada possible posició inicial i comparem els elements del patró amb els de l'array a partir d'aquella posició.
Si n és la longitud de les dades i m la del patró, l'últim inici possible és n - m, inclòs. Per a cada inici i, comparem dades[i + j] amb patro[j]:
int[] dades = {2, 1, 2, 3, 1};
int[] patro = {2, 3};
int pos = -1;
for (int i = 0; i <= dades.length - patro.length; i++) {
boolean coincideix = true;
for (int j = 0; j < patro.length; j++) {
if (dades[i + j] != patro[j]) {
coincideix = false;
break;
}
}
if (coincideix) {
pos = i;
break;
}
}
println("Inici del patro: " + pos);
El resultat és 2; si el patró no apareix, pos conserva el valor -1. Si el patró és més llarg que les dades, el bucle exterior no s'executa. Amb un patró buit, aquest codi retorna 0, seguint el conveni que la seqüència buida apareix al principi.
En el pitjor cas es comparen fins a m elements per cada inici possible: el cost és $O((n - m + 1) m)$ quan $1 ≤ m ≤ n$, habitualment expressat com $O(nm)$.
En una cadena de text, un patró contigu és una subcadena. Podem aplicar el mateix algorisme utilitzant length() i charAt(i + j) / charAt(j) per comparar els caràcters de les dades i del patró. Una subseqüència, en canvi, permet saltar elements mantenint-ne l'ordre: {2, 3} és subseqüència de {2, 1, 3}, però no és un segment contigu.
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:
Una finestra és un segment d'elements consecutius d'una seqüència. Si té mida k i comença a l'índex i, inclou les posicions de i a i + k - 1. Desplaçar-la una posició significa eliminar l'element de l'esquerra i incorporar-ne un de nou per la dreta.
Volem trobar la suma màxima de k elements consecutius i l'índex on comença el primer segment que l'aconsegueix. Suposem que 1 ≤ k ≤ dades.length.
Una primera solució consisteix a provar tots els inicis possibles i calcular cada suma des de zero:
La condició inici == 0 fa que la primera suma es guarde sempre, encara que siga negativa. Després, només actualitzem el màxim si la nova suma és superior. Aquesta solució fa k sumes per cada finestra: cost $O((n - k + 1) k)$, amb una cota $O(nk)$.
Dues finestres consecutives comparteixen k - 1 elements. Per tant, podem obtindre la nova suma amb una resta i una suma: restem l'element que ix i sumem el que entra.
| Inici | Finestra | Càlcul de la suma |
|---|---|---|
| 0 | 2, 1, 5 | 2 + 1 + 5 = 8 |
| 1 | 1, 5, 1 | 8 − 2 + 1 = 7 |
| 2 | 5, 1, 3 | 7 − 1 + 3 = 9 |
k. Per a cada índex i, ix dades[i - k] i entra dades[i].i - k + 1.
int[] dades = {2, 1, 5, 1, 3};
int k = 3;
int suma = 0;
for (int i = 0; i < k; i++) {
suma += dades[i];
}
int sumaMax = suma;
int iniciMax = 0;
for (int i = k; i < dades.length; i++) {
suma -= dades[i - k];
suma += dades[i];
if (suma > sumaMax) {
sumaMax = suma;
iniciMax = i - k + 1;
}
}
println("Suma maxima: " + sumaMax);
println("Inici: " + iniciMax);
El resultat és una suma màxima de 9 amb inici a l'índex 2. En cas d'empat, conservem la primera finestra perquè comparem amb >. L'algorisme també funciona amb valors negatius: el màxim inicial és la suma de la primera finestra, no zero.
El primer bucle processa k elements i el segon en processa n - k. En total, el cost és $O(n)$ i l'espai addicional és $O(1)$. Si k == dades.length, només hi ha una finestra i el segon bucle no s'executa.
En la cerca de patrons també desplacem un segment, però tornem a comparar els elements en cada posició. En aquesta suma amb finestra lliscant, la millora consisteix a actualitzar el resultat anterior sense recalcular tota la finestra.
| 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)$ |
| Patró contigu | Localitzar una seqüència d'elements consecutius | Patró no buit per a aquesta cota | $O(nm)$ |
| Finestra lliscant (suma) | Suma màxima de k elements consecutius | $1 ≤ k ≤ n$ | $O(n)$ |
| 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.