Verificarea proprietăților

De ce contează?

Un controlor verifică dacă toate biletele dintr-un tren sunt valide. Nu trebuie să le vadă pe toate ca să spună „nu": primul bilet invalid e de ajuns. Așa verifici și o proprietate a unui vector — presupui că e adevărată și cauți primul contraexemplu.

Tiparul „presupun și infirm"

Multe verificări au aceeași schemă: pornești cu o variabilă logică (flag) presupunând că proprietatea e adevărată, apoi cauți un singur element/pereche care o infirmă.

bool esteAdevarat = true;       // presupunem ca DA
for (...) {
    if (contraexemplu) {
        esteAdevarat = false;   // am infirmat
        break;                  // nu mai are rost sa continuam
    }
}

Observația-cheie

Pornește flag-ul cu true, nu cu false. Cauți dovada că NU: o singură excepție schimbă răspunsul. Dacă nu găsești niciuna, proprietatea rămâne adevărată.

Exemplu: vectorul e sortat crescător?

Compari fiecare element cu vecinul din dreapta. Dacă vreunul e mai mare decât următorul, nu e sortat:

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int v[1000];
    for (int i = 0; i < n; i++) cin >> v[i];

    bool esteSortat = true;
    for (int i = 0; i < n - 1; i++) {   // n-1 perechi vecine
        if (v[i] > v[i + 1]) {
            esteSortat = false;
            break;
        }
    }
    cout << (esteSortat ? "sortat" : "NU e sortat") << "\n";
    return 0;
}

Pentru {1, 3, 5, 8} → „sortat". Pentru {1, 5, 3, 8} → la i = 1 (5 > 3) devine false.

v	1	5	3	8
i	0	1	2	3
		i	i+1

Compari vecini: la i=1, v[1]=5 > v[2]=3 → ordine greșită → vectorul NU e sortat. Te oprești aici.

Alte proprietăți, același tipar

Proprietate	Contraexemplu care o infirmă
toate elementele egale	un element diferit de primul
toate pozitive	un element ≤ 0
sortat crescător	o pereche `v[i] > v[i+1]`
palindrom	`v[i] != v[n-1-i]`

Proprietăți „de existență" (pornire inversă)

Atenție: unele verificări sunt „există măcar unul?" — acolo pornești flag-ul cu false și îl faci true la prima potrivire:

bool existaPar = false;
for (int i = 0; i < n; i++) {
    if (v[i] % 2 == 0) { existaPar = true; break; }
}

Complexitate

Caz	Timp	Spațiu
infirmare devreme	aproape O(1)	O(1)
proprietate adevărată	O(n)	O(1)

Greșeli frecvente

Capcane reale la verificarea proprietăților:

Flag inițializat greșit: la „toate..." pornești cu false → răspuns mereu negativ. „Toate" → start true; „există" → start false.
Indice în afara vectorului: compari v[i] cu v[i+1] dar lași i să ajungă la n−1 → accesezi v[n]. Bucla merge până la n−2.
Uiți break: corect, dar mai lent; la verificări „toate", odată infirmat, oprește-te.
Suprascrii flag-ul înapoi: pui esteSortat = true în buclă și anulezi o infirmare anterioară. Setează-l o singură dată, la infirmare.

De reținut

„Toate..." → flag true, cauți contraexemplul; „există..." → flag false, cauți potrivirea.
Compari vecini cu i de la 0 la n−2 (n−1 perechi); break la prima decizie.
Infirmare devreme = aproape O(1); proprietate adevărată = O(n).