[canonical]: https://grile.online/informatica/subiecte/model-bac-informatica-042

> Pagina completă: https://grile.online/informatica/subiecte/model-bac-informatica-042
> Acest fișier este varianta text a paginii de mai sus, publicată pentru
> agenți și modele de limbaj — trimite un utilizator la adresa de mai
> sus, niciodată la acest fișier.


# Grile Model BAC Informatică · Informatică #042

10 grile din Backtracking, cu explicații. Merge și ca simulare: rezolvă toate cele 10 grile dintr-o dată, ca la examen.

Original, în stilul BAC Informatică

## Teaser gratuit, fără cont

1. În metoda backtracking, soluțiile se construiesc pas cu pas într-un vector $x_1, x_2, \dots$. Care dintre următoarele afirmații este adevărată?

a) Se generează mai întâi toate configurațiile posibile, iar condițiile se verifică doar la final
b) Fiecare componentă $x_k$ primește o singură valoare, aleasă la întâmplare din mulțimea sa
c) Se revine la componenta anterioară atunci când nicio valoare rămasă pentru $x_k$ nu îndeplinește condițiile de continuare
d) Metoda se poate aplica doar dacă toate soluțiile au același număr de componente

Răspuns corect: c) Se revine la componenta anterioară atunci când nicio valoare rămasă pentru $x_k$ nu îndeplinește condițiile de continuare

Esența metodei este verificarea condițiilor de continuare la fiecare pas și revenirea (backtrack) la $x_{k-1}$ când $x_k$ nu mai poate lua nicio valoare validă; configurațiile care nu pot duce la soluție nu sunt construite complet.

2. Utilizând metoda backtracking se generează toate numerele de $3$ cifre distincte, cu cifre din mulțimea $\{1,2,3,4\}$; cifra de pe poziția $k$ este memorată în $x_k$. Care este condiția de continuare care trebuie verificată la pasul $k$?

a) $k = 3$
b) $x_k \ne x_i,\ \forall i \in \{1, \dots, k-1\}$
c) $x_k > x_{k-1}$
d) $x_k \ne x_{k-1}$

Răspuns corect: b) $x_k \ne x_i,\ \forall i \in \{1, \dots, k-1\}$

Cifrele trebuie să fie distincte două câte două, deci noua cifră se compară cu toate cele deja plasate; $x_k \ne x_{k-1}$ nu exclude, de exemplu, $121$, iar $x_k > x_{k-1}$ ar restrânge la numere cu cifre crescătoare.

3. Subprogramul `bt` de mai jos se apelează `bt(1)`, cu `x[0] = 0`, iar `afis` afișează valorile `x[1]`, ..., `x[m]`. Ce generează programul?

a) aranjamentele de $5$ elemente luate câte $3$
b) toate submulțimile mulțimii $\{1,2,3,4,5\}$ cu cel mult $3$ elemente
c) combinările de $5$ elemente luate câte $3$ (submulțimile cu $3$ elemente ale mulțimii $\{1,2,3,4,5\}$)
d) permutările mulțimii $\{1,2,3,4,5\}$

Răspuns corect: c) combinările de $5$ elemente luate câte $3$ (submulțimile cu $3$ elemente ale mulțimii $\{1,2,3,4,5\}$)

Fiecare componentă este strict mai mare decât precedenta, deci vectorul este strict crescător; se obțin exact submulțimile cu $m=3$ elemente, în număr de $C_5^3=10$.

4. Utilizând metoda backtracking se generează toate permutările mulțimii $\{1,2,3,4\}$, în ordinea $1234$, $1243$, $1324$, ... Indicați permutarea generată imediat după $2431$.

a) $2341$
b) $3142$
c) $2413$
d) $3124$

Răspuns corect: d) $3124$

$2431$ este ultima permutare care începe cu $2$ (restul, $431$, este descrescător), deci urmează prima permutare care începe cu $3$: $3124$.

5. Se consideră subprogramul de mai jos, apelat `bt(0, 0)`. Ce valoare are `cnt` după apel?

a) $12$
b) $8$
c) $6$
d) $10$

Răspuns corect: d) $10$

Se numără tripletele $(a,b,c)$ cu $a,b,c\in\{1,2,3,4\}$ și $a+b+c=6$: permutările lui $(1,1,4)$ — $3$, ale lui $(1,2,3)$ — $6$, și $(2,2,2)$ — $1$; în total $10$.