Verificarea proprietăților unui vector

De ce contează?

Vrei să verifici dacă o serie de măsurători e mereu crescătoare, dacă un cod e format doar din cifre pozitive, sau dacă un șir se citește la fel de la stânga și de la dreapta. Toate sunt variante ale aceleiași idei: parcurgi vectorul și verifici o condiție, oprindu-te imediat ce găsești primul element care o încalcă.

Tiparul general

ok ← adevarat
pentru i de la 0 la n-1:
    daca v[i] nu respecta conditia:
        ok ← fals
        stop   ← iesire timpurie
daca ok: proprietatea e indeplinita

Ieșirea timpurie e importantă la concursuri: nu continuăm verificarea după ce am găsit prima „greșeală". Dacă primele 3 elemente din 1.000 încalcă condiția, nu mai verificăm celelalte 997.

Sortat crescător

bool sortat = true;
for (int i = 0; i < n - 1; i++) {    // comparam perechi consecutive
    if (v[i] > v[i + 1]) {
        sortat = false;
        break;
    }
}

Comparăm n-1 perechi: (v[0],v[1]), (v[1],v[2]), ..., (v[n-2],v[n-1]).

Toate elementele pozitive

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

Vector palindrom

bool palindrom = true;
for (int i = 0; i < n / 2; i++) {
    if (v[i] != v[n - 1 - i]) {
        palindrom = false;
        break;
    }
}

Implementare C++ completă

#include <iostream>
using namespace std;

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

    bool sortat = true;
    for (int i = 0; i < n - 1; i++) {
        if (v[i] > v[i + 1]) { sortat = false; break; }
    }

    bool palindrom = true;
    for (int i = 0; i < n / 2; i++) {
        if (v[i] != v[n - 1 - i]) { palindrom = false; break; }
    }

    cout << (sortat ? "sortat" : "nesortat") << "\n";
    cout << (palindrom ? "palindrom" : "nu palindrom") << "\n";
    return 0;
}

Complexitate

Verificare	Timp	Observație
Orice proprietate	O(n) în cel mai rău caz	Ieșire timpurie: adesea mai rapid

Observația-cheie

Toate verificările urmează același tipar: bool ok = true; for (...) { if (conditie_rea) { ok = false; break; } }. Schimbi doar condiția, nu structura. Recunoașterea tiparului te ajută să scrii rapid oricare verificare nouă.

Greșeli frecvente

Greșeala 1: Bucla pentru „sortat" merge până la i < n în loc de i < n-1 — accesezi v[n], care e în afara vectorului.

Greșeala 2: Nu folosești break după ok = false — verificarea continuă inutil; la concurs pierzi timp prețios pe date mari.

Greșeala 3: Verifici palindromul cu bucla i < n în loc de i < n/2 — compari fiecare pereche de două ori și, dacă n e impar, compari elementul din mijloc cu el însuși (inofensiv, dar irositor).

Recapitulare

Toate verificările: parcurgi vectorul, la primul element „rău" setezi ok=false și faci break.
„Sortat" compară perechi consecutive: bucla merge până la i < n-1.
Palindromul compară simetric: bucla merge până la i < n/2.