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

Ora 8: Recapitulare și test

Ce vei învăța astăzi: Recapitularea reprezentării și a operațiilor cu mulțimi, urmată de un test integrativ

Rezultat practic: Recapitulizezi reprezentarea și operațiile cu mulțimi și rezolvi un test integrativ în C++ (Competența 6.1).

Competența 6.1 Săptămâna 4

Înainte de a începe

De ce contează? Recapitularea leagă între ele reprezentarea și toate operațiile cu mulțimi, iar tabelul rezumativ te pregătește pentru testul modulului și pentru subiectele de BAC.

Ce știi deja?

Ai parcurs orele 1-7: mulțimea ca model neliniar (o structură de date în care elementele nu sunt stocate pe poziții, ci prin simpla prezență), vectorul de prezență (un vector în care marcam cu 1 valorile care aparțin mulțimii) și toate operațiile. Poți rezuma din memorie reuniunea (mulțimea elementelor care apar în cel puțin una dintre cele două mulțimi), intersecția (mulțimea elementelor comune) și diferența (mulțimea elementelor din prima mulțime care nu apar în a doua)?

Ideea-cheie: Toate operațiile cu mulțimi se reduc la o singură condiție pe vectorii de prezență — cunoașterea tabelului rezumativ le acoperă pe toate dintr-o dată.
SINTEZĂ TEORETICĂ ȘI EXEMPLE GHIDATE

Ce vei învăța astăzi?

După această lecție vei recapitula tot ce ai învățat despre mulțimi: reprezentarea, operațiile și verificările, apoi vei rezolva un test integrativ.

Recapitularea reprezentării mulțimilor
Tabel rezumativ al operațiilor
Program de recapitulare în C++
Test final al modulului

Recapitulare: mulțimea și reprezentarea ei

Mulțimea este un model conceptual neliniar: elemente distincte, fără ordine. O reprezentăm în C++ cu un vector de prezență, unde frec[x] = 1 dacă x ∈ A.

Recapitulare rapidă

  • Elemente distincte: fiecare valoare apare o singură dată
  • Reprezentare: frec[x] = 1 marchează prezența lui x
  • Afișare sortată: parcurgem vectorul crescător

Tabel rezumativ al operațiilor cu mulțimi

Operația Simbol Condiția în C++ Exemplu (A={1,2,3}, B={3,4})
Reuniunea A ∪ B frecA[i] == 1 || frecB[i] == 1 {1, 2, 3, 4}
Intersecția A ∩ B frecA[i] == 1 && frecB[i] == 1 {3}
Diferența A - B frecA[i] == 1 && frecB[i] == 0 {1, 2}
Apartenența x ∈ A frecA[x] == 1 3 ∈ A (adevărat)
Incluziunea A ⊆ B fără frecA[i] == 1 && frecB[i] == 0 A ⊆ B (fals)
Egalitatea A = B frecA[i] == frecB[i] pentru toți i A = B (fals)

Program de recapitulare în C++

Un program complet care calculează reuniunea, intersecția, diferența și numărul de elemente distincte pentru două mulțimi.

citeste n, apoi n elemente in A citeste m, apoi m elemente in B nr = 0 scrie "Reuniune:" pentru i = 1, 100 executa daca A[i] == 1 SAU B[i] == 1 atunci scrie i nr = nr + 1 scrie "Intersectie:" pentru i = 1, 100 executa daca A[i] == 1 SI B[i] == 1 atunci scrie i scrie "Diferenta A - B:" pentru i = 1, 100 executa daca A[i] == 1 SI B[i] == 0 atunci scrie i scrie "Elemente distincte: ", nr
C++ - Recapitulare: toate operațiile cu mulțimi
#include <iostream>
using namespace std;

int main() {
    int n, m, x, i, A[101] = {0}, B[101] = {0}, nr = 0;
    cin >> n;
    for (i = 1; i <= n; i++) {
        cin >> x;
        A[x] = 1;
    }
    cin >> m;
    for (i = 1; i <= m; i++) {
        cin >> x;
        B[x] = 1;
    }

    cout << "Reuniune: ";
    for (i = 1; i <= 100; i++)
        if (A[i] == 1 || B[i] == 1)
            cout << i << " ";
    cout << endl;

    cout << "Intersectie: ";
    for (i = 1; i <= 100; i++)
        if (A[i] == 1 && B[i] == 1)
            cout << i << " ";
    cout << endl;

    cout << "Diferenta A - B: ";
    for (i = 1; i <= 100; i++)
        if (A[i] == 1 && B[i] == 0)
            cout << i << " ";
    cout << endl;

    for (i = 1; i <= 100; i++)
        if (A[i] == 1 || B[i] == 1)
            nr++;
    cout << "Elemente distincte: " << nr << endl;
    return 0;
}

Observă: același pereche de vectori de prezență susține toate operațiile; fiecare operație se reduce la o condiție simplă.

Exercițiu de completare

Completează rezumatul operațiilor:

Reuniunea A ∪ B conține elementele din A ______ B, intersecția A ∩ B conține elementele ______, iar diferența A - B conține elementele din A care nu sunt în ______.

Bancă de cuvinte:
sau comune B

Exercițiu de completare

Completează condițiile C++:

Reuniunea: frecA[i] == 1 ______ frecB[i] == 1; intersecția: frecA[i] == 1 ______ frecB[i] == 1; diferența: frecA[i] == 1 ______ frecB[i] == 0.

Bancă de cuvinte:
|| &&

Test de înțelegere

Test rapid - recapitulare:

1. Pentru A = {1, 2, 3} și B = {3, 4}, reuniunea A ∪ B este:

2. Pentru aceleași mulțimi, intersecția A ∩ B este:

3. Câte valori distincte are șirul 2 5 2 3 5?

Ai grijă la: la test, verifică de două ori condițiile: || la reuniune, && la intersecție și && cu frecB[i] == 0 la diferență — inversarea lor costă puncte.

Aprofundare

Legăturile dintre operații: operațiile cu mulțimi nu sunt izolate; între ele există echivalențe utile la rezolvarea problemelor și la verificarea soluțiilor.

  • A ⊆ B ⟺ A ∪ B = B ⟺ A ∩ B = A: dacă una dintre condiții e adevărată, toate sunt; poți verifica încrucișat un program care testează incluziunea (faptul că toate elementele lui A se află și în B).
  • Cardinalul reuniunii: |A ∪ B| = |A| + |B| - |A ∩ B|; numărând elementele celor două mulțimi și elementele comune, obții cardinalul reuniunii fără a o construi.
  • Diferența și incluziunea: A - B = ∅ exact atunci când A ⊆ B; dacă diferența este vidă, mulțimea A este inclusă în B.
  • Structură unică: toate operațiile folosesc aceeași pereche de vectori de prezență; doar condiția din buclă se schimbă, ceea ce face programul ușor de extins.
  • Pentru BAC: un program care combină toate operațiile (ca în recapitulare) acoperă o mare parte din subiectele de tipul "prelucrări pe mulțimi".
APLICARE ȘI REZOLVARE DE PROBLEME

PbInfo - Reuniunea și cardinalul

Enunț:

Cerință: Se citesc două mulțimi de numere naturale. Să se afișeze reuniunea lor sortată, apoi cardinalul acesteia.

Date de intrare:

Programul citește n, apoi n elemente ale primei mulțimi, apoi m, apoi m elemente ale celei de-a doua mulțimi.

Date de ieșire:

Programul va afișa pe prima linie elementele reuniunii, iar pe a doua linie cardinalul reuniunii.

Restricții și precizări:

1 ≤ n, m ≤ 100; elementele sunt numere naturale între 1 și 100.

Exemplu:

Intrare:

3
1 2 3
3
3 4 5

Ieșire:

1 2 3 4 5
5
Cum gândim soluția:
  1. Marcăm prezența elementelor din ambele mulțimi
  2. Afișăm valorile din reuniune și numărăm cardinalul
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;

int main() {
    int n, m, x, i, frec[101] = {0}, nr = 0;
    cin >> n;
    for (i = 1; i <= n; i++) {
        cin >> x;
        frec[x] = 1;
    }
    cin >> m;
    for (i = 1; i <= m; i++) {
        cin >> x;
        frec[x] = 1;
    }
    for (i = 1; i <= 100; i++)
        if (frec[i] == 1) {
            cout << i << " ";
            nr++;
        }
    cout << endl << nr;
    return 0;
}

Ce învățăm: reuniunea și cardinalul ei se obțin dintr-o singură parcurgere a vectorului de prezență.

PbInfo - Elemente comune

Enunț:

Cerință: Se citesc două mulțimi de numere naturale. Să se afișeze câte elemente comune au cele două mulțimi (cardinalul intersecției).

Date de intrare:

Programul citește n, apoi n elemente ale primei mulțimi, apoi m, apoi m elemente ale celei de-a doua mulțimi.

Date de ieșire:

Programul va afișa pe ecran numărul de elemente comune.

Restricții și precizări:

1 ≤ n, m ≤ 100; elementele sunt numere naturale între 1 și 100.

Exemplu:

Intrare:

4
1 2 3 4
3
3 4 5

Ieșire:

2
Cum gândim soluția:
  1. Marcăm prezența elementelor din ambele mulțimi
  2. Numărăm valorile cu frecA == 1 și frecB == 1
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;

int main() {
    int n, m, x, i, frecA[101] = {0}, frecB[101] = {0}, nr = 0;
    cin >> n;
    for (i = 1; i <= n; i++) {
        cin >> x;
        frecA[x] = 1;
    }
    cin >> m;
    for (i = 1; i <= m; i++) {
        cin >> x;
        frecB[x] = 1;
    }
    for (i = 1; i <= 100; i++)
        if (frecA[i] == 1 && frecB[i] == 1)
            nr++;
    cout << nr;
    return 0;
}

Ce învățăm: cardinalul intersecției se obține numărând valorile comune celor doi vectori de prezență.

EXERCIȚII PRACTICE

Exercițiul Practic: Recapitulare și test

Sarcini de lucru

Completează următoarele sarcini pentru a-ți verifica cunoștințele din modul

Sarcina 1: Rezolvă problema integrativ

Cerință: Pentru A = {2, 4, 6, 8} și B = {4, 6, 9}, calculează A ∪ B, A ∩ B, A - B și cardinalul reuniunii.

Soluție pentru Sarcina 1:
A ∪ B = {2, 4, 6, 8, 9}
A ∩ B = {4, 6}
A - B = {2, 8}
|A ∪ B| = 5
Sarcina 2: Scrie programul de recapitulare

Cerință: Scrie un program C++ care citește două mulțimi și afișează reuniunea, intersecția și numărul de elemente distincte.

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

int main() {
    int n, m, x, i, A[101] = {0}, B[101] = {0}, nr = 0;
    cin >> n;
    for (i = 1; i <= n; i++) {
        cin >> x;
        A[x] = 1;
    }
    cin >> m;
    for (i = 1; i <= m; i++) {
        cin >> x;
        B[x] = 1;
    }
    cout << "Reuniune: ";
    for (i = 1; i <= 100; i++)
        if (A[i] == 1 || B[i] == 1) {
            cout << i << " ";
            nr++;
        }
    cout << endl;
    cout << "Intersectie: ";
    for (i = 1; i <= 100; i++)
        if (A[i] == 1 && B[i] == 1)
            cout << i << " ";
    cout << endl;
    cout << "Elemente distincte: " << nr << endl;
    return 0;
}

Scrie pe caiet - De reținut

Titlul lecției

Ora 8: Recapitulare și test

Definiția lecției

Acest modul a arătat că orice problemă cu mulțimi se reduce la vectori de prezență și la condiții simple pe aceștia. Mulțimea se reprezintă cu frec[x] = 1, iar afișarea indicilor marcați produce elementele sortate. Reuniunea folosește operatorul ||, intersecția folosește &&, iar diferența A - B folosește condiția frecA[i] == 1 && frecB[i] == 0. Apartenența se verifică direct cu frecA[x] == 1, iar incluziunea și egalitatea se verifică element cu element, cu un steag boolean ok. Numărarea valorilor distincte dintr-un șir se face marcând fiecare valoare la prima ei apariție. Tabelul rezumativ al operațiilor este instrumentul principal de rezolvare la test și la BAC.

Definiții esențiale

Algoritmul cheie - pseudocod

citeste n, apoi n elemente in A citeste m, apoi m elemente in B nr = 0 scrie "Reuniune:" pentru i = 1, 100 executa daca A[i] == 1 SAU B[i] == 1 atunci scrie i nr = nr + 1 scrie "Intersectie:" pentru i = 1, 100 executa daca A[i] == 1 SI B[i] == 1 atunci scrie i scrie "Diferenta A - B:" pentru i = 1, 100 executa daca A[i] == 1 SI B[i] == 0 atunci scrie i scrie "Elemente distincte: ", nr

Algoritmul cheie - cod C++

C++ - Recapitulare: toate operațiile cu mulțimi
#include <iostream>
using namespace std;

int main() {
    int n, m, x, i, A[101] = {0}, B[101] = {0}, nr = 0;
    cin >> n;
    for (i = 1; i <= n; i++) {
        cin >> x;
        A[x] = 1;
    }
    cin >> m;
    for (i = 1; i <= m; i++) {
        cin >> x;
        B[x] = 1;
    }

    cout << "Reuniune: ";
    for (i = 1; i <= 100; i++)
        if (A[i] == 1 || B[i] == 1)
            cout << i << " ";
    cout << endl;

    cout << "Intersectie: ";
    for (i = 1; i <= 100; i++)
        if (A[i] == 1 && B[i] == 1)
            cout << i << " ";
    cout << endl;

    cout << "Diferenta A - B: ";
    for (i = 1; i <= 100; i++)
        if (A[i] == 1 && B[i] == 0)
            cout << i << " ";
    cout << endl;

    for (i = 1; i <= 100; i++)
        if (A[i] == 1 || B[i] == 1)
            nr++;
    cout << "Elemente distincte: " << nr << endl;
    return 0;
}

Greșeli comune de evitat

Sfaturi practice și trucuri

Exemplu practic

O agenție are două baze de date cu abonați: managerul vrea să afișeze reuniunea, intersecția și diferența dintre ele:

C++ - Operațiile cu mulțimi pe două baze de date
#include <iostream>
using namespace std;

int main() {
    int n, m, x, i, A[101] = {0}, B[101] = {0};
    cin >> n;
    for (i = 1; i <= n; i++) {
        cin >> x;
        A[x] = 1;
    }
    cin >> m;
    for (i = 1; i <= m; i++) {
        cin >> x;
        B[x] = 1;
    }
    cout << "Reuniune: ";
    for (i = 1; i <= 100; i++)
        if (A[i] == 1 || B[i] == 1)
            cout << i << " ";
    cout << endl;
    cout << "Intersectie: ";
    for (i = 1; i <= 100; i++)
        if (A[i] == 1 && B[i] == 1)
            cout << i << " ";
    cout << endl;
    cout << "Diferenta A - B: ";
    for (i = 1; i <= 100; i++)
        if (A[i] == 1 && B[i] == 0)
            cout << i << " ";
    cout << endl;
    return 0;
}