De ce contează?
Temperatura de ieri era 20°C, azi e 25°C — s-a schimbat. Mulți algoritmi nu depind doar de valoarea curentă, ci de relația ei cu cea de dinainte. Variabila prev îți dă exact asta: memoria unui singur pas înapoi.
Când ai nevoie de prev?
Ori de câte ori logica depinde de relația elementului curent cu cel anterior:
- Numărul de schimbări de valoare dintr-un șir
- Verificarea că șirul e strict crescător (sau descrescător)
- Detectarea momentului când o proprietate „pornește" sau „se oprește"
- Lungimea unui bloc de valori consecutive egale
Algoritmul
Șir: 3 3 5 5 5 2
tranzitii = 0
prev = 3 (primul element)
x=3: 3 == prev → nimic
x=5: 5 != prev → tranzitii++, prev = 5
x=5: 5 == prev → nimic
x=5: 5 == prev → nimic
x=2: 2 != prev → tranzitii++, prev = 2
Rezultat: tranzitii = 2Implementare C++
#include <iostream>
#include <fstream>
using namespace std;
int main() {
ifstream fin("tranzitii.in");
ofstream fout("tranzitii.out");
int n;
fin >> n;
int prev;
fin >> prev; // primul element devine prev initial
int tranzitii = 0;
for (int i = 1; i < n; i++) { // incepem de la al doilea element
int x;
fin >> x;
if (x != prev) {
tranzitii++;
prev = x; // actualizeaza prev la fiecare pas
}
}
fout << tranzitii << "\n";
return 0;
}Exemplu: 6 / 3 3 5 5 5 2 → 2
Verificarea unui șir strict crescător
Același tipar cu prev, schimbi doar condiția:
fin >> prev;
bool crescator = true;
for (int i = 1; i < n; i++) {
int x; fin >> x;
if (x <= prev) { crescator = false; break; }
prev = x;
}Actualizează prev = x la fiecare iterație, nu doar când detectezi o schimbare. Dacă o faci condiționat, prev rămâne blocat la o valoare veche și comparația de la pasul următor e greșită.
Complexitate
| Caz | Timp | Spațiu |
|---|---|---|
| Procesare cu prev | O(n) | O(1) |
Greșeala 1: Inițializezi prev = 0 în loc să citești primul element separat. Dacă primul element e 0, funcționează întâmplător. Dacă e altceva, prima comparație e greșită.
Greșeala 2: Uiți prev = x la sfârșitul buclei. prev trebuie actualizat la fiecare iterație, altfel compari mereu cu primul element.
Greșeala 3: Pornești bucla de la i = 0 în loc de i = 1 după ce ai citit primul element separat. Vei citi primul element de două ori.