Maximul și poziția lui
Maximul si pozitia lui
#include <iostream>
using namespace std;
int main() {
int v[] = {5, 12, 3, 12, 7}, n = 5;
int maxim = v[0], poz = 0;
for (int i = 1; i < n; i++)
if (v[i] > maxim) {
maxim = v[i];
poz = i;
}
cout << maxim << " " << poz;
return 0;
}Atenție: Se retine prima pozitie a maximului, fiindca inegalitatea e stricta. Pascal indexeaza de la 1, de aceea pozitia se scade cu unu ca sa iasa acelasi raspuns.
Inițializezi cu PRIMUL element, nu cu 0 (vectorul poate avea doar valori negative).
Sortarea prin interschimbare (bubble sort)
Sortarea prin metoda bulelor
#include <iostream>
using namespace std;
int main() {
int v[] = {5, 2, 9, 1, 7}, n = 5;
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - i - 1; j++)
if (v[j] > v[j + 1]) {
int aux = v[j];
v[j] = v[j + 1];
v[j + 1] = aux;
}
for (int i = 0; i < n; i++) cout << v[i] << " ";
return 0;
}După fiecare trecere, cel mai mare element "se scufundă" la finalul zonei nesortate. Pentru descrescător, inversezi comparația (<).
Urmărire pe [3, 1, 2]: trecerea 1: (3,1)→schimb → [1,3,2]; (3,2)→schimb → [1,2,3]. Trecerea 2: (1,2) ok. Sortat. ✓
Căutarea
Liniară (vector oarecare): parcurgi și compari, O(n).
Cautarea secventiala
#include <iostream>
using namespace std;
int main() {
int v[] = {5, 2, 9, 1, 7}, n = 5, x = 9;
int gasit = 0;
for (int i = 0; i < n; i++)
if (v[i] == x) { gasit = 1; break; }
cout << gasit;
return 0;
}Atenție: Pascal nu are break in varianta standard de examen, de aceea conditia de oprire se pune chiar in while.
Binară (DOAR pe vector SORTAT): înjumătățești intervalul la fiecare pas, O(log n).
Cautarea binara
#include <iostream>
using namespace std;
int main() {
int v[] = {1, 3, 5, 7, 9, 11}, n = 6, x = 7;
int st = 0, dr = n - 1, gasit = 0;
while (st <= dr) {
int m = (st + dr) / 2;
if (v[m] == x) { gasit = 1; break; }
else if (v[m] < x) st = m + 1;
else dr = m - 1;
}
cout << gasit;
return 0;
}Atenție: Cautarea binara cere ca vectorul sa fie deja sortat. Pe un vector nesortat da raspunsuri gresite, desi ruleaza fara eroare.
Pentru x = 7 în [1, 3, 5, 7, 9]: m=2 (5<7) → st=3; m=3 (7=7) → găsit în 2 pași. ✓
Frecvența elementelor
Vectorul de frecvente
#include <iostream>
using namespace std;
int main() {
int v[] = {3, 7, 3, 1, 7, 3}, n = 6;
int fr[101] = {0};
for (int i = 0; i < n; i++)
fr[v[i]]++;
for (int val = 0; val <= 10; val++)
if (fr[val] > 0) cout << val << ":" << fr[val] << " ";
return 0;
}Atenție: Vectorul de frecvente se foloseste cand valorile sunt intregi si marginite. Indicele e chiar valoarea, de aceea trebuie sa incapa in vector.
Vectorul de frecvență: fr[x] = de câte ori apare x. Merge când valorile sunt mici (aici 0-100).
Reține
Căutarea binară cere vector SORTAT: pe vector nesortat dă rezultate greșite fără niciun mesaj de eroare. La BAC verifică întâi ipoteza de sortare.
Greșeli frecvente
- Maxim inițializat cu 0 în loc de v[0]: pică pe vectori cu numere negative.
- La bubble sort, limita interioară e n-i-1: fără -1 ieși din vector la v[j+1].
- La binară, actualizează st = m+1 / dr = m-1, nu st = m (buclă infinită).