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

Ora 8: Probleme integrate: matrice + liste sortate

Ce vei învăța astăzi: Combinarea matricei cu căutarea binară și interclasarea

Rezultat practic: Rezolvi o problemă integrată care folosește o matrice cu linii sortate și algoritmi pe liste sortate în C++ (Competența 5.2).

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

Înainte de a începe

De ce contează? Problemele reale de evaluare combină structuri: o matrice cu linii sortate leagă toate competențele modulului într-un singur program - exact nivelul cerut la evaluarea finală și la proiect.

Ce știi deja?

Știi parcurgerea matricei și prelucrările de bază (orele 1-2) și algoritmii pe liste sortate - căutarea binară și interclasarea (orele 4-6). Azi îi folosești împreună, pe aceleași date. Ce algoritm ai aplica pe o linie sortată a matricei?

Ideea-cheie: Decompoziția: verifică mai întâi care linii sunt sortate, apoi aplică pe ele căutarea binară sau interclasarea, pas cu pas, cu algoritmi deja cunoscuți - fiecare linie devine o listă pe care o prelucrezi separat.
SINTEZĂ TEORETICĂ ȘI EXEMPLE GHIDATE

Ce vei învăța astăzi?

După această lecție vei combina matricea cu listele sortate: vei verifica liniile sortate ale unei matrice (linii ale căror elemente sunt ordonate crescător), vei aplica căutarea binară pe linii (algoritmul de căutare prin înjumătățirea intervalului, aplicat separat pe fiecare linie) și vei interclasa liniile unei matrice.

Combinarea matricei cu listele sortate
Căutarea binară pe liniile matricei
Verificarea liniilor sortate
Interclasarea liniilor unei matrice

De ce combinăm structurile?

O matrice ale cărei linii sunt sortate crescător este un model mixt foarte folosit: pentru fiecare linie putem aplica algoritmi rapizi pe liste sortate, precum căutarea binară sau interclasarea.

Exemplu: numărăm liniile sortate ale unei matrice

Program complet
#include <iostream>
using namespace std;

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

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

    for (i = 1; i <= m; i++) {
        sortat = true;
        for (j = 1; j < n; j++)
            if (a[i][j] > a[i][j + 1])
                sortat = false;
        if (sortat)
            cnt++;
    }

    cout << cnt;
    return 0;
}

Observă: pentru fiecare linie i verificăm condiția a[i][j] <= a[i][j + 1] pe toate coloanele j.

Căutarea binară pe fiecare linie

Dacă liniile matricei sunt sortate, putem căuta o valoare x aplicând căutarea binară pe fiecare linie, în loc să parcurgem toată matricea.

Algoritmul CăutareBinarăPeLinii(a, m, n, x): // pasul 1: citim matricea cu liniile sortate pentru i = 1, m execută pentru j = 1, n execută citește a[i][j] sfârșit pentru sfârșit pentru citește x // pasul 2: căutăm x pe fiecare linie, binar gasit <- fals i <- 1 cât timp i <= m și nu gasit execută st <- 1 dr <- n cât timp st <= dr execută mij <- (st + dr) / 2 dacă a[i][mij] = x atunci gasit <- adevărat oprește bucla altfel dacă a[i][mij] < x atunci st <- mij + 1 altfel dr <- mij - 1 sfârșit dacă sfârșit cât timp i <- i + 1 sfârșit cât timp // pasul 3: afișăm rezultatul dacă gasit atunci scrie "DA" altfel scrie "NU" sfârșit dacă
Program complet: verifică dacă x apare în cel puțin o linie sortată
#include <iostream>
using namespace std;

int main() {
    int m, n, a[101][101], x, i, j, st, dr, mij;
    bool gasit = false;
    cin >> m >> n;

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

    for (i = 1; i <= m && !gasit; i++) {
        st = 1;
        dr = n;
        while (st <= dr) {
            mij = (st + dr) / 2;
            if (a[i][mij] == x) {
                gasit = true;
                break;
            } else if (a[i][mij] < x) {
                st = mij + 1;
            } else {
                dr = mij - 1;
            }
        }
    }

    if (gasit)
        cout << "DA";
    else
        cout << "NU";
    return 0;
}

Observă: bucla exterioară parcurge liniile, iar pe fiecare linie aplicăm căutarea binară cu a[i][mij]. Ne oprim la prima linie în care găsim valoarea.

Interclasarea liniilor matricei

Fiind date două linii sortate ale matricei, le putem interclasa într-un vector (un tablou unidimensional), ca pe două liste sortate oarecare.

Program complet: interclasează liniile 1 și 2 ale matricei
#include <iostream>
using namespace std;

int main() {
    int m, n, a[101][101], c[201], i, j, k;
    cin >> m >> n;

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

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

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

Observă: liniile matricei se tratează exact ca niște liste sortate; interclasarea lor produce un vector sortat cu 2 * n elemente.

Exercițiu de completare

Completează enunțul cu cuvintele potrivite:

O matrice ale cărei linii sunt ______ permite căutarea rapidă a unei valori. Pe fiecare linie putem aplica ______, nu căutarea secvențială.

Bancă de cuvinte:
sortate căutare binară secvențială aleatoare

Exercițiu de completare 2

Completează afirmațiile despre prelucrări:

Pentru a număra liniile sortate, verificăm pentru fiecare linie i dacă a[i][j] <= a[i][j+1] pentru orice ______. Dacă liniile sunt sortate, le putem interclasa ca pe două ______.

Bancă de cuvinte:
j liste i numere

Test de înțelegere

Test rapid - probleme integrate:

1. O matrice cu m linii și n coloane are în total:

2. Căutarea binară pe o linie sortată cu n elemente are complexitatea:

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

Ai grijă la: căutarea binară aplicată pe o linie nesortată: rezultatul devine întâmplător, fără nicio eroare vizibilă. Verifică întotdeauna sortarea liniilor ÎNAINTE de a decide algoritmul de aplicat.

Aprofundare

De ce funcționează combinația matrice + căutare binară? Fiecare linie a matricei este o listă sortată independentă. Aplicând căutarea binară pe fiecare linie, complexitatea căutării unei valori în întreaga matrice (numărul total de comparații, raportat la dimensiunile matricei) devine O(m * log2 n), în loc de O(m * n) prin parcurgerea completă. Pentru o matrice cu 100 de linii și 100 de coloane, înseamnă aproximativ 700 de comparații în loc de 10000 - o îmbunătățire semnificativă, exact ce se punctează la problemele cu restricții mari.

Optimizarea cu oprirea timpurie: în programul de mai sus, bucla exterioară conține condiția i <= m && !gasit: imediat ce găsim valoarea pe o linie, nu mai căutăm pe liniile următoare. Fără această oprire, programul ar parcurge inutil toată matricea chiar și după găsirea valorii. Același model de gândire se aplică la orice problemă de tip „există cel puțin un element cu proprietatea P".

Verificarea liniilor sortate - capcana inițializării: variabila sortat trebuie resetată la true la începutul fiecărei linii, nu doar o dată înaintea buclelor. Altfel, o linie nesortată ar „contamina" verdictul liniilor următoare. În plus, dacă matricea are o singură coloană (n = 1), bucla interioară nu se execută și toate liniile sunt considerate sortate - comportament corect, deoarece o listă cu un element este întotdeauna sortată.

Aplicație reală - tabelul de rezultate sportive: un tabel cu rezultatele echipelor (fiecare linie = o echipă, valori = punctaje pe etape, sortate crescător) permite întrebări rapide: „a obținut echipa X vreodată exact 12 puncte?" - cu căutare binară pe fiecare linie, răspunsul vine aproape instant, chiar și pentru zeci de echipe și sute de etape.

APLICARE ȘI REZOLVARE DE PROBLEME

PbInfo - Căutare în matrice

Enunț:

Cerință: Se dă o matrice cu m linii și n coloane, fiecare linie fiind sortată crescător, și o valoare x. Să se afișeze DA dacă x apare în cel puțin o linie a matricei, sau NU în caz contrar, folosind căutarea binară pe fiecare linie.

Date de intrare:

Programul citește de la tastatură numerele m și n, apoi elementele matricei, linie cu linie, apoi valoarea x.

Date de ieșire:

Programul va afișa DA dacă valoarea există în matrice, altfel NU.

Restricții și precizări:

1 <= m, n <= 100, liniile matricei sunt sortate crescător.

Exemplu:

Intrare:

3 4
1 3 5 7
2 4 6 8
1 9 10 12
6

Ieșire:

DA
Cum gândim soluția:
  1. Citim matricea și valoarea x
  2. Pentru fiecare linie, inițializăm st = 1 și dr = n
  3. Aplicăm căutarea binară pe linia curentă
  4. Ne oprim la prima linie în care valoarea este găsită
Scrie soluția în C++:
Soluție corectă:
Soluția completă
#include <iostream>
using namespace std;

int main() {
    int m, n, a[101][101], x, i, j, st, dr, mij;
    bool gasit = false;
    cin >> m >> n;

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

    for (i = 1; i <= m && !gasit; i++) {
        st = 1;
        dr = n;
        while (st <= dr) {
            mij = (st + dr) / 2;
            if (a[i][mij] == x) {
                gasit = true;
                break;
            } else if (a[i][mij] < x) {
                st = mij + 1;
            } else {
                dr = mij - 1;
            }
        }
    }

    if (gasit)
        cout << "DA";
    else
        cout << "NU";
    return 0;
}

Ce învățăm: combinăm parcurgerea matricei cu căutarea binară: pentru fiecare linie sortată aplicăm algoritmul cu st, dr și mij.

PbInfo - Linii sortate

Enunț:

Cerință: Se dă o matrice cu m linii și n coloane. Să se afișeze numărul de linii care sunt sortate crescător.

Date de intrare:

Programul citește de la tastatură numerele m și n, apoi elementele matricei, linie cu linie.

Date de ieșire:

Programul va afișa numărul de linii sortate crescător.

Restricții și precizări:

1 <= m, n <= 100, elementele matricei sunt numere întregi.

Exemplu:

Intrare:

3 4
1 2 3 4
5 3 8 9
1 1 1 1

Ieșire:

2
Cum gândim soluția:
  1. Pentru fiecare linie, verificăm dacă a[i][j] <= a[i][j+1] pentru toate coloanele
  2. Folosim o variabilă booleană pentru fiecare linie
  3. Numărăm liniile sortate
  4. Afișăm rezultatul
Scrie soluția în C++:
Soluție corectă:
Soluția completă
#include <iostream>
using namespace std;

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

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

    for (i = 1; i <= m; i++) {
        sortat = true;
        for (j = 1; j < n; j++)
            if (a[i][j] > a[i][j + 1])
                sortat = false;
        if (sortat)
            cnt++;
    }

    cout << cnt;
    return 0;
}

Ce învățăm: verificăm ordinea pe fiecare linie a matricei, comparând elemente alăturate a[i][j] și a[i][j + 1].

EXERCIȚII PRACTICE

Exercițiul Practic: Probleme integrate

Sarcini de lucru

Completează următoarele sarcini pentru a-ți consolida problemele integrate

Sarcina 1: Interclasează două linii ale matricei

Cerință: Scrie un program C++ care citește o matrice cu m linii și n coloane, cu liniile 1 și 2 sortate, interclasează liniile 1 și 2 într-un vector și afișează vectorul rezultat.

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

int main() {
    int m, n, a[101][101], c[201], i, j, k;
    cin >> m >> n;

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

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

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

Verifică: liniile matricei se tratează ca liste sortate: accesăm a[1][i] și a[2][j] în loc de a[i] și b[j].

Sarcina 2: Suma elementelor de pe liniile sortate

Cerință: Scrie un program C++ care citește o matrice cu m linii și n coloane și afișează suma tuturor elementelor de pe liniile care sunt sortate crescător.

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

int main() {
    int m, n, a[101][101], i, j, s = 0;
    bool sortat;
    cin >> m >> n;

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

    for (i = 1; i <= m; i++) {
        sortat = true;
        for (j = 1; j < n; j++)
            if (a[i][j] > a[i][j + 1])
                sortat = false;
        if (sortat)
            for (j = 1; j <= n; j++)
                s = s + a[i][j];
    }

    cout << s;
    return 0;
}

Verifică: mai întâi stabilim dacă linia este sortată, apoi, doar pentru liniile sortate, adunăm elementele.

Scrie pe caiet - De reținut

Titlul lecției

Ora 8: Probleme integrate: matrice + liste sortate

Definiția lecției

O matrice ale cărei linii sunt sortate crescător este un model mixt foarte folosit: fiecare linie poate fi tratată ca o listă sortată independentă, asupra căreia aplicăm algoritmi rapizi. Căutarea binară pe liniile matricei parcurge liniile cu o buclă exterioară și aplică algoritmul clasic cu st, dr și mij pe elementele a[i][mij], oprindu-se la prima linie în care valoarea a fost găsită; complexitatea devine O(m * log2 n), în loc de O(m * n) la parcurgerea completă. Verificarea unei linii sortate compară fiecare element cu următorul, a[i][j] <= a[i][j + 1], iar variabila sortat trebuie resetată la începutul fiecărei linii. Interclasarea a două linii sortate funcționează exact ca interclasarea a două liste oarecare, cu indicii i, j și k, și produce un vector sortat cu 2 * n elemente.

Definiții esențiale

  • O matrice ale cărei linii sunt sortate este un model mixt ce permite algoritmi rapizi pe fiecare linie: căutare binară, interclasare.
  • Căutarea binară pe liniile matricei: pentru fiecare linie i, aplicăm algoritmul clasic cu st, dr, mij pe elementele a[i][mij].
  • Complexitatea căutării pe întreaga matrice: O(m * log2 n).
  • Liniile matricei se interclasează ca niște liste sortate oarecare: a[1][...] și a[2][...].

Algoritmul cheie - pseudocod

Algoritmul CăutareBinarăPeLinii(a, m, n, x): gasit <- fals i <- 1 cât timp i <= m și nu gasit execută st <- 1 dr <- n cât timp st <= dr execută mij <- (st + dr) / 2 dacă a[i][mij] = x atunci gasit <- adevărat altfel dacă a[i][mij] < x atunci st <- mij + 1 altfel dr <- mij - 1 sfârșit dacă sfârșit cât timp i <- i + 1 sfârșit cât timp dacă gasit atunci scrie "DA" altfel scrie "NU" sfârșit dacă

Algoritmul cheie - cod C++

Căutarea binară pe liniile matricei
gasit = false;
for (i = 1; i <= m && !gasit; i++) {
    st = 1;
    dr = n;
    while (st <= dr) {
        mij = (st + dr) / 2;
        if (a[i][mij] == x) {
            gasit = true;
            break;
        } else if (a[i][mij] < x) {
            st = mij + 1;
        } else {
            dr = mij - 1;
        }
    }
}

Greșeli comune de evitare

  • Resetarea variabilei sortat doar o dată: trebuie reinițializată cu true la începutul fiecărei linii.
  • Parcurgerea secvențială a liniilor sortate: pierzi avantajul de eficiență al căutării binare.
  • Oprirea căutării prea devreme sau prea târziu: fără !gasit în condiția buclei exterioare, parcurgi inutil restul matricei.

Exemplu practic

Un tabel cu rezultatele echipelor sportive are fiecare linie sortată crescător: linia unei echipe conține punctajele ei pe etape. Pentru a verifica rapid dacă o echipă a obținut vreodată exact x puncte, aplicăm căutarea binară pe fiecare linie. Programul de mai jos citește matricea și afișează DA dacă valoarea x apare în cel puțin o linie.

Căutarea binară pe liniile matricei
#include <iostream>
using namespace std;

int main() {
    int m, n, a[101][101], x, i, j, st, dr, mij;
    bool gasit = false;
    cin >> m >> n;

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

    for (i = 1; i <= m && !gasit; i++) {
        st = 1;
        dr = n;
        while (st <= dr) {
            mij = (st + dr) / 2;
            if (a[i][mij] == x) {
                gasit = true;
                break;
            } else if (a[i][mij] < x) {
                st = mij + 1;
            } else {
                dr = mij - 1;
            }
        }
    }

    if (gasit)
        cout << "DA";
    else
        cout << "NU";
    return 0;
}

Pentru o matrice cu 3 echipe și 4 etape, programul răspunde aproape instant dacă punctajul x a fost atins vreodată, verificând fiecare linie cu cel mult log2 4 = 2 comparații.

Sfaturi practice și trucuri

  • Verifică mai întâi dacă liniile sunt chiar sortate (o linie nesortată invalidează căutarea binară).
  • La interclasarea liniilor, tratează fiecare linie ca pe o listă independentă, cu indicii proprii.
  • În bareme se punctează eficiența: menționează complexitatea O(m * log2 n) la justificări.