Scrie pe caiet - De reținut

Titlul lecției

Ora 10: Aplicații integrate: matrice și liste sortate

Definiția lecției

O problemă integrată folosește simultan matricea și algoritmii pe liste sortate: matricea organizează datele în tabel, iar sortarea, căutarea binară și interclasarea prelucrează rapid liniile sau zonele ei. Diagonala principală este o listă ascunsă în matrice: elementele a[1][1], a[2][2], ..., a[n][n] se copiază într-un vector de lucru, se sortează prin selecție, iar matricea rămâne neschimbată. Interclasarea a două linii sortate tratează fiecare linie ca pe o listă independentă: indicii i și j parcurg liniile 1 și 2, iar k construiește vectorul rezultat, sortat, cu 2 * n elemente. Pe acest vector se poate aplica imediat căutarea binară, fără o sortare suplimentară. Cheia rezolvării este decompoziția: extragem zona cerută, o prelucrăm cu algoritmul potrivit, apoi raportăm rezultatul, fără a modifica datele de intrare.

Definiții esențiale

• Problema integrată combină matricea cu algoritmii pe liste sortate: extragem zona cerută într-un vector, apoi aplicăm sortare, căutare binară sau interclasare.
• Elementele diagonalei principale: a[i][i]; ale diagonalei secundare: a[i][j] cu i + j == n + 1.
• Interclasarea a două linii cu n elemente produce un vector cu 2 * n elemente, sortat.
• Pe rezultatul interclasării se poate aplica direct căutarea binară, fără sortare suplimentară.

Algoritmul cheie - pseudocod

Algoritmul cheie - cod C++

i = 1;
j = 1;
k = 0;
while (i <= n && j <= n) {
    k++;
    if (a[1][i] <= a[2][j]) {
        c[k] = a[1][i];
        i++;
    } else {
        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++; }

Greșeli comune de evitare

• Sortarea elementelor direct în matrice: modifică datele de intrare; lucrează mereu pe un vector de lucru.
• Confundarea diagonalei secundare: condiția este i + j == n + 1, nu i + j == n.
• Interclasarea liniilor fără a verifica dacă acestea sunt sortate: rezultatul nu va mai fi ordonat.

Exemplu practic

Un profesor are notele elevilor pe două discipline, fiecare linie a matricei fiind sortată crescător. El vrea lista completă a notelor elevilor la cele două discipline, în ordine, și verifică apoi dacă nota x apare în această listă. Programul interclasează liniile 1 și 2 ale matricei, apoi caută binar valoarea x în vectorul rezultat.

#include <iostream>
using namespace std;

int main() {
    int m, n, a[101][101], c[201], x, i, j, k, 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];

    i = 1; j = 1; k = 0;
    while (i <= n && j <= n) {
        k++;
        if (a[1][i] <= a[2][j]) { c[k] = a[1][i]; i++; }
        else { 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++; }

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

    for (i = 1; i <= k; i++)
        cout << c[i] << " ";
    cout << endl;
    if (gasit)
        cout << "DA";
    else
        cout << "NU";
    return 0;
}

Pentru matricea cu liniile 1 3 5 și 2 4 6, programul afișează 1 2 3 4 5 6 și verdictul căutării, totul fără o sortare suplimentară.

Sfaturi practice și trucuri

• Decompune problema în pași: extragere, prelucrare, raportare - și rezolvă fiecare pas separat.
• Dacă liniile sunt sortate, maximul matricei este a[m][n], iar minimul a[1][1] - verificări rapide la barem.
• Verifică dimensiunile înainte de a interclasa: matricea trebuie să aibă cel puțin două linii.