Ora 20 - Verificarea unei proprietăți

TEORIE - 40 minute

Ce vei învăța astăzi?

După această lecție, vei putea verifica diverse proprietăți ale elementelor dintr-un vector folosind flag-uri și condiții logice.

Ce este un flag (steguleț)

Verificare "toate elementele"

Verificare "există cel puțin un element"

Proprietăți complexe (pare, prim, perfect)

Ce este un FLAG (steguleț)?

Definiție: Un flag este o variabilă booleană (adevărat/fals) care indică prezența sau absența unei proprietăți.

Analogii:
✓ Steguleț ridicat = proprietatea este adevărată
✓ Steguleț coborât = proprietatea este falsă
✓ Comutator aprins/stins = stare activă/inactivă

DEMONSTRAȚIE FLAG

FALS

Nu am găsit încă proprietatea

Flag = variabilă booleană (true / false)

Analogii pentru a înțelege flag-urile:

Alarma de fum

În repaus: flag = FALS. Când detectează fum: flag = ADEVĂRAT.

Verificare teme

Profesorul pornește cu flag = ADEVĂRAT. Când găsește un elev fără teme: flag = FALS.

Căutare chei

Începi cu flag = FALS. Când le găsești: flag = ADEVĂRAT.

Prima întrebare corectă: „Toate?”, „Există?”, „Niciunul?”

Înainte să scrii cod, alege întrebarea potrivită. În informatică, aproape orice verificare pe vector se reduce la una din aceste 3 forme:

TOATE elementele au proprietatea P?
EXISTĂ cel puțin un element cu proprietatea P?
NICIUN element nu are proprietatea P?

Întrebare	Cum pornești flag-ul	Ce cauți în buclă	Te oprești când...
TOATE au P?	`true`	un contraexemplu (un element care NU are P)	ai găsit primul element care NU are P
EXISTĂ un element cu P?	`false`	un exemplu (un element care ARE P)	ai găsit primul element care ARE P
NICIUN element nu are P?	`true`	un contraexemplu (un element care ARE P)	ai găsit primul element care ARE P

Truc logic foarte util: „Niciun element nu e 0” este același lucru cu „Toate elementele sunt diferite de 0”.

📋 Mini-șabloane (de copiat în caiet)

// 1) TOATE au P?  -> pornesc true, caut contraexemplu
bool ok = true;
for (int i = 0; i < n; i++) {
    if ( /* v[i] NU are P */ ) {
        ok = false;
        break;
    }
}

// 2) EXISTĂ cu P? -> pornesc false, caut exemplu
bool gasit = false;
for (int i = 0; i < n; i++) {
    if ( /* v[i] ARE P */ ) {
        gasit = true;
        break;
    }
}

// 3) NICIUN cu P? -> pornesc true, caut contraexemplu (un element cu P)
bool ok2 = true;
for (int i = 0; i < n; i++) {
    if ( /* v[i] ARE P */ ) {
        ok2 = false;
        break;
    }
}

Algoritmi pentru verificarea proprietăților

// VERIFICARE: Toate elementele sunt pare? 1. ok ← true // Presupunem că toate sunt pare (flag inițial) 2. pentru i ← 0, n-1 execută 3. dacă v[i] % 2 ≠ 0 // Dacă găsim un element IMPAR 4. ok ← false // Atunci nu mai sunt toate pare 5. oprește // Nu mai are rost să verificăm restul 6. sfârșit dacă 7. sfârșit pentru 8. dacă ok = adevărat atunci 9. scrie "Toate elementele sunt pare" 10. altfel 11. scrie "Nu toate sunt pare"

Strategie: Începem cu presupunerea că proprietatea este adevărată (ok = true). Dacă găsim un contraexemplu, schimbăm flag-ul în false.

💻 Implementare în C++

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    const int MAX = 1000;
    int v[MAX];
    
    // Citire vector
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    
    // Verificare: toate elementele sunt pare?
    bool toatePare = true;  // Flag - presupunem că toate sunt pare
    
    for (int i = 0; i < n; i++) {
        if (v[i] % 2 != 0) {  // Dacă găsim un număr impar
            toatePare = false; // Atunci nu mai sunt toate pare
            break;             // Ieșim din buclă (optimizare)
        }
    }
    
    if (toatePare) {
        cout << "TOATE elementele sunt pare." << endl;
    } else {
        cout << "NU toate elementele sunt pare." << endl;
    }
    
    return 0;
}

// VERIFICARE: Există cel puțin un element par? 1. gasit ← false // Presupunem că nu există niciun par (flag inițial) 2. pentru i ← 0, n-1 execută 3. dacă v[i] % 2 = 0 // Dacă găsim un element PAR 4. gasit ← true // Atunci am găsit cel puțin unul 5. oprește // Nu mai are rost să căutăm 6. sfârșit dacă 7. sfârșit pentru 8. dacă gasit = adevărat atunci 9. scrie "Există cel puțin un element par" 10. altfel 11. scrie "Nu există niciun element par"

Strategie inversă: Începem cu presupunerea că proprietatea este falsă (gasit = false). Dacă găsim un exemplu, schimbăm flag-ul în true.

💻 Implementare în C++

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    const int MAX = 1000;
    int v[MAX];
    
    // Citire vector
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    
    // Verificare: există cel puțin un element par?
    bool existaPar = false;  // Flag - presupunem că nu există
    
    for (int i = 0; i < n; i++) {
        if (v[i] % 2 == 0) {  // Dacă găsim un număr par
            existaPar = true;  // Atunci am găsit cel puțin unul
            break;             // Ieșim din buclă (optimizare)
        }
    }
    
    if (existaPar) {
        cout << "EXISTĂ cel puțin un element par." << endl;
    } else {
        cout << "NU există niciun element par." << endl;
    }
    
    return 0;
}

// VERIFICARE: Niciun element nu este negativ? 1. ok ← true // Presupunem că niciunul nu e negativ (flag inițial) 2. pentru i ← 0, n-1 execută 3. dacă v[i] < 0 // Dacă găsim un element NEGATIV 4. ok ← false // Atunci avem cel puțin un negativ 5. oprește // Nu mai are rost să verificăm 6. sfârșit dacă 7. sfârșit pentru 8. dacă ok = adevărat atunci 9. scrie "Niciun element nu este negativ" 10. altfel 11. scrie "Există cel puțin un element negativ"

Observație: "Niciun element nu are proprietatea X" este logic echivalent cu "Toate elementele NU au proprietatea X".

💻 Implementare în C++

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    const int MAX = 1000;
    int v[MAX];
    
    // Citire vector
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    
    // Verificare: niciun element nu este negativ?
    bool niciunNegativ = true;  // Flag - presupunem că niciunul nu e negativ
    
    for (int i = 0; i < n; i++) {
        if (v[i] < 0) {         // Dacă găsim un număr negativ
            niciunNegativ = false; // Atunci avem cel puțin un negativ
            break;                 // Ieșim din buclă
        }
    }
    
    if (niciunNegativ) {
        cout << "NICIUN element nu este negativ." << endl;
    } else {
        cout << "Există cel puțin un element negativ." << endl;
    }
    
    return 0;
}

Aici ai „traducerea” pe care o folosim la clasă: întâi pseudocod (pașii), apoi varianta C++ (de copiat și rulat).

// PROPRIETATE EXEMPLU: "număr par" (P(x) = x este par) // ÎNTREBARE: Toate elementele sunt pare? ok ← true pentru i ← 0..n-1 execută dacă v[i] este impar atunci ok ← false oprește dacă ok atunci scrie "DA" altfel scrie "NU"

C++ (echivalent) — „toate pare”

bool ok = true;
for (int i = 0; i < n; i++) {
    if (v[i] % 2 != 0) {   // contraexemplu: impar
        ok = false;
        break;
    }
}
cout << (ok ? "DA" : "NU");

// ÎNTREBARE: Există cel puțin un element par? gasit ← false pentru i ← 0..n-1 execută dacă v[i] este par atunci gasit ← true oprește dacă gasit atunci scrie "DA" altfel scrie "NU"

C++ (echivalent) — „există par”

bool gasit = false;
for (int i = 0; i < n; i++) {
    if (v[i] % 2 == 0) {   // exemplu: par
        gasit = true;
        break;
    }
}
cout << (gasit ? "DA" : "NU");

// ÎNTREBARE: Niciun element nu este 0? ok ← true pentru i ← 0..n-1 execută dacă v[i] = 0 atunci ok ← false oprește dacă ok atunci scrie "DA" altfel scrie "NU"

C++ (echivalent) — „niciun zero”

bool ok = true;
for (int i = 0; i < n; i++) {
    if (v[i] == 0) {   // contraexemplu: am găsit 0
        ok = false;
        break;
    }
}
cout << (ok ? "DA" : "NU");

Observă că „oprește” din pseudocod devine break; în C++. Îl folosim ca să nu parcurgem degeaba restul vectorului.

Rețetele standard (exact ca în problemele de tip „DA/NU”)

Când verifici o proprietate într-un vector, alegi una din cele 3 întrebări: „toate?”, „există?”, „niciunul?”. Diferența dintre ele este valoarea inițială a flag-ului și condiția care îl schimbă.

Întrebare	Flag inițial	Când îl schimb?	Ce caut?
Toate elementele au proprietatea P?	`true`	când găsesc un element care NU are P	contraexemplu
Există cel puțin un element cu P?	`false`	când găsesc un element care ARE P	exemplu
Niciun element nu are P?	`true`	când găsesc un element care ARE P	contraexemplu

📋 Șablon 1: „TOATE” (flag pornește true)

bool ok = true;
for (int i = 0; i < n; i++) {
    if ( /* v[i] NU are proprietatea P */ ) {
        ok = false;
        break;
    }
}

📋 Șablon 2: „EXISTĂ” (flag pornește false)

bool gasit = false;
for (int i = 0; i < n; i++) {
    if ( /* v[i] ARE proprietatea P */ ) {
        gasit = true;
        break;
    }
}

📋 Șablon 3: „NICIUNUL” (flag pornește true)

bool ok = true;
for (int i = 0; i < n; i++) {
    if ( /* v[i] ARE proprietatea P */ ) {
        ok = false;
        break;
    }
}

Truc: dacă întrebarea e de tip „DA/NU”, aproape sigur ai un flag + o singură parcurgere. Folosește break când ai aflat răspunsul, ca să nu muncești degeaba.

Greșeli care apar foarte des (și cum le eviți)

Câteva detalii mici fac diferența între un program corect și unul care „pare” corect. Ține minte cele două reguli de mai jos.

1) `=` NU este `==`

❌ Greșit: if (ok = true) (aici faci atribuire!)

✅ Corect: if (ok == true) sau mai simplu: if (ok)

2) Negarea cu `!`

Dacă ai o funcție care întoarce true/false, negarea e foarte utilă:

// dacă NU e prim:
if (!estePrim(v[i])) {
    // atunci proprietatea „toate sunt prime” pică
}

Când verifici „toate sunt pozitive”, condiția corectă pentru eșec este v[i] <= 0, nu doar v[i] < 0 (0 nu este pozitiv).

Exercițiu de completare - Verificare elemente pare

Completează TOATE spațiile libere din codul C++ pentru verificarea dacă toate elementele sunt pare:

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

const int MAX = 1000;

int v[MAX];

// Citire vector

for (int i = 0; i < n; i++) {

cin >> v[i];

}

// Verificare: toate elementele sunt pare?

bool toatePare = ______;

for (int i = 0; i < n; i++) {

if (v[i] % 2 ______ 0) {

toatePare = ______;

______;

}

if (______) {

cout << "Toate sunt pare" << endl;

} else {

cout << "Nu toate sunt pare" << endl;

}

return ______;

}

Bancă de cuvinte:

true false != break toatePare 0

Click pe un spațiu liber, apoi pe un cuvânt din bancă.

Test de înțelegere: Care este strategia corectă?

Test rapid - alegerea flag-ului inițial:

Pentru fiecare situație, alege valoarea inițială corectă a flag-ului:

Verificare:
"Toate elementele sunt pozitive"

Verificare:
"Există cel puțin un element par"

Verificare:
"Niciun element nu este zero"

Verificarea proprietăților complexe: Număr prim & Număr perfect

1. Număr prim

Definiție: Un număr prim este un număr natural mai mare decât 1 care are exact doi divizori: 1 și el însuși.

✅ Funcție care verifică dacă un număr este prim

bool estePrim(int x) {
    // Numerele mai mici decât 2 nu sunt prime
    if (x < 2) return false;
    
    // 2 este singurul număr prim par
    if (x == 2) return true;
    
    // Dacă e par și mai mare ca 2, nu e prim
    if (x % 2 == 0) return false;
    
    // Verificăm divizorii impari până la sqrt(x)
    for (int d = 3; d * d <= x; d += 2) {
        if (x % d == 0) {
            return false;  // Am găsit un divizor, deci nu e prim
        }
    }
    
    return true;  // Nu am găsit divizori, deci e prim
}

// Exemplu de utilizare în verificarea unui vector:
bool toatePrime = true;
for (int i = 0; i < n; i++) {
    if (!estePrim(v[i])) {  // Dacă NU e prim
        toatePrime = false;
        break;
    }
}

2. Număr perfect

Definiție: Un număr perfect este un număr natural egal cu suma divizorilor săi proprii (toți divizorii mai mici decât numărul însuși, inclusiv 1).
Exemplu: 6 = 1 + 2 + 3 (6 este perfect)

// Funcție care verifică dacă un număr este perfect
bool estePerfect(int x) {
    // Cel mai mic număr perfect este 6
    if (x < 2) {
        return false;
    }
    
    // 1 este divizor pentru orice număr > 1
    int sumaDivizori = 1;
    
    // Căutăm divizori începând de la 2 până la sqrt(x)
    for (int d = 2; d * d <= x; d++) {
        if (x % d == 0) {
            // Adăugăm divizorul d
            sumaDivizori += d;
            
            // Dacă d != x/d, adăugăm și celălalt divizor
            if (d != x / d) {
                sumaDivizori += x / d;
            }
        }
    }
    
    // Verificăm dacă suma divizorilor proprii este egală cu numărul
    return (sumaDivizori == x);
}

/* Exemplu de utilizare:
   Verificăm dacă există cel puțin un număr perfect în vector */
bool existaPerfect = false;
for (int i = 0; i < n; i++) {
    if (estePerfect(v[i])) {
        existaPerfect = true;
        break;
    }
}

Primele numere perfecte: 6, 28, 496, 8128, 33550336, ...

Observație: Toate numerele perfecte pare se termină în 6 sau 28.

Sfaturi practice pentru verificarea proprietăților

Alege corect valoarea inițială a flag-ului

"Toate" → true
"Există" → false
"Niciun" → true

Folosește break pentru optimizare

Odată ce știi răspunsul final, nu mai are rost să continui verificarea.

Separă verificările complexe în funcții

Scrie funcții separate pentru estePrim(), estePerfect(), estePalindrom() etc.

Testează cu cazuri limită

Vector gol, vector cu 1 element, toate elemente egale, valori extreme.

Încălzire (2 minute)

Test rapid - identificare strategie flag: Pentru fiecare verificare, spune dacă începi cu true sau false:

Toate elementele sunt mai mari decât 10 → verifică
Există cel puțin un element egal cu 0 → verifică
Niciun element nu este mai mic decât -5 → verifică

📌 Regulă: "Toate" → true, "Există" → false, "Niciun" → true

PROBLEME PBINFO - 15 minute (3 probleme)

PbInfo #402 - Toate elementele pozitive

Enunț:

Cerință: Se citește un număr n și apoi n numere întregi. Să se verifice dacă toate elementele sunt pozitive.

Date de intrare:

Programul citește de la tastatură numărul n, apoi n numere întregi.

Date de ieșire:

Programul va afișa pe ecran "DA" dacă toate elementele sunt pozitive, altfel va afișa "NU".

Exemplu:

Intrare:

5
10 20 5 30 15

Ieșire:

DA

Scrie soluția în C++:

Soluție corectă:

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    const int MAX = 1000;
    int v[MAX];
    
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    
    bool toatePozitive = true;
    
    for (int i = 0; i < n; i++) {
        if (v[i] <= 0) {
            toatePozitive = false;
            break;
        }
    }
    
    if (toatePozitive) {
        cout << "DA" << endl;
    } else {
        cout << "NU" << endl;
    }
    
    return 0;
}

PbInfo #403 - Există cel puțin un număr par

Enunț:

Cerință: Se citește un număr n și apoi n numere întregi. Să se verifice dacă există cel puțin un număr par în șir.

Date de intrare:

Programul citește de la tastatură numărul n, apoi n numere întregi.

Date de ieșire:

Programul va afișa pe ecran "DA" dacă există cel puțin un număr par, altfel va afișa "NU".

Exemplu:

Intrare:

5
7 3 9 2 5

Ieșire:

DA

Scrie soluția în C++:

Soluție corectă:

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    const int MAX = 1000;
    int v[MAX];
    
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    
    bool existaPar = false;
    
    for (int i = 0; i < n; i++) {
        if (v[i] % 2 == 0) {
            existaPar = true;
            break;
        }
    }
    
    if (existaPar) {
        cout << "DA" << endl;
    } else {
        cout << "NU" << endl;
    }
    
    return 0;
}

PbInfo #404 - Niciun element nu este zero

Enunț:

Cerință: Se citește un număr n și apoi n numere întregi. Să se verifice dacă niciun element nu este egal cu 0.

Date de intrare:

Programul citește de la tastatură numărul n, apoi n numere întregi.

Date de ieșire:

Programul va afișa pe ecran "DA" dacă niciun element nu este 0, altfel va afișa "NU".

Exemplu:

Intrare:

5
10 20 5 30 15

Ieșire:

DA

Scrie soluția în C++:

Soluție corectă:

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    const int MAX = 1000;
    int v[MAX];
    
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    
    bool niciunZero = true;
    
    for (int i = 0; i < n; i++) {
        if (v[i] == 0) {
            niciunZero = false;
            break;
        }
    }
    
    if (niciunZero) {
        cout << "DA" << endl;
    } else {
        cout << "NU" << endl;
    }
    
    return 0;
}

EXERCIȚII PRACTICE - 10 minute

Exercițiul Practic: Verificări complexe cu flag-uri

Sarcini de lucru

Completează următoarele sarcini pentru a-ți consolida cunoștințele despre verificarea proprietăților

Sarcina 1: Analiză și corectare cod

Analizează următorul cod și găsește greșelile:

#include <iostream>
using namespace std;

int main() {
    int n = 5;
    int vector[5] = {8, 3, 10, 2, 7};
    
    // Verificare: toate elementele sunt mai mari decât 5?
    bool toateMaiMari = false;  // începem cu false
    
    for (int i = 0; i < n; i++) {
        if (vector[i] > 5) {
            toateMaiMari = true;
        }
    }
    
    if (toateMaiMari = true) {
        cout << "Toate sunt mai mari decat 5" << endl;
    } else {
        cout << "Nu toate sunt mai mari decat 5" << endl;
    }
    
    return 0;
}

Scrie aici greșelile găsite și corecțiile:

Soluție pentru Sarcina 1:

Greșeli identificate și corecții:

1. Valoare inițială greșită a flag-ului: bool toateMaiMari = false; este greșit pentru verificarea "toate".
Corect: bool toateMaiMari = true;
2. Logica inversă în buclă: Când găsim un element care NU este mai mare decât 5, ar trebui să setăm flag-ul pe false.
Corect: if (vector[i] <= 5) toateMaiMari = false;
3. Lipsă break pentru optimizare: Odată ce am găsit un contraexemplu, nu mai are rost să continuăm.
Corect: Adăugăm break; după setarea flag-ului pe false.
4. Eroare de atribuire în loc de comparație: if (toateMaiMari = true) este atribuire, nu comparație.
Corect: if (toateMaiMari == true) sau simplu if (toateMaiMari)

Sarcina 2: Implementare completă

Cerință: Scrie un program care citește n, apoi n numere. Programul verifică și afișează:

Dacă toate elementele sunt pozitive
Dacă există cel puțin un element par
Dacă niciun element nu este mai mic decât -10
Dacă toate elementele sunt mai mici decât 100

Cod C++ complet:

Soluție pentru Sarcina 2:

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    const int MAX = 1000;
    int v[MAX];
    
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    
    // 1. Toate elementele sunt pozitive?
    bool toatePozitive = true;
    for (int i = 0; i < n; i++) {
        if (v[i] <= 0) {
            toatePozitive = false;
            break;
        }
    }
    
    // 2. Există cel puțin un element par?
    bool existaPar = false;
    for (int i = 0; i < n; i++) {
        if (v[i] % 2 == 0) {
            existaPar = true;
            break;
        }
    }
    
    // 3. Niciun element nu este mai mic decât -10?
    bool niciunMaiMicCaMinus10 = true;
    for (int i = 0; i < n; i++) {
        if (v[i] < -10) {
            niciunMaiMicCaMinus10 = false;
            break;
        }
    }
    
    // 4. Toate elementele sunt mai mici decât 100?
    bool toateMaiMiciCa100 = true;
    for (int i = 0; i < n; i++) {
        if (v[i] >= 100) {
            toateMaiMiciCa100 = false;
            break;
        }
    }
    
    cout << "1. Toate elementele sunt pozitive: " 
         << (toatePozitive ? "DA" : "NU") << endl;
    cout << "2. Exista cel putin un element par: " 
         << (existaPar ? "DA" : "NU") << endl;
    cout << "3. Niciun element nu este mai mic decat -10: " 
         << (niciunMaiMicCaMinus10 ? "DA" : "NU") << endl;
    cout << "4. Toate elementele sunt mai mici decat 100: " 
         << (toateMaiMiciCa100 ? "DA" : "NU") << endl;
    
    return 0;
}

Ce vei învăța astăzi?

Ce este un FLAG (steguleț)?

DEMONSTRAȚIE FLAG

Analogii pentru a înțelege flag-urile:

Prima întrebare corectă: „Toate?”, „Există?”, „Niciunul?”

Algoritmi pentru verificarea proprietăților

Rețetele standard (exact ca în problemele de tip „DA/NU”)

Greșeli care apar foarte des (și cum le eviți)

1) = NU este ==

2) Negarea cu !

Exercițiu de completare - Verificare elemente pare

Completează TOATE spațiile libere din codul C++ pentru verificarea dacă toate elementele sunt pare:

Bancă de cuvinte:

Test de înțelegere: Care este strategia corectă?

Test rapid - alegerea flag-ului inițial:

Verificarea proprietăților complexe: Număr prim & Număr perfect

1. Număr prim

2. Număr perfect

Sfaturi practice pentru verificarea proprietăților

Încălzire (2 minute)

PbInfo #402 - Toate elementele pozitive

Enunț:

Date de intrare:

Date de ieșire:

Exemplu:

Scrie soluția în C++:

Soluție corectă:

PbInfo #403 - Există cel puțin un număr par

Enunț:

Date de intrare:

Date de ieșire:

Exemplu:

Scrie soluția în C++:

Soluție corectă:

PbInfo #404 - Niciun element nu este zero

Enunț:

Date de intrare:

Date de ieșire:

Exemplu:

Scrie soluția în C++:

Soluție corectă:

Exercițiul Practic: Verificări complexe cu flag-uri

Sarcini de lucru

Sarcina 1: Analiză și corectare cod

Soluție pentru Sarcina 1:

Sarcina 2: Implementare completă

Soluție pentru Sarcina 2:

Descarcă toate exercițiile și soluțiile

1) `=` NU este `==`

2) Negarea cu `!`