Invariantul unei bucle la BAC: justificare și exemple

Un invariant de buclă este o afirmație despre variabilele algoritmului care rămâne adevărată într-un moment precis al fiecărei repetări. El te ajută să explici de ce programul produce rezultatul cerut, nu doar să observi că funcționează pentru câteva exemple. La BAC, această metodă este utilă când urmărești un pseudocod, corectezi o inițializare sau justifici un algoritm eficient.

Nu ai nevoie de un limbaj complicat. O propoziție precum „contorul reprezintă numărul valorilor pozitive citite până acum” poate fi un invariant, dacă precizezi când o verifici. Vom construi explicația pe un algoritm simplu și apoi vom vedea cum îl folosești la alte cerințe din subiectele de BAC.

Ce problemă rezolvăm

Se citesc un număr natural de elemente, cel mult o sută de mii, apoi atâtea numere întregi. Cerința este să afișăm câte dintre valorile citite sunt strict pozitive. Zero nu este pozitiv, iar valorile negative nu se numără.

Pentru secvența minus doi, cinci, zero, șapte și minus unu, răspunsul este doi. Programul nu trebuie să păstreze toate valorile. Are nevoie de numărul elementelor deja prelucrate și de un contor al celor care îndeplinesc proprietatea.

Această problemă este suficient de simplă încât să poți verifica fiecare pas. Tocmai de aceea este potrivită pentru a învăța justificarea, înainte să o aplici la algoritmi cu mai multe variabile și condiții.

Alegerea momentului de verificare

Vom verifica invariantul la începutul fiecărei iterații. Variabila de parcurgere pornește de la zero și arată câte elemente au fost deja prelucrate. Contorul arată câte dintre aceste elemente sunt strict pozitive.

Afirmația completă este: înainte de citirea următoarei valori, contorul este numărul valorilor pozitive dintre primele elemente deja prelucrate. Dacă schimbi momentul și verifici după citire, dar înainte de actualizarea contorului, trebuie să adaptezi formularea. O afirmație corectă într-un punct al buclei poate fi temporar falsă în alt punct.

Început de pas	Elemente deja prelucrate	Număr de valori pozitive
1	Niciun element	0
2	Minus doi	0
3	Minus doi, cinci	1
4	Minus doi, cinci, zero	1
5	Minus doi, cinci, zero, șapte	2

După prelucrarea ultimei valori, toate cele cinci elemente au fost analizate, iar contorul este doi. Tabelul arată semnificația stării, nu doar o listă de calcule fără explicație.

Ce trebuie demonstrat în trei etape

Inițializarea: înaintea primei iterații nu am prelucrat niciun element. Numărul valorilor pozitive dintr-o secvență goală este zero, deci inițializarea contorului cu zero face afirmația adevărată.

Păstrarea: presupunem că afirmația este adevărată înainte de un pas. Citim o valoare. Dacă este pozitivă, numărul valorilor pozitive crește cu unu, iar programul mărește contorul cu unu. Dacă nu este pozitivă, nici numărul cerut, nici contorul nu se schimbă. După actualizarea indicelui, afirmația este adevărată pentru prefixul mai lung.

Rezultatul la ieșire: când au fost prelucrate toate elementele, prefixul despre care vorbește invariantul este întregul șir. Contorul reprezintă deci exact numărul cerut. Acesta este motivul pentru care îl putem afișa.

Programul C++ corespunzător

#include <iostream>
using namespace std;

int main() {
    int n, x, pozitive = 0;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> x;
        if (x > 0) ++pozitive;
    }
    cout << pozitive;
    return 0;
}

Programul acceptă și zero elemente, conform domeniului declarat. În acest caz, bucla nu rulează și răspunsul este zero. Dacă un enunț precizează că șirul este nevid, algoritmul continuă să fie corect, dar testul cu șirul vid rămâne doar o verificare suplimentară a implementării noastre.

Condiția folosește comparația strictă cu zero. Înlocuirea ei cu o comparație care include egalitatea ar schimba proprietatea numărată în „valori nenegative”. Invariantul ar trebui schimbat și el. Nu este suficient ca variabila să se numească „pozitive”; instrucțiunile trebuie să respecte sensul ales.

Invariantul nu dovedește singur terminarea

O buclă poate păstra o proprietate și totuși să nu se oprească. Pentru programul de mai sus, mai avem nevoie să observăm că indicele crește cu unu și este limitat de numărul elementelor. Numărul elementelor rămase de prelucrat scade la fiecare pas până la zero.

Această cantitate care scade este un argument de terminare. Nu o confunda cu invariantul: unul explică progresul către oprire, celălalt explică sensul variabilelor în timpul parcurgerii. Împreună susțin corectitudinea completă a algoritmului, în condițiile intrării specificate.

Dacă uiți incrementarea indicelui într-o buclă scrisă manual, contorul poate continua să fie actualizat pentru valori noi, dar numărul de pași nu mai este controlat corect. O justificare care verifică și terminarea te obligă să observi acest defect.

Cum găsești un invariant într-un program necunoscut

Pornește de la variabila care va fi afișată. Întreabă-te ce ar putea reprezenta după câteva iterații: o sumă, un număr de apariții, un maxim, un produs ori o proprietate logică. Calculează două sau trei exemple mici și caută o propoziție care le explică pe toate.

Apoi verifică inițializarea. O sumă pornește de obicei de la zero, un produs de la unu, iar un extrem al unui șir nevid poate porni de la primul element. Aceste valori nu sunt interschimbabile. Semnificația variabilei ar trebui să îți spună de ce a fost aleasă fiecare.

În final, urmărește o iterație simbolică. Nu te limita la valorile concrete din exemplu. Arată ce se întâmplă pentru un element care îndeplinește condiția și pentru unul care nu o îndeplinește. Dacă ambele cazuri păstrează afirmația, ai o justificare mai puternică decât o simplă simulare.

Cum descoperi o inițializare greșită

Dacă în problema noastră contorul ar porni de la unu, invariantul ar fi fals înainte de prima citire: nu există încă nicio valoare pozitivă prelucrată. La final, rezultatul ar fi mai mare cu unu decât cel corect.

Un test cu toate valorile negative ar descoperi rapid eroarea, fiindcă răspunsul așteptat este zero. Justificarea prin invariant o descoperă chiar înainte să rulezi programul. Cele două metode se completează: demonstrația explică regula, testul verifică implementarea concretă.

Acesta este un mod practic de a aplica învățarea prin înțelegere: înlocuiești memorarea unei inițializări cu o propoziție care o impune logic.

Exerciții cu răspunsuri

Un acumulator adună valorile pare citite. Care este invariantul? La începutul fiecărui pas, acumulatorul este suma valorilor pare dintre elementele deja prelucrate. Inițializarea este zero. Pentru un element impar, suma rămâne neschimbată.

Un contor crește când două valori vecine sunt egale. Ce prefix descrii? Trebuie să vorbești despre perechile vecine deja verificate, nu doar despre numărul elementelor citite. Primul element singur nu formează nicio pereche.

Un maxim pornește de la zero, iar intrarea poate conține numai numere negative. Este corect? Nu. Zero poate rămâne rezultat fără să aparțină șirului. Inițializarea cu primul element al unui șir nevid păstrează semnificația de maxim al prefixului.

O buclă împarte repetat un număr pozitiv la zece. Ce dovedește terminarea? Valoarea naturală scade strict cât timp este pozitivă, până când devine zero. Invariantul despre suma cifrelor, dacă există un asemenea acumulator, este o afirmație separată.

Întrebări frecvente

Trebuie să folosesc neapărat cuvântul invariant la BAC?

Formularea cerută depinde de exercițiu. Chiar dacă nu se solicită o demonstrație formală, precizarea sensului variabilelor te ajută să construiești și să verifici rezolvarea. Răspunde întotdeauna cerinței concrete.

Un exemplu corect este o demonstrație?

Nu pentru toate intrările. Exemplul arată că algoritmul funcționează pe acele date. Invariantul descrie o proprietate generală și explică de ce ea este păstrată la fiecare pas.

Cum pot exersa explicațiile?

Alege un program scurt și scrie o propoziție pentru fiecare acumulator. Verifică începutul, un pas și finalul. Poți cere feedback pe aceste propoziții unui profesor din anunțurile de informatică.