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

Ora 9: Recapitulare și test

Ce vei învăța astăzi: Recapitularea matricei, a căutării binare și a interclasării, test final

Rezultat practic: Rezolvi independent probleme care combină matricea și listele sortate în C++, verificând toate competențele modulului (Competența 6.4).

Competența 6.4 Săptămâna 16

Înainte de a începe

De ce contează? Recapitularea îți arată exact ce se cere la test: alegerea algoritmului potrivit tipului de date, complexitatea corectă și formatul exact de afișare - adică baremul după care ești notat.

Ce știi deja?

Ai parcurs toate lecțiile: matricea, diagonalele, căutarea binară, interclasarea (combinarea a două liste sortate într-o singură listă sortată), fuzionarea (interclasarea care elimină valorile repetate). Acum le pui cap la cap pe un singur test. Poți spune din memorie complexitatea fiecărui algoritm și condiția lui de aplicare?

Ideea-cheie: Tabelul rezumativ este harta testului: pentru fiecare problemă identifici structura datelor (matrice, listă sortată, două liste sortate) și alegi algoritmul cu complexitatea potrivită.
SINTEZĂ TEORETICĂ ȘI EXEMPLE GHIDATE

Ce vei învăța astăzi?

După această lecție vei recapitula tot modulul: matricea și prelucrările ei, căutarea binară și interclasarea, apoi vei rezolva un test final.

Recapitularea matricei și a listelor sortate
Tabelul rezumativ al algoritmilor
Căutare binară și interclasare
Test final de verificare a modulului

Tabel rezumativ al modulului

Structură / algoritm Idee principală Complexitate Exemplu de cod
Matricea tabel cu m linii și n coloane parcurgere O(m * n) a[i][j], două bucle for
Diagonala principală elementele cu i == j O(n) a[i][i]
Căutarea binară tablou sortat, împărțire în jumătăți (reducerea la fiecare pas a zonei căutate la jumătate) O(log2 n) st, dr, mij
Interclasarea două liste sortate, alegem minimul O(n + m) i, j, k

Recapitulare: căutarea binară și interclasarea

Căutarea binară găsește rapid o valoare într-o listă sortată, iar interclasarea combină două liste sortate într-una singură, tot sortată. Ambele se bazează pe faptul că datele sunt sortate.

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 și caută 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];

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

Observă: după interclasare, tabloul c este sortat, deci putem căuta x în el cu căutare binară, în O(log2(n + m)).

Recapitulare: matricea

La matrice combinăm parcurgerea cu două bucle, prelucrarea diagonalelor și determinarea maximului cu poziție.

Program complet: maximul de pe diagonala principală
#include <iostream>
using namespace std;

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

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

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

    cout << maxi;
    return 0;
}

Observă: pentru diagonala principală parcurgem doar elementele a[i][i], cu un singur indice.

Exercițiu de completare

Completează enunțul cu cuvintele potrivite:

Căutarea binară necesită o listă ______. Interclasarea primește două liste ______ și produce o listă ______.

Bancă de cuvinte:
sortată sortate aleatoare goală

Exercițiu de completare 2

Completează afirmațiile despre matrice:

Suma elementelor de pe diagonala principală folosește condiția ______. Poziția unui element în matrice este dată de linie și ______.

Bancă de cuvinte:
i == j coloană i > j diagonală

Test de înțelegere

Test rapid - recapitulare:

1. Complexitatea căutării binare într-o listă cu n elemente este:

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

3. Pentru a găsi maximul dintr-o matrice, trebuie să parcurgem:

Ai grijă la: „poziția" cerută de enunț nu înseamnă valoarea: la căutare trebuie afișat indicele, nu elementul găsit - o confuzie care costă puncte la aproape fiecare test.

Aprofundare

Cum se combină corect interclasarea cu căutarea binară? Cheia este ordinea operațiilor: interclasarea produce o listă c sortată, deci căutarea binară se poate aplica imediat, fără nici o sortare suplimentară. Dacă am sorta din nou rezultatul, am distruge avantajul de eficiență - interclasarea este liniară (O(n + m)), iar căutarea binară logaritmică (O(log2(n + m))). Un program „naiv" care sortează cele două liste apoi caută secvențial ar costa O((n + m)^2) - de milioane de ori mai mult pentru date mari.

Recapitularea condițiilor de aplicare - test rapid de memorie:

  • Căutarea binară cere listă sortată; altfel răspunsul poate fi greșit.
  • Interclasarea cere două liste sortate și produce o listă sortată.
  • Verificarea sortării este O(n) - o singură parcurgere, cu a[i] <= a[i + 1].
  • Diagonala principală: i == j; deasupra: i < j; sub: i > j.

Cazuri particulare de la evaluare (situații speciale la marginile datelor de intrare, de exemplu liste goale sau valori inexistente): dacă una dintre liste este goală, interclasarea copiază întreaga listă rămasă (buclele while de rest acoperă automat acest caz). Dacă x nu există în rezultat, căutarea binară se termină cu st > dr și afișăm -1. Dacă x apare de mai multe ori, varianta cu break afișează o poziție oarecare a sa - pentru prima apariție exactă se folosește varianta „primă poziție cu >= x" de la ora 5.

Înainte de evaluare, verifică mereu: inițializarea sumelor și contoarelor, dimensiunile tablourilor (cu un loc în plus pentru indexarea de la 1), afișarea cu spații și endl, și citirea atentă a enunțului pentru a alege între interclasare (cu dubluri) și fuzionare (fără dubluri).

APLICARE ȘI REZOLVARE DE PROBLEME

PbInfo - Căutare binară (test final)

Enunț:

Cerință: Se dă un tablou cu n numere naturale, sortat crescător, și o valoare x. Să se afișeze poziția 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 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:

5
2 4 6 8 10
8

Ieșire:

4
Cum gândim soluția:
  1. Inițializăm st = 1 și dr = n
  2. Repetăm cât timp st <= dr, calculând mij
  3. Comparăm a[mij] cu x și micșorăm intervalul
  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;
            break;
        } else if (a[mij] < x) {
            st = mij + 1;
        } else {
            dr = mij - 1;
        }
    }

    if (poz == 0)
        cout << -1;
    else
        cout << poz;
    return 0;
}

Ce învățăm: recapitulăm algoritmul clasic al căutării binare, cu indicii st, dr și mij.

PbInfo - Interclasare (test final)

Enunț:

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

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 cele n + m valori, în ordine crescătoare, separate prin spații.

Restricții și precizări:

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

Exemplu:

Intrare:

3
1 3 5
3
2 4 6

Ieșire:

1 2 3 4 5 6
Cum gândim soluția:
  1. Citim cele două șiruri sortate
  2. Folosim indicii i, j pentru cele două șiruri și k pentru rezultat
  3. Copiem elementul mai mic, apoi restul din șirul neepuizat
  4. Afișăm tabloul rezultat
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;
    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++;
    }

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

Ce învățăm: recapitulăm interclasarea cu trei indici: copiem elementul mai mic, apoi restul din lista rămasă.

EXERCIȚII PRACTICE

Exercițiul Practic: Test final al modulului

Sarcini de lucru

Rezolvă cele două sarcini finale pentru a verifica tot ce ai învățat în modul

Sarcina 1: Maximul de pe diagonala principală

Cerință: Scrie un program C++ care citește o matrice pătrată cu n linii și coloane și afișează valoarea maximă dintre elementele de pe diagonala principală.

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

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

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

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

    cout << maxi;
    return 0;
}

Verifică: pe diagonala principală accesăm elementele a[i][i] și le comparăm cu maximul.

Sarcina 2: Suma elementelor din interclasare

Cerință: Scrie un program C++ care citește două șiruri sortate, le interclasează în tabloul c și afișează suma tuturor elementelor rezultate.

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

int main() {
    int n, m, a[100005], b[100005], c[200005], i, j, k;
    long long s = 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;
    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++;
    }

    for (i = 1; i <= k; i++)
        s = s + c[i];

    cout << s;
    return 0;
}

Verifică: după interclasare adunăm toate elementele din tabloul rezultat; folosim long long pentru sume mari.

Scrie pe caiet - De reținut

Titlul lecției

Ora 9: Recapitulare și test

Definiția lecției

Recapitularea reunește tot modulul: matricea cu prelucrările ei, diagonalele, căutarea binară, interclasarea și fuzionarea. Matricea este un tabel cu m linii și n coloane, accesat cu a[i][j], cu diagonalele i == j, respectiv i + j == n + 1. Căutarea binară lucrează pe o listă sortată, cu indicii st, dr și mij, și are complexitatea O(log2 n). Interclasarea combină două liste sortate într-una singură, sortată, cu indicii i, j și k, în O(n + m). Fuzionarea este interclasarea care elimină dublurile, avansând ambii indici la egalitate. Ordinea corectă într-o problemă combinată este: interclasare, apoi căutare binară în rezultatul sortat. La test se punctează și condițiile de aplicare ale algoritmilor, nu doar codul.

Definiții esențiale

  • Matricea: tabel cu m linii și n coloane, accesat cu a[i][j]; diagonala principală i == j, secundară i + j == n + 1.
  • Căutarea binară: algoritm pe listă sortată, complexitate O(log2 n), indicii st, dr, mij.
  • Interclasarea: combină două liste sortate într-una singură sortată, complexitate O(n + m), indicii i, j, k.
  • Fuzionarea: interclasarea care elimină dublurile (la egalitate avansăm ambii indici).

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 și nu gasit 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

  • Uitarea copierii restului după interclasare: jumătate din rezultat dispare.
  • Căutarea binară pe o listă nesortată: răspuns greșit, deși programul rulează.
  • Inițializarea sumei sau a contorului în interiorul buclei: rezultate complet greșite.

Exemplu practic

Două clase au publicat, fiecare, listele elevilor admiși la olimpiadă, sortate după numărul matricol. Coordonatorul vrea o singură listă, sortată, și verifică apoi dacă elevul cu numărul x este în ea. Programul interclasează cele două liste, apoi caută binar valoarea x în rezultatul sortat.

Interclasare, apoi căutare binară î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];

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

Dacă lista interclasată conține 6 elevi și x = 4, căutarea binară îl găsește în cel mult 3 comparații, fără a mai sorta nimic după interclasare.

Sfaturi practice și trucuri

  • Rezolvă întâi problema pe hârtie cu un exemplu mic, apoi scrie codul.
  • Verifică dimensiunile tablourilor: a[100005], b[100005], c[200005].
  • La test, citește enunțul de două ori: „distincte" înseamnă fuzionare, „toate elementele" înseamnă interclasare.