Sinteza Modulului 3 - Clasa X | Școala Româno-Britanică

DEFINIȚIILE CHEIE

Matricea

Definiție: Matricea este un model conceptual mixt de organizare a datelor, format dintr-un tabel cu m linii și n coloane. Practic, este o listă de liste: fiecare linie este o listă de valori.

Un element se accesează cu a[i][j], unde i este linia și j coloana. Declarare: int a[101][101]; pentru dimensiuni maximale de 100; dimensiunile reale se citesc la rulare.

Înțelege-l astfel: gândește-te la un catalog de clasă: rândurile sunt elevii (liniile), coloanele sunt disciplinele, iar fiecare căsuță a[i][j] este nota elevului i la disciplina j. Indicele i se schimbă cel mai „încet" (bucla exterioară), iar j cel mai „repede" (bucla interioară) - de aceea citirea și afișarea pe linii sunt naturale.

Parcurgerea matricei

Definiție: A parcurge matricea înseamnă a vizita fiecare element exact o dată, folosind două bucle for imbricate: bucla exterioară parcurge liniile (i), bucla interioară coloanele (j). Prelucrările de bază: suma elementelor, minimul și maximul, numărarea elementelor cu o proprietate.

Zonele unei matrice pătrate: diagonala principală i == j, diagonala secundară i + j == n + 1, deasupra diagonalei principale i < j, sub diagonală i > j.

Lista sortată și căutarea binară

Definiție: O listă sortată este un tablou în care fiecare element este mai mic sau egal cu următorul: a[i] <= a[i + 1]. Căutarea binară este algoritmul de căutare pe listă sortată care, la fiecare pas, înjumătățește intervalul de căutare comparând valoarea căutată cu elementul din mijloc. Complexitate: O(log2 n).

Înțelege-l astfel: exact ca atunci când cauți un cuvânt în dicționar: deschizi la mijloc și, dacă cuvântul căutat este înainte, arunci jumătatea din dreapta. După fiecare comparație rămâi cu jumătate din interval, deci după log2 n pași ai ajuns la un singur element. Reține: condiția buclei este st <= dr, iar indicii se actualizează cu mij + 1 și mij - 1.

Interclasarea și fuzionarea

Definiție: Interclasarea combină două liste sortate într-o singură listă sortată, parcurgându-le simultan și alegând mereu elementul mai mic. Complexitate: O(n + m). Fuzionarea este interclasarea care elimină dublurile: la egalitate, valoarea se copiază o singură dată și se avansează ambii indici.

Înțelege-l astfel: imaginează-ți două cozi sortate de elevi care trebuie unite într-o singură coadă sortată: la fiecare pas vine în față elevul cu numărul mai mic dintre cei doi de la capete. Când o coadă se golește, restul celeilalte trece direct în rezultat. De aceea avem trei indici: i (prima listă), j (a doua listă) și k (lista rezultat).

ALGORITMII PRINCIPALI - PSEUDOCOD ȘI COD C++

Algoritmul 1: citirea și prelucrarea matricei

Algoritmul PrelucrareMatrice(m, n): pentru i = 1, m execută pentru j = 1, n execută citește a[i][j] sfârșit pentru sfârșit pentru s <- 0 maxi <- a[1][1] pentru i = 1, m execută pentru j = 1, n execută s <- s + a[i][j] dacă a[i][j] > maxi atunci maxi <- a[i][j] sfârșit dacă sfârșit pentru sfârșit pentru scrie s, maxi

Suma și maximul unei matrice

int s = 0, maxi = a[1][1];
for (i = 1; i <= m; i++)
    for (j = 1; j <= n; j++) {
        s = s + a[i][j];
        if (a[i][j] > maxi)
            maxi = a[i][j];
    }

De reținut: suma se inițializează cu 0, maximul cu primul element a[1][1]. Pentru diagonala principală se folosește a[i][i], iar pentru zona de deasupra diagonalei, j de la i + 1 la n.

Algoritmul 2: căutarea binară

Algoritmul CăutareBinară(a, n, x): st <- 1, dr <- n, poz <- 0 cât timp st <= dr execută mij <- (st + dr) / 2 dacă a[mij] = x atunci poz <- mij oprește bucla altfel dacă a[mij] < x atunci st <- mij + 1 altfel dr <- mij - 1 sfârșit dacă sfârșit cât timp dacă poz = 0 atunci scrie -1 altfel scrie poz sfârșit dacă

Căutarea binară a lui x

st = 1;
dr = n;
poz = 0;
while (st <= dr) {
    mij = (st + dr) / 2;
    if (a[mij] == x) {
        poz = mij;
        break;
    } else if (a[mij] < x) {
        st = mij + 1;
    } else {
        dr = mij - 1;
    }
}
if (poz == 0)
    cout << -1;
else
    cout << poz;

De reținut: variantele pentru prima apariție (condiția >=, continuăm spre stânga) și ultima apariție (condiția <=, continuăm spre dreapta). Numărul de elemente mai mici decât x este poz - 1, unde poz este prima poziție cu valoarea >= x.

Algoritmul 3: interclasarea

Algoritmul Interclasare(a, b, n, m): i <- 1, j <- 1, k <- 0 cât timp i <= n și j <= m execută dacă a[i] <= b[j] atunci k <- k + 1 c[k] <- a[i] i <- i + 1 altfel k <- k + 1 c[k] <- b[j] j <- j + 1 sfârșit dacă sfârșit cât timp cât timp i <= n execută k <- k + 1 c[k] <- a[i] i <- i + 1 sfârșit cât timp cât timp j <= m execută k <- k + 1 c[k] <- b[j] j <- j + 1 sfârșit cât timp scrie c[1..k]

Interclasarea lui a și b în c

i = 1;
j = 1;
k = 0;
while (i <= n && j <= m) {
    k++;
    if (a[i] <= b[j]) {
        c[k] = a[i];
        i++;
    } else {
        c[k] = b[j];
        j++;
    }
}
while (i <= n) { k++; c[k] = a[i]; i++; }
while (j <= m) { k++; c[k] = b[j]; j++; }

De reținut: la fuzionare, cazul a[i] == b[j] se tratează separat: copiem o singură dată și avansăm ambii indici. Dacă se cere doar numărul de valori distincte, numărăm cu k fără a construi tabloul c.

Algoritmul 4: verificarea unei liste sortate

Verificăm dacă o listă este sortată crescător cu o singură parcurgere: lista nu este sortată dacă găsim un a[i] > a[i + 1]. Nu ai nevoie de două bucle - complexitatea este O(n).

Verificarea sortării în O(n)

bool sortata = true;
for (i = 1; i < n; i++)
    if (a[i] > a[i + 1]) {
        sortata = false;
        break;
    }
cout << (sortata ? "DA" : "NU");

Algoritmul 5: prima apariție (căutare binară adaptată)

Pentru prima apariție a lui x căutăm prima poziție cu a[poz] >= x: când găsim egalitate, reținem poziția și continuăm spre stânga (dr = mij - 1). Dacă la final a[poz] != x, valoarea nu există.

Prima apariție a lui x

st = 1; dr = n; poz = n + 1;
while (st <= dr) {
    mij = (st + dr) / 2;
    if (a[mij] >= x) {
        poz = mij;
        dr = mij - 1;
    } else {
        st = mij + 1;
    }
}
if (poz <= n && a[poz] == x)
    cout << poz;
else
    cout << -1;

TABELE RECAPITULATIVE - COMPLEXITĂȚI

Complexitățile algoritmilor modulului

Algoritm / structură	Date de intrare	Complexitate	Condiție de aplicare
Parcurgerea matricei	matrice m x n	O(m * n)	oricare matrice
Diagonalele matricei	matrice pătrată n x n	O(n)	m == n
Verificarea sortării	listă cu n elemente	O(n)	oricare listă
Căutarea binară	listă sortată cu n elemente	O(log2 n)	listă sortată
Prima / ultima apariție	listă sortată cu n elemente	O(log2 n)	listă sortată
Interclasarea	două liste sortate (n și m)	O(n + m)	ambele liste sortate
Fuzionarea	două liste sortate (n și m)	O(n + m)	ambele liste sortate
Sortarea prin selecție	listă cu n elemente	O(n^2)	oricare listă

Observă: odată ce datele sunt sortate, toate prelucrările devin rapide: căutare în log2 n pași, combinare liniară. De aceea „sortarea datelor" este prima întrebare pe care ți-o pui la o problemă cu restricții mari.

Câte operații facem practic?

Dimensiune date	Căutare secvențială	Căutare binară	Interclasare (2 liste)
n = 1000	până la 1000 pași	aproximativ 10 pași	2000 de pași
n = 100000	până la 100000 pași	aproximativ 17 pași	200000 de pași
n = 1000000	până la 1000000 pași	aproximativ 20 de pași	2000000 de pași

COMPARAȚII IMPORTANTE

Căutare secvențială vs căutare binară

Criteriu	Căutare secvențială	Căutare binară
Condiție de aplicare	oricare tablou, sortat sau nu	DOAR tablou sortat
Complexitate	O(n) - verifică element cu element	O(log2 n) - înjumătățește intervalul
Când o alegi	tablou mic sau nesortat, o singură căutare	tablou mare și sortat, mai multe căutări
Implementare	o singură buclă for, simplă	bucle while cu st, dr, mij - mai atentă la condiții

Regula practică: dacă datele sunt deja sortate, folosește întotdeauna căutarea binară. Dacă ar trebui să sortezi doar ca să cauți o singură valoare, compară costurile: sortarea O(n^2) plus căutarea binară O(log2 n) este mai scumpă decât o singură căutare secvențială O(n).

Interclasare vs sortare

Criteriu	Interclasare	Sortare
De unde pornește	două liste deja sortate	o singură listă nesortată
Complexitate	O(n + m) - liniară, foarte rapidă	O(n^2) la selecție / inserție (stil BAC)
Ce obține	o listă rezultat, sortată, cu toate elementele	aceeași listă, ordonată
Când o folosești	două șiruri sortate care trebuie combinate	un singur șir care trebuie ordonat

Observație: interclasarea este „mai ieftină" decât sortarea pentru că profită de faptul că listele sunt deja ordonate. De aceea, la problemele care dau două liste sortate, interclasarea este răspunsul corect - nu sortarea tuturor elementelor.

CE TREBUIE SĂ ȘTII PENTRU TEST

Lista de verificare pentru test

Matricea: declară int a[101][101]; (dimensiune maximă + 1 pentru indexarea de la 1), citește și afișează cu două bucle for, suma cu 0, maximul cu a[1][1].
Diagonalele: principală a[i][i], secundară a[i][n + 1 - i], formula i + j == n + 1.
Lista sortată: definiția a[i] <= a[i + 1] și verificarea într-o singură parcurgere.
Căutarea binară: condiția st <= dr, mijlocul (st + dr) / 2, actualizarea cu mij + 1 și mij - 1, complexitatea O(log2 n).
Prima / ultima apariție: după găsire, continui spre stânga (condiția >=) sau spre dreapta (condiția <=).
Interclasarea: indicii i = 1, j = 1, k = 0, alegerea minimului, apoi cele două bucle de copiere a restului, complexitatea O(n + m).
Fuzionarea: la a[i] == b[j] copiezi o singură dată și avansezi ambii indici.
Eficiență: pentru fiecare algoritm știi complexitatea și condiția de aplicare - sunt cerute explicit la subiectul de teorie.
Afișare: exact formatul din enunț: spații între valori, endl la sfârșitul liniilor, verdictul cerut („DA"/„NU", -1).

EXERCIȚII DE RECAPITULARE

Mini-provocare 1: rulează căutarea binară pe hârtie

Tabloul a = [2, 5, 8, 12, 17, 21, 24] (7 elemente, indexare de la 1) și valoarea x = 17. Notează pe hârtie valorile lui st, dr și mij la fiecare pas, până la găsirea lui 17. Câte comparații faci?

Pasul 1: st=1, dr=7  -> mij=4, a[4]=12 < 17 -> st=5
Pasul 2: st=5, dr=7  -> mij=6, a[6]=21 > 17 -> dr=5
Pasul 3: st=5, dr=5  -> mij=5, a[5]=17 == 17 -> poz=5

Răspuns: 17 se află pe poziția 5, în doar 3 comparații
(față de 5 comparații la căutarea secvențială).

Mini-provocare 2: interclasează pe hârtie

Interclasează a = [1, 4, 6] și b = [2, 3, 5]. Scrie lista rezultat c, element cu element, urmărind indicii i, j și k. Verifică apoi că rezultatul este sortat.

i=1,j=1: 1 < 2   -> c[1]=1, i->2
i=2,j=1: 4 > 2   -> c[2]=2, j->2
i=2,j=2: 4 > 3   -> c[3]=3, j->3
i=2,j=3: 4 < 5   -> c[4]=4, i->3
i=3,j=3: 6 > 5   -> c[5]=5, j->4 (b se epuizează)
i=3 (a mai are un element) -> c[6]=6

Răspuns: c = [1, 2, 3, 4, 5, 6]

Mini-provocare 3: suma deasupra diagonalei principale

Pentru o matrice pătrată n x n, scrie buclele (sau condiția din bucla interioară) care calculează suma elementelor strict deasupra diagonalei principale, fără a atinge diagonala.

// Varianta 1: limite directe în bucle
s = 0;
for (i = 1; i <= n; i++)
    for (j = i + 1; j <= n; j++)   // j pornește de la i+1
        s = s + a[i][j];

// Varianta 2: condiție în bucla interioară
for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++)
        if (j > i)                  // strict deasupra diagonalei
            s = s + a[i][j];

GREȘELI FRECVENTE LA TEST

Greșeli frecvente la test

Condiția st < dr în loc de st <= dr la căutarea binară: elementul dintr-un interval cu un singur element nu mai este verificat.
st = mij sau dr = mij: intervalul nu se reduce și apare buclă infinită. Corect: st = mij + 1, dr = mij - 1.
Diagonala secundară cu i + j == n: corect este n + 1 la indexarea de la 1.
Maximul sau minimul inițializat cu 0: la valori negative (sau pozitive, în funcție de caz) rezultatul este greșit; inițializează cu a[1][1].
Lipsa buclelor de copiere a restului la interclasare: rezultatul devine incomplet, fără nicio eroare de compilare.
Fuzionare scrisă ca interclasare simplă: dublurile nu se elimină, iar enunțul cu „distincte" este nerespectat.
Afișarea valorii în locul poziției: la căutare se cere indicele, nu elementul găsit.
Indexarea de la 0: la BAC se lucrează de la 1; declară tablourile cu un loc în plus (a[100005] pentru 100000 de valori).

REGLI ȘI GREȘELI FRECVENTE

Regulile de aur ale modulului

Citește enunțul de două ori: „distincte" înseamnă fuzionare, „toate elementele" înseamnă interclasare, „poziția" înseamnă căutare.
Verifică dacă datele sunt sortate înainte de a aplica căutarea binară sau interclasarea.
Indexează de la 1 și declară tablourile cu un loc în plus: a[100005] pentru 100000 de valori.
Inițializează corect: suma cu 0, contorul cu 0, maximul cu a[1][1], poz cu n + 1 la numărarea elementelor mai mici.
Afișează în formatul cerut: valori separate prin spații, endl după fiecare linie, verdictul exact („DA"/„NU", -1).
Verifică cele trei cazuri de aur: date minime (n = 1), date maxime și rezultat absent.

Greșelile frecvente de evitat la test

Condiția buclei st < dr în loc de st <= dr: intervalul cu un singur element nu mai este verificat.
Actualizarea indicilor cu st = mij sau dr = mij: risc de buclă infinită; folosește mij + 1 și mij - 1.
Diagonala secundară scrisă i + j == n: corect este i + j == n + 1.
Maximul inițializat cu 0: greșit la matrice cu valori negative; folosește a[1][1].
Uitarea buclelor de copiere a restului la interclasare: jumătate din rezultat dispare.
Inițializarea lui k cu 1 la interclasare: primul element al rezultatului se pierde.
Verificarea sortării în O(n^2): o singură parcurgere cu a[i] <= a[i + 1] este suficientă.
Sortarea în loc a matricei când se cere doar afișarea unei zone sortate: lucrează pe un vector de lucru.

Verificarea rapidă înainte de predare

Lista de control pentru orice program:

Am citit toate datele de intrare, în ordinea din enunț?
Am declarat tablourile cu dimensiune suficientă, cu loc pentru indexarea de la 1?
Am inițializat corect sumele, contoarele, maximul/minimul și pozițiile?
Am ales algoritmul potrivit tipului de date (matrice, listă sortată, două liste sortate)?
Am tratat toate cazurile particulare (listă goală, valoare inexistentă, matrice cu o linie)?
Afișarea respectă formatul cerut: spații, linii noi, mesaje exacte?

Sinteza Modulului 3: Modele mixte și liste sortate