Algoritmi fundamentali de prelucrare a datelor structurate în tablouri
Algoritmi de căutare
Căutare secvențială (vector nesortat)
Se parcurge fiecare element din vector comparându-l cu elementul căutat, oprindu-se când îl găsește.
gasit ← 0
pentru i ← 1, n execută
dacă v[i] = x atunci
gasit ← 1
Căutare binară (vector sortat)
Se utilizează împărțirea intervalului de căutare în jumătate, repetând procesul până la găsirea elementului.
li ← 1, ls ← n, gasit ← 0
cât timp li ≤ ls și gasit = 0 execută
mij ← (li + ls) / 2
dacă v[mij] = x atunci
gasit ← 1
altfel dacă x < v[mij] atunci
ls ← mij - 1
altfel
li ← mij + 1
Algoritmi de sortare
Sortare prin selecție directă
Selectează cel mai mic element din partea nesortată și îl plasează în partea sortată a vectorului.
pentru i ← 1, n-1 execută
min ← i
pentru j ← i+1, n execută
dacă v[j] < v[min] atunci
min ← j
interschimbă v[i], v[min]
Sortare prin metoda bulelor
Compară perechi de elemente vecine și le interschimbă dacă sunt în ordine greșită.
sortat ← 0
cât timp sortat = 0 execută
sortat ← 1
pentru i ← 1, n-1 execută
dacă v[i] > v[i+1] atunci
interschimbă v[i], v[i+1]
sortat ← 0
Interclasare
Combină două tablouri sortate într-un singur tablou sortat.
i ← 1, j ← 1, k ← 0
cât timp i ≤ m și j ≤ n execută
k ← k + 1
dacă a[i] < b[j] atunci
c[k] ← a[i]; i ← i + 1
altfel
c[k] ← b[j]; j ← j + 1
cât timp i ≤ m execută
k ← k + 1; c[k] ← a[i]; i ← i + 1
cât timp j ≤ n execută
k ← k + 1; c[k] ← b[j]; j ← j + 1
Prelucrări specifice tablourilor bidimensionale
Exemplu: Calculul sumei elementelor fiecărei linii dintr-o matrice.
pentru i ← 1, n execută
suma ← 0
pentru j ← 1, m execută
suma ← suma + a[i][j]
scrie suma
Aplicații practice detaliate și metode de rezolvare
- Gestionarea notelor elevilor: Medii, maxim/minim calculabile prin algoritmi de sortare și căutare secvențială.
- Analiza temperaturilor: Sortare și căutare pentru determinarea extremelor și tendințelor.
- Gestiunea prețurilor produselor: Sortarea listelor și interclasarea cataloagelor pentru organizare eficientă.
- Clasamente sportive: Sortare rapidă și actualizare a pozițiilor în clasament.
- Prezență școlară: Contorizarea zilnică și generarea rapoartelor prin algoritmi de sumă și numărare în matrice.
Exerciții propuse și metode de rezolvare
- Nota maximă și minimă pentru fiecare elev: Folosește căutarea secvențială.
- Sortarea produselor după preț: Aplică sortarea prin selecție directă.
- Temperatura extremă: Utilizare algoritm de căutare secvențială.
- Interclasarea listelor: Folosirea algoritmului de interclasare detaliat.
- Prezența zilnică: Prelucrare matriceală pentru contorizarea prezențelor și absențelor.