Sinteza Modulului 1 - Clasa X | Școala Româno-Britanică

1. Mulțimea - model conceptual neliniar (Ora 1)

Definiție: O mulțime este o colecție de elemente distincte, fără o ordine anume, considerate ca un singur obiect.

Model conceptual neliniar: elementele nu sunt stocate pe poziții (indecși), ci prin simpla prezență sau absență a fiecărui element.

Șir (liniar) vs. mulțime (neliniar)

Șirul: elemente pe poziții, poate avea dubluri, ordinea contează; 5 3 5 2 3.
Mulțimea: elemente distincte, fără poziții, ordinea nu contează; {2, 3, 5}.

Proprietăți: elementele sunt distincte (un element nu se repetă) și nu au o ordine ({1, 2, 3} = {3, 2, 1}). Cardinalul |A| este numărul de elemente distincte; mulțimea vidă ∅ are cardinalul 0.

2. Reprezentarea mulțimilor în C++ (Ora 2)

Vector de prezență: frec[x] = 1 dacă x aparține mulțimii, frec[x] = 0 dacă nu. Vector de frecvență: numără aparițiile (frec[x]++); pentru mulțimi se folosește doar prezența.

Inițializare: frec[101] = {0}; se declară cu o poziție în plus față de valoarea maximă. Afișarea parcurgând vectorul crescător produce mulțimea sortată.

Reguli: valorile trebuie să fie întregi într-un domeniu cunoscut; dublurile nu modifică rezultatul marcării; complexitate O(n) pentru construire și O(V) pentru afișare.

3. Algoritm principal: construirea și afișarea unei mulțimi

Pașii: citim valorile și le marcăm în vectorul de prezență, apoi parcurgem vectorul și afișăm valorile marcate, în ordine crescătoare.

citeste n frec[1..100] = 0 pentru i = 1, n executa citeste x frec[x] = 1 pentru i = 1, 100 executa daca frec[i] == 1 atunci scrie i

C++ - Reprezentarea mulțimii cu vector de prezență

#include <iostream>
using namespace std;

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

4. Operațiile cu mulțimi (Orele 3, 4)

Reuniunea A ∪ B: elementele din A sau B (sau ambele). Intersecția A ∩ B: elementele comune lui A și B. Diferența A - B: elementele din A care nu sunt în B.

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}

Reguli: reuniunea și intersecția sunt comutative; diferența nu este (A - B ≠ B - A, în general). Cardinalul reuniunii: |A ∪ B| = |A| + |B| - |A ∩ B|.

5. Algoritm principal: reuniune, intersecție, diferență

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

C++ - Reuniunea, intersecția și diferența

#include <iostream>
using namespace std;

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

6. Apartenența, incluziunea și egalitatea (Ora 5)

Apartenența x ∈ A: frecA[x] == 1. Incluziunea A ⊆ B: fiecare element al lui A se află în B (nu există frecA[i] == 1 && frecB[i] == 0). Egalitatea A = B: frecA[i] == frecB[i] pentru toți i.

Tehnica steagului: inițializăm ok = true; la prima excepție executăm ok = false; la final ok dă răspunsul.

citeste x daca frecA[x] == 1 atunci scrie "x apartine lui A" altfel scrie "x nu apartine lui A" ok = adevarat pentru i = 1, 100 executa daca frecA[i] == 1 SI frecB[i] == 0 atunci ok = fals daca ok atunci scrie "A este inclusa in B" altfel scrie "A nu este inclusa in B" ok = adevarat pentru i = 1, 100 executa daca frecA[i] != frecB[i] atunci ok = fals daca ok atunci scrie "A este egala cu B" altfel scrie "A nu este egala cu B"

C++ - Verificări cu mulțimi

#include <iostream>
using namespace std;

int main() {
    int n, m, x, i, frecA[101] = {0}, frecB[101] = {0};
    bool ok;
    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;
    }
    cin >> x;
    if (frecA[x] == 1)
        cout << x << " apartine lui A" << endl;
    else
        cout << x << " nu apartine lui A" << endl;

    ok = true;
    for (i = 1; i <= 100; i++)
        if (frecA[i] == 1 && frecB[i] == 0)
            ok = false;
    if (ok)
        cout << "A este inclusa in B" << endl;
    else
        cout << "A nu este inclusa in B" << endl;

    ok = true;
    for (i = 1; i <= 100; i++)
        if (frecA[i] != frecB[i])
            ok = false;
    if (ok)
        cout << "A este egala cu B" << endl;
    else
        cout << "A nu este egala cu B" << endl;
    return 0;
}

7. Eliminarea dublurilor și numărarea elementelor distincte (Ora 6)

Numărăm o valoare doar dacă o întâlnim prima dată: if (frec[x] == 0) { frec[x] = 1; nr++; }. Rezultatul nr este cardinalul mulțimii valorilor distincte; complexitate O(n).

citeste n frec[1..100] = 0 nr = 0 pentru i = 1, n executa citeste x daca frec[x] == 0 atunci frec[x] = 1 nr = nr + 1 scrie nr

C++ - Numărarea elementelor distincte

#include <iostream>
using namespace std;

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

8. Aplicații practice cu caractere (Ora 7)

Un caracter are valoare numerică (cod ASCII), deci poate fi folosit ca indice: frec[s[i]] = 1 cu frec[256]. Citim cu cin.getline(s, 100), aflăm lungimea cu strlen, iar la afișare transformăm indicele înapoi cu (char)i.

C++ - Literele distincte dintr-un cuvânt

#include <iostream>
#include <cstring>
using namespace std;

int main() {
    char s[100];
    int frec[256] = {0}, i, n;
    cin.getline(s, 100);
    n = strlen(s);
    for (i = 0; i < n; i++)
        if (s[i] != ' ')
            frec[s[i]] = 1;
    for (i = 0; i < 256; i++)
        if (frec[i] == 1)
            cout << (char)i << " ";
    return 0;
}

9. Tabel recapitulativ complet al relațiilor (Ora 8)

Relația	Notație	Semnificație	Condiția în C++
Apartenența	`x ∈ A`	x este element al lui A	`frecA[x] == 1`
Incluziunea	`A ⊆ B`	toate elementele lui A sunt în B	fără `frecA[i] == 1 && frecB[i] == 0`
Egalitatea	`A = B`	aceleași elemente în ambele mulțimi	`frecA[i] == frecB[i]` pentru toți i

Reguli și echivalențe utile: A ⊆ B ⟺ A ∪ B = B ⟺ A ∩ B = A; A - B = ∅ ⟺ A ⊆ B; mulțimea vidă este inclusă în orice mulțime; |A ∪ B| = |A| + |B| - |A ∩ B|.

10. Greșeli frecvente și cum le eviți

Greșeli frecvente la evaluare

Inversarea operatorilor: || la reuniune, && la intersecție și diferență.
La diferență, scrierea frecB[i] == 1 în loc de frecB[i] == 0.
Uitarea inițializării cu {0} și a declarării cu o poziție în plus (frec[101] pentru valori până la 100).
Compararea elementului cu el însuși (j <= i în loc de j < i) la verificarea dublurilor.
Inițializarea lui ok sau a lui distinct în interiorul buclei.
Afișarea lui x în locul indicelui i la parcurgerea vectorului de prezență.
Citirea cu cin >> s pentru șiruri cu spații; trebuie cin.getline.

Pași de verificare a unei soluții

Identifică modelul: liniar (șir) sau neliniar (mulțime).
Alege reprezentarea: comparare directă sau vector de prezență, după domeniul valorilor.
Scrie pseudocodul înainte de codul C++.
Urmărește algoritmul pe un exemplu mic, scris pe hârtie.
Testează și cazurile limită: valori la capetele intervalului, mulțime vidă, toate elementele egale.

11. Comparație rapidă: reuniune vs intersecție vs diferență

Întrebarea	Reuniunea A ∪ B	Intersecția A ∩ B	Diferența A - B
Ce păstrează?	tot ce e în A sau B	doar ce e comun lui A și B	ce e în A, dar nu în B
Operatorul C++	`frecA[i] == 1 \|\| frecB[i] == 1`	`frecA[i] == 1 && frecB[i] == 1`	`frecA[i] == 1 && frecB[i] == 0`
A={1,2,3}, B={3,4}	{1, 2, 3, 4}	{3}	{1, 2}
Comutativă?	da	da	nu (A - B ≠ B - A)

Reguli de reținut: la reuniune contează un singur „da" (||); la intersecție sunt necesare două „da" (&&); la diferență primul este „da", iar al doilea „nu" (frecB[i] == 0).

12. Vector de prezență vs vector de frecvență

Criteriu	Vector de prezență	Vector de frecvență
Ce reține	dacă x există (0 sau 1)	de câte ori apare x (0, 1, 2, ...)
Instrucțiunea	`frec[x] = 1`	`frec[x]++`
Când îl folosim	reprezentarea unei mulțimi	numărarea aparițiilor, statistici
Legătura cu mulțimea	vectorul de prezență este reprezentarea mulțimii în C++	numărul de poziții cu `frec[i] > 0` este cardinalul

Reține: pentru o mulțime folosim doar prezența (0 sau 1); vectorul de frecvență devine util când problema cere și de câte ori apare fiecare valoare.

13. Exemple suplimentare de cod C++

Exemplul 1 - Cardinalul reuniunii prin formulă. Nu construim reuniunea, ci numărăm direct cu |A ∪ B| = |A| + |B| - |A ∩ B|.

C++ - Cardinalul reuniunii fără construcția reuniunii

#include <iostream>
using namespace std;

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

Exemplul 2 - Diferența simetrică. Elementele care aparțin exact uneia dintre mulțimi: (A - B) ∪ (B - A).

C++ - Valorile care apar o singură dată în cele două mulțimi

#include <iostream>
using namespace std;

int main() {
    int n, m, x, i, frecA[101] = {0}, frecB[101] = {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; }
    cout << "Doar in A: ";
    for (i = 1; i <= 100; i++)
        if (frecA[i] == 1 && frecB[i] == 0)
            cout << i << " ";
    cout << endl << "Doar in B: ";
    for (i = 1; i <= 100; i++)
        if (frecB[i] == 1 && frecA[i] == 0)
            cout << i << " ";
    cout << endl;
    return 0;
}

14. Ce trebuie să știi pentru test

Lista de verificare

să definești mulțimea ca model conceptual neliniar și să o deosebești de șir
să construiești și să afișezi sortat o mulțime cu vector de prezență
să scrii condițiile C++ pentru reuniune, intersecție și diferență
să verifici apartenența, incluziunea și egalitatea cu tehnica steagului ok
să numeri elementele distincte cu tehnica marcare-numărare
să aplici vectorul de prezență pe caractere (cod ASCII, frec[256])
să estimezi complexitatea: O(n) pentru construire, O(V) pentru afișare

15. Exerciții de recapitulare (cu rezolvare)

Exercițiul 1 - Mulțime vs șir

Care este cardinalul mulțimii valorilor din șirul 4 7 4 2 7 4 9? Scrie valorile distincte.

Rezolvare: valorile distincte sunt {2, 4, 7, 9}, deci cardinalul este 4. Verificare: 2, 4, 7 și 9 apar; restul sunt dubluri.

Exercițiul 2 - Operații cu mulțimi

Pentru A = {1, 3, 5, 7} și B = {3, 7, 9}, calculează A ∪ B, A ∩ B și A - B.

Rezolvare: A ∪ B = {1, 3, 5, 7, 9}; A ∩ B = {3, 7}; A - B = {1, 5}. Verificare: 3 și 7 sunt comune; 9 este doar în B, deci nu apare în A - B.

Exercițiul 3 - Mini-provocare

Scrie în C++ un program care citește n valori și afișează valorile care apar exact o dată în șir.

Rezolvare (idee + cod): folosim un vector de frecvență (frec[x]++), apoi afișăm valorile pentru care frec[i] == 1.

#include <iostream>
using namespace std;

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

16. Greșeli frecvente la test

Greșelile care costă cel mai mult puncte

inversarea operatorilor: || la reuniune, && la intersecție și la diferență
la diferență, scrierea frecB[i] == 1 în loc de frecB[i] == 0
uitarea inițializării {0} sau declararea vectorului fără poziție în plus
compararea elementului cu el însuși la verificarea dublurilor (j <= i în loc de j < i)
inițializarea steagului ok în interiorul buclei
afișarea lui x în locul indicelui i la parcurgerea vectorului de prezență
citirea unui șir cu spații cu cin >> s în loc de cin.getline

Sfat pentru test: verifică întâi pseudocodul pe un exemplu mic, apoi scrie codul C++; testează și cazurile limită (mulțime vidă, toate valorile egale, valori la capetele domeniului).

Sinteza Modulului 1 - Mulțimea, model conceptual neliniar