Backtracking la BAC: numărarea șirurilor binare

Numărarea soluțiilor prin backtracking cere să deosebești o construcție parțială validă de o soluție completă. La BAC, nu fiecare apel recursiv reprezintă un răspuns. Numărăm o soluție numai când toate pozițiile cerute au fost completate și restricțiile sunt respectate.

Lecția privește metoda backtracking de la matematică-informatică. Vom număra șirurile binare de lungime n în care nu apar două valori unu consecutive. Lungimea este între zero și douăzeci și cinci, pentru ca enumerarea recursivă să rămână potrivită exemplului. Pentru un subiect de BAC, verifică separat dacă se cere enumerare, numărare sau doar o anumită soluție.

Ce construiește un nivel

La fiecare nivel alegem valoarea unei poziții: zero sau unu. Prefixul construit până atunci trebuie să respecte restricția. Dacă ultimul element este unu, următoarea alegere poate fi numai zero.

Dacă ultimul element este zero sau nu am ales încă nimic, ambele valori sunt posibile. Restricția depinde numai de elementul anterior, deci nu trebuie să verificăm din nou toate perechile din prefix la fiecare pas.

Această observație reduce starea necesară pentru numărare. Păstrăm câte poziții au fost completate și valoarea anterioară. Nu trebuie să memorăm întregul șir dacă nu avem obligația să îl afișăm.

Prefix valid și soluție completă

Pentru lungimea trei, prefixul zero, unu este valid, dar încă nu reprezintă o soluție completă. Mai lipsește o poziție. Poate fi completat numai cu zero, obținând șirul zero, unu, zero.

Prefixul unu, unu este invalid și nu trebuie extins. Orice completare ar păstra perechea interzisă deja formată. Respingerea lui imediată evită explorarea unor ramuri care nu pot produce rezultate.

Prefix	Valid?	Complet pentru lungimea 3?
0, 1	Da	Nu
1, 1	Nu	Nu
1, 0, 1	Da	Da

Un prefix valid poate avea mai multe completări, una singură sau niciuna, în funcție de restricțiile problemei. În exemplul nostru, alegerea zero este mereu disponibilă cât timp mai există poziții de completat.

Program C++ pentru numărare

Funcția primește numărul pozițiilor deja completate, lungimea totală și valoarea precedentă. Pentru primul apel folosim zero ca valoare precedentă convențională, astfel încât prima poziție să poată primi atât zero, cât și unu.

#include <iostream>
using namespace std;

long long numara(int k, int n, int precedent) {
    if (k == n) return 1;
    long long total = numara(k + 1, n, 0);
    if (precedent == 0)
        total += numara(k + 1, n, 1);
    return total;
}

int main() {
    int n;
    cin >> n;
    cout << numara(0, n, 0);
    return 0;
}

Returnarea lui unu în cazul de bază înseamnă că prefixul curent este o soluție completă. Celelalte apeluri adună numărul completărilor din ramurile permise. Nu adaugă automat unu pentru ele însele.

Enumerarea de control pentru lungimea trei

Șirurile valide sunt 000, 001, 010, 100 și 101. Sunt cinci. Celelalte trei șiruri binare de lungime trei conțin cel puțin o pereche de valori unu consecutive și sunt excluse.

Ramura care începe cu zero are trei completări valide: 000, 001, 010. Ramura care începe cu unu are două: 100, 101. Suma este cinci, în acord cu rezultatul funcției.

Această descompunere este o verificare mai bună decât simpla memorare a numărului cinci. Ea arată că ramurile sunt disjuncte și că fiecare soluție aparține exact uneia, după prima valoare aleasă.

De ce nu apar dubluri

Fiecare traseu de la început până la lungimea n fixează o succesiune unică de alegeri. Două trasee care diferă la o poziție produc șiruri diferite. Nu există o reordonare ulterioară care să transforme două trasee în aceeași soluție.

În același timp, orice șir valid poate fi urmărit de la stânga la dreapta prin alegerile permise ale algoritmului. Dacă un element este unu, precedentul său nu este unu, deci ramura corespunzătoare nu este eliminată.

Aceste două argumente justifică numărarea exactă: fiecare soluție validă apare și niciuna nu este numărată de două ori. Numărul afișat nu este doar rezultatul unor apeluri care par să exploreze multe posibilități.

Lungimea zero și șirul vid

Pentru lungimea zero există un singur șir: șirul vid. Nu conține nicio pereche interzisă, deci este valid. Apelul inițial ajunge direct la cazul de bază și returnează unu.

Această convenție este utilă matematic pentru numărarea completărilor. Dacă o problemă admite numai lungimi pozitive, nu vei primi zero la intrare, dar cazul de bază al recursivității tot exprimă o completare terminată.

Nu confunda „nu mai sunt poziții de ales” cu „nu există nicio soluție”. În primul caz, alegerile deja făcute formează o soluție completă. Zero soluții înseamnă că nu există nicio completare permisă pentru starea analizată.

O recurență pentru verificarea numărului

Pentru lungimi de cel puțin doi, șirurile valide se pot împărți după început. Cele care încep cu zero lasă o problemă de lungime mai mică cu unu. Cele care încep cu unu trebuie să continue cu zero și lasă o problemă de lungime mai mică cu doi.

Astfel, numărul pentru o lungime este suma numerelor pentru cele două lungimi anterioare. Valorile inițiale sunt unu pentru lungimea zero și doi pentru lungimea unu. Urmează trei, cinci, opt și treisprezece.

Această recurență permite un algoritm de numărare mai rapid, cu rezultate memorate sau calcul iterativ. Programul prezentat urmărește însă structura ramificării de tip backtracking. Pentru lungimi foarte mari, enumerarea tuturor completărilor nu ar fi alegerea eficientă.

Timp și memorie

Numărul ramurilor crește rapid cu lungimea, deși restricția elimină o parte dintre șirurile binare posibile. Timpul acestei implementări este exponențial în lungime. Nu este liniar doar fiindcă fiecare traseu are cel mult n niveluri.

Adâncimea maximă a apelurilor este proporțională cu lungimea. La un moment dat se păstrează traseul activ, nu toate traseele simultan, deci memoria de stivă este liniară. Tipul rezultatului trebuie să poată păstra numărul total de soluții.

Separarea dintre numărul nodurilor explorate și adâncimea arborelui ajută la înțelegerea complexității. Ele măsoară lucruri diferite și nu trebuie înlocuite una cu cealaltă.

Exerciții cu răspunsuri

Lungimea este unu. Șirurile sunt zero și unu, deci rezultatul este doi.

Lungimea este doi. Șirurile sunt 00, 01, 10, deci rezultatul este trei. Șirul 11 este exclus.

Lungimea este patru. Rezultatul este opt, obținut și prin suma dintre cinci și trei.

Prefixul se termină în unu. Următoarea valoare trebuie să fie zero. Alegerea lui unu ar încălca restricția imediat.

Întrebări frecvente

Pot număra fiecare apel ca soluție?

Nu. Majoritatea apelurilor descriu prefixe incomplete. Numără numai stările în care toate pozițiile au fost completate valid.

De ce nu folosim un vector pentru șir?

Cerința solicită doar numărul soluțiilor, iar validarea depinde numai de valoarea precedentă. Pentru afișarea fiecărui șir, ar trebui păstrate și alegerile de pe traseu.

Cum verific un alt algoritm de numărare?

Enumeră manual cazurile mici și compară totalurile, apoi justifică lipsa dublurilor și acoperirea tuturor soluțiilor. Pentru feedback pe arborele de căutare, poți consulta un profesor de informatică.