Școala Româno-Britanică
Modulul 3 Clasa a X-a | C++

Ora 11: Recapitulare generală

Ce vei învăța astăzi: Să recapitulăm întregul modul: matricea cu prelucrările ei, căutarea binară, interclasarea (combinarea a două liste sortate într-o singură listă sortată) și fuzionarea (interclasarea care elimină valorile repetate), prin tabel rezumativ și programe complete

Rezultat practic: Consolidezi toate competențele modulului, rezolvând programe C++ complete care acoperă matricea și listele sortate (Competența 5.2).

Competența 5.2 Săptămâna 17

Înainte de a începe

De ce contează? Înaintea evaluării finale, recapitularea generală îți consolidează imaginea completă: toți algoritmii modulului, cu complexitățile și condițiile lor de aplicare, strânși pe o singură pagină.

Ce știi deja?

Ai toate lecțiile parcurse, inclusiv aplicațiile integrate de la ora 10. Ora aceasta este momentul în care se leagă totul înaintea evaluării finale. Poți enumera algoritmii modulului fără să te uiți în caiet?

Ideea-cheie: Fiecare algoritm din modul are o condiție de aplicare (situația în care poate fi folosit corect): matricea pentru date în tabel, căutarea binară pentru o listă sortată, interclasarea pentru două liste sortate - alegerea corectă a algoritmului rezolvă jumătate din problemă.
SINTEZĂ TEORETICĂ ȘI EXEMPLE GHIDATE

Ce vei învăța astăzi?

După această lecție vei avea imaginea completă a modulului: vei recapitula matricea, căutarea binară, interclasarea și fuzionarea, cu tabelul rezumativ al algoritmilor și programe C++ complete.

Recapitularea lecțiilor modulului
Tabelul rezumativ al algoritmilor
Matricea: diagonale și prelucrări
Căutare binară, interclasare, fuzionare

Tabel rezumativ al modulului

Această lecție reunește toate lecțiile modulului, de la modelul conceptual mixt al matricei până la problemele integrate. Tabelul de mai jos este harta de navigare a modulului (rezumatul care arată legătura dintre toate lecțiile modulului): pentru fiecare structură sau algoritm găsești ideea principală, complexitatea și exemplul de cod.

Structură / algoritm Idee principală Complexitate Exemplu de cod
Matricea tabel cu m linii și n coloane, listă de liste parcurgere O(m * n) a[i][j], două bucle for
Diagonala principală elementele cu i == j O(n) a[i][i]
Diagonala secundară elementele cu i + j == n + 1 O(n) a[i][n + 1 - i]
Maximul cu poziție primul element + comparare O(m * n) maxi, lmax, cmax
Căutarea binară listă sortată, împărțire în jumătăți O(log2 n) st, dr, mij
Prima / ultima apariție prima poziție cu >= x, respectiv <= x O(log2 n) poz, mutarea indicilor
Interclasarea două liste sortate, alegem minimul O(n + m) i, j, k
Fuzionarea interclasare cu eliminarea dublurilor O(n + m) a[i] == b[j], avansăm ambii

Observă: toți algoritmii pe liste sortate au complexități mici; de aceea ordonarea datelor este „aur" în informatică - odată sortate, datele se caută și se combină aproape instant.

Recapitulare: matricea și prelucrările ei

Matricea se declară cu două dimensiuni, se citește cu două bucle for, iar prelucrările tipice sunt: suma elementelor, maximul cu poziția și diagonalele. La problemele combinate, o linie a matricei poate fi tratată ca o listă asupra căreia aplicăm algoritmi de căutare sau interclasare.

Program complet: suma deasupra diagonalei principale și maximul matricei
#include <iostream>
using namespace std;

int main() {
    int n, a[101][101], i, j, s = 0, maxi, lmax = 1, cmax = 1;
    cin >> n;

    // pasul 1: citim matricea pătrată
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            cin >> a[i][j];

    // pasul 2: suma elementelor deasupra diagonalei principale (i < j)
    for (i = 1; i <= n; i++)
        for (j = i + 1; j <= n; j++)
            s = s + a[i][j];

    // pasul 3: maximul matricei, cu prima apariție a poziției
    maxi = a[1][1];
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            if (a[i][j] > maxi) {
                maxi = a[i][j];
                lmax = i;
                cmax = j;
            }

    // pasul 4: afișăm rezultatele
    cout << s << endl;
    cout << maxi << " " << lmax << " " << cmax;
    return 0;
}

Observă: zona de deasupra diagonalei se parcurge direct cu j de la i + 1 la n - fără if, mai rapid și mai clar.

Recapitulare: căutarea binară, interclasarea și fuzionarea

Căutarea binară găsește rapid o valoare într-o listă sortată; interclasarea combină două liste sortate într-una singură; fuzionarea face același lucru eliminând dublurile. Programul următor le leagă pe toate: interclasează două liste sortate și caută binar o valoare în rezultat.

Algoritmul InterclasareȘiCăutareBinară(a, b, n, m, x): // pasul 1: citirea celor două liste sortate citește n și lista a citește m și lista b // pasul 2: interclasarea în lista c 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 // pasul 3: căutarea binară a lui x în lista c (sortată) citește x st <- 1, dr <- k, gasit <- fals cât timp st <= dr execută mij <- (st + dr) / 2 dacă c[mij] = x atunci gasit <- adevărat oprește bucla altfel dacă c[mij] < x atunci st <- mij + 1 altfel dr <- mij - 1 sfârșit dacă sfârșit cât timp // pasul 4: afișarea rezultatului dacă gasit atunci scrie mij altfel scrie -1 sfârșit dacă
Program complet: interclasează două liste sortate și caută binar x în rezultat
#include <iostream>
using namespace std;

int main() {
    int n, m, a[100005], b[100005], c[200005], x, i, j, k, st, dr, mij;
    bool gasit = false;
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> a[i];
    cin >> m;
    for (j = 1; j <= m; j++)
        cin >> b[j];

    // pasul 1: 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++;
    }

    // pasul 2: căutarea binară a lui x în c (lista este sortată)
    cin >> x;
    st = 1;
    dr = k;
    while (st <= dr) {
        mij = (st + dr) / 2;
        if (c[mij] == x) {
            gasit = true;
            break;
        } else if (c[mij] < x) {
            st = mij + 1;
        } else {
            dr = mij - 1;
        }
    }

    // pasul 3: afișăm rezultatul căutării
    if (gasit)
        cout << mij;
    else
        cout << -1;
    return 0;
}

Observă: interclasarea produce o listă sortată în O(n + m), deci căutarea binară se aplică imediat, în O(log2(n + m)) - cele două algoritme se „înțeleg" perfect.

Exercițiu de completare

Completează enunțul cu cuvintele potrivite:

Căutarea binară cere o listă ______ și are complexitatea ______. Interclasarea combină două liste sortate în ______.

Bancă de cuvinte:
sortată O(log2 n) O(n + m) O(n^2)

Exercițiu de completare 2

Completează afirmațiile despre matrice:

Elementele diagonalei principale îndeplinesc condiția ______. Fuzionarea elimină ______ din rezultat. Maximul matricei se inițializează cu ______.

Bancă de cuvinte:
i == j dublurile a[1][1] i + j == n

Test de înțelegere

Test rapid - recapitulare generală:

1. Elementele deasupra diagonalei principale îndeplinesc condiția:

2. La fuzionare, când a[i] == b[j]:

3. Interclasarea a două liste cu n și m elemente are complexitatea:

Ai grijă la: memorarea algoritmilor fără condiția lor de aplicare (situația în care algoritmul poate fi folosit corect): interclasarea pe liste nesortate sau căutarea binară pe date neordonate dau răspunsuri greșite, chiar dacă codul arată corect și compilează fără probleme.

Aprofundare

Cum construiești singur tabelul rezumativ al modulului? Pentru fiecare algoritm învățat, răspunde la trei întrebări: pe ce date se aplică? (matrice oarecare, listă sortată, două liste sortate), ce produce? (valoare, poziție, listă sortată) și cât costă? (complexitate). Acest exercițiu de sinteză este exact ce se verifică la evaluare și la susținerea proiectului.

Legătura dintre lecțiile modulului - un singur fir: matricea este o „colecție de liste" (ora 1-3); odată ce o linie a matricei este sortată, devine o „listă sortată" pe care se aplică căutarea binară (ora 4-5); două linii sortate se combină prin interclasare sau fuzionare (ora 6-7); iar problemele integrate le îmbină pe toate (ora 8-10). Dacă înțelegi acest fir, orice problemă nouă de la test devine o combinație de pași deja cunoscuți.

Capcane recurente de la testele de recapitulare:

  • Confuzia dintre interclasare (păstrează dublurile) și fuzionare (le elimină) - citește cuvintele enunțului.
  • Inițializarea sumelor cu valori greșite: suma cu 0, maximul cu primul element, contorul cu 0.
  • Declararea tablourilor fără locul în plus pentru indexarea de la 1: a[100005] pentru 100000 de valori.
  • Condiția buclei while (st <= dr) scrisă fără egalitate - intervalul cu un singur element nu mai este verificat.

Strategia pentru testul final: citește enunțul o dată în întregime, marchează structurile implicate (matrice, listă sortată, ambele), alege algoritmul potrivit pentru fiecare pas și scrie programul pas cu pas, verificând la final cazurile limită (matrice cu 1 linie, listă cu 1 element, valoare inexistentă).

APLICARE ȘI REZOLVARE DE PROBLEME

PbInfo - Recapitulare: căutare binară

Enunț:

Cerință: Se dă un tablou cu n numere naturale, sortat crescător, și o valoare x. Să se afișeze poziția primei apariții a lui x în tablou sau -1 dacă valoarea nu există.

Date de intrare:

Programul citește de la tastatură numărul n, apoi cele n valori sortate, apoi valoarea x.

Date de ieșire:

Programul va afișa poziția primei apariții a lui x (numerotată de la 1) sau -1.

Restricții și precizări:

1 <= n <= 100000, valorile sunt numere naturale sortate crescător.

Exemplu:

Intrare:

7
2 4 6 6 6 8 10
6

Ieșire:

3
Cum gândim soluția:
  1. Căutăm prima poziție cu a[poz] >= x
  2. Când găsim un element egal cu x, continuăm spre stânga (dr = mij - 1)
  3. Verificăm dacă pe poziția reținută există chiar x
  4. Afișăm poziția sau -1
Scrie soluția în C++:
Soluție corectă:
Soluția completă
#include <iostream>
using namespace std;

int main() {
    int n, a[100005], x, i, st, dr, mij, poz = 0;
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> a[i];
    cin >> x;

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

    if (poz != 0 && a[poz] == x)
        cout << poz;
    else
        cout << -1;
    return 0;
}

Ce învățăm: recapitulăm varianta „prima apariție" a căutării binare: condiția >= ne duce mereu spre stânga, iar verificarea finală confirmă prezența valorii.

PbInfo - Recapitulare: fuzionarea cu eliminarea dublurilor

Enunț:

Cerință: Se dau două șiruri de numere naturale, fiecare sortat crescător. Să se afișeze, în ordine crescătoare, elementele distincte obținute prin fuzionarea celor două șiruri.

Date de intrare:

Programul citește de la tastatură numărul n, apoi cele n valori ale primului șir, numărul m, apoi cele m valori ale celui de-al doilea șir.

Date de ieșire:

Programul va afișa valorile distincte, în ordine crescătoare, separate prin spații.

Restricții și precizări:

1 <= n, m <= 100000, valorile sunt numere naturale.

Exemplu:

Intrare:

4
1 2 2 5
3
2 3 4

Ieșire:

1 2 3 4 5
Cum gândim soluția:
  1. Folosim indicii i, j pentru cele două șiruri și k pentru rezultat
  2. Când a[i] == b[j], copiem o singură dată și avansăm ambii indici
  3. Când valorile diferă, copiem valoarea mai mică
  4. Copiem restul din șirul neepuizat și afișăm rezultatul
Scrie soluția în C++:
Soluție corectă:
Soluția completă
#include <iostream>
using namespace std;

int main() {
    int n, m, a[100005], b[100005], c[200005], i, j, k = 0;
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> a[i];
    cin >> m;
    for (j = 1; j <= m; j++)
        cin >> b[j];

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

    for (i = 1; i <= k; i++)
        cout << c[i] << " ";
    return 0;
}

Ce învățăm: recapitulăm fuzionarea: la egalitate copiem valoarea o singură dată și avansăm ambii indici - exact diferența față de interclasarea clasică.

EXERCIȚII PRACTICE

Exercițiul Practic: Recapitulare completă a modulului

Sarcini de lucru

Rezolvă cele două sarcini de recapitulare, care acoperă matricea și listele sortate

Sarcina 1: Numărul de apariții ale maximului în matrice

Cerință: Scrie un program C++ care citește o matrice cu m linii și n coloane și afișează valoarea maximă a matricei și de câte ori apare aceasta în matrice.

Soluție pentru Sarcina 1:
#include <iostream>
using namespace std;

int main() {
    int m, n, a[101][101], i, j, maxi, cnt = 0;
    cin >> m >> n;

    for (i = 1; i <= m; i++)
        for (j = 1; j <= n; j++)
            cin >> a[i][j];

    maxi = a[1][1];
    for (i = 1; i <= m; i++)
        for (j = 1; j <= n; j++)
            if (a[i][j] > maxi)
                maxi = a[i][j];

    for (i = 1; i <= m; i++)
        for (j = 1; j <= n; j++)
            if (a[i][j] == maxi)
                cnt++;

    cout << maxi << " " << cnt;
    return 0;
}

Verifică: mai întâi determinăm maximul, apoi parcurgem din nou matricea numărând aparițiile - două parcurgeri distincte, fiecare cu rolul ei.

Sarcina 2: Câte valori din a sunt mai mici decât x

Cerință: Scrie un program C++ care citește un tablou sortat crescător cu n elemente și o valoare x, apoi afișează câte elemente din tablou sunt strict mai mici decât x, folosind căutarea binară.

Soluție pentru Sarcina 2:
#include <iostream>
using namespace std;

int main() {
    int n, a[100005], x, i, st, dr, mij, poz;
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> a[i];
    cin >> 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;
        }
    }

    cout << poz - 1;
    return 0;
}

Verifică: prima poziție cu valoare >= x împarte tabloul în două zone; elementele strict mai mici decât x sunt exact poz - 1 la număr.

Scrie pe caiet - De reținut

Titlul lecției

Ora 11: Recapitulare generală

Definiția lecției

Recapitularea generală reunește toate lecțiile modulului într-o singură imagine: matricea, diagonalele, căutarea binară, interclasarea și fuzionarea. Matricea este un tabel cu m linii și n coloane, cu diagonala principală i == j, diagonala secundară i + j == n + 1 și zonele deasupra (i < j) și sub diagonală (i > j). Căutarea binară are complexitatea O(log2 n) și necesită o listă sortată, folosind indicii st, dr și mij. Interclasarea combină două liste sortate într-una singură, sortată, în O(n + m), iar fuzionarea face același lucru eliminând dublurile. Verificarea sortării se face într-o singură parcurgere, O(n), cu condiția a[i] <= a[i + 1]. Firul care leagă toate lecțiile: o linie de matrice sortată devine o listă sortată, iar două liste sortate se combină prin interclasare.

Definiții esențiale

  • Matricea: tabel cu m linii și n coloane; diagonala principală i == j, secundară i + j == n + 1, deasupra i < j.
  • Căutarea binară: O(log2 n), necesită listă sortată, indicii st, dr, mij.
  • Interclasarea: O(n + m), combină două liste sortate; fuzionarea elimină dublurile.
  • Verificarea sortării: O(n), condiția a[i] <= a[i + 1].

Algoritmul cheie - pseudocod

Algoritmul InterclasareȘiCăutareBinară(a, b, n, m, x): citește n, a, m, b i <- 1, j <- 1, k <- 0 cât timp i <= n și j <= m execută dacă a[i] <= b[j] atunci c[k + 1] <- a[i], k <- k + 1, i <- i + 1 altfel c[k + 1] <- b[j], k <- k + 1, j <- j + 1 sfârșit dacă sfârșit cât timp cât timp i <= n execută c[k + 1] <- a[i], k <- k + 1, i <- i + 1 sfârșit cât timp cât timp j <= m execută c[k + 1] <- b[j], k <- k + 1, j <- j + 1 sfârșit cât timp citește x st <- 1, dr <- k, gasit <- fals cât timp st <= dr execută mij <- (st + dr) / 2 dacă c[mij] = x atunci gasit <- adevărat altfel dacă c[mij] < x atunci st <- mij + 1 altfel dr <- mij - 1 sfârșit dacă sfârșit cât timp dacă gasit atunci scrie mij altfel scrie -1 sfârșit dacă

Algoritmul cheie - cod C++

Interclasare + căutare binară
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++; }

st = 1; dr = k;
while (st <= dr) {
    mij = (st + dr) / 2;
    if (c[mij] == x) { poz = mij; break; }
    else if (c[mij] < x) st = mij + 1;
    else dr = mij - 1;
}

Greșeli comune de evitare

  • Interclasare vs. fuzionare: la fuzionare, egalitățile se copiază o singură dată.
  • Condiția st < dr în loc de st <= dr: intervalul de un element nu mai este verificat.
  • Diagonalele: secundară este i + j == n + 1, nu i + j == n.

Exemplu practic

La festivitatea de premiere, cele două clase au fiecare lista elevilor calificați, sortată după numărul matricol. Organizatorii unesc cele două liste prin interclasare, apoi verifică dacă elevul cu numărul x este în lista finală, folosind căutarea binară. Programul de mai jos leagă toți algoritmii modulului într-un singur program.

Interclasare și căutare binară în lista rezultat
#include <iostream>
using namespace std;

int main() {
    int n, m, a[100005], b[100005], c[200005], x, i, j, k, st, dr, mij;
    bool gasit = false;
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> a[i];
    cin >> m;
    for (j = 1; j <= m; j++)
        cin >> b[j];

    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++; }

    cin >> x;
    st = 1; dr = k;
    while (st <= dr) {
        mij = (st + dr) / 2;
        if (c[mij] == x) { gasit = true; break; }
        else if (c[mij] < x) st = mij + 1;
        else dr = mij - 1;
    }

    if (gasit)
        cout << mij;
    else
        cout << -1;
    return 0;
}

Pentru listele 1 2 5 și 3 4 6 și x = 4, programul afișează poziția lui 4 în lista interclasată, demonstrând legătura dintre interclasare și căutarea binară.

Sfaturi practice și trucuri

  • Învață tabelul rezumativ: algoritm, date de intrare, complexitate, exemplu de cod.
  • La probleme combinate, rezolvă pas cu pas: matrice -> listă -> algoritm pe listă.
  • Verifică întotdeauna cazurile limită: listă cu un element, valoare inexistentă, matrice cu o singură linie.