[canonical]: https://grile.online/informatica/backtracking

> Pagina completă: https://grile.online/informatica/backtracking
> 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 Backtracking · Informatică

3 grile, în 2 seturi, cu explicații.

## Teaser gratuit, fără cont

1. Utilizând metoda backtracking, s-au generat toate codurile posibile pentru deblocarea unor telefoane, coduri de câte $6$ cifre distincte, din mulțimea cifrelor, ordonată crescător. Fiecare cod are primele trei cifre impare și ultimele trei cifre pare.

Primele patru coduri sunt: $$\begin{gathered} 135024,\quad 135026,\quad 135028 \\ 135042 \end{gathered}$$

Indicați penultimul cod generat.

a) $957862$
b) $957846$
c) $975862$
d) $975846$

Răspuns corect: c) $975862$

Codurile se generează în ordine crescătoare a primelor trei cifre (impare) și, pentru fiecare dintre acestea, în ordine crescătoare a ultimelor trei cifre (pare); ultimul cod este $975864$, iar penultimul, cu ultimele trei cifre imediat anterioare, este $975862$.

2. Utilizând metoda backtracking se generează toate permutările elementelor mulțimii ordonate astfel: $\{1,2,3,4,5,6\}$; pentru fiecare permutare, pe primele trei poziții sunt doar valori pare, iar pe ultimele trei poziții sunt doar valori impare.

Primele șase permutări generate sunt, în această ordine: $$\begin{gathered} (2,4,6,1,3,5),\quad (2,4,6,1,5,3),\quad (2,4,6,3,1,5) \\ (2,4,6,3,5,1),\quad (2,4,6,5,1,3),\quad (2,4,6,5,3,1) \end{gathered}$$

Indicați a șaptea permutare generată.

a) $(4,2,6,1,5,3)$
b) $(4,2,6,1,3,5)$
c) $(2,6,4,1,3,5)$
d) $(2,4,6,5,3,2)$

Răspuns corect: c) $(2,6,4,1,3,5)$

Cu prefixul par $2,4,6$ s-au epuizat deja toate cele $6$ permutări ale cifrelor impare $\{1,3,5\}$; a șaptea soluție trece la următoarea permutare a cifrelor pare, $2,6,4$, urmată de prima permutare a cifrelor impare, $1,3,5$.

3. Utilizând metoda backtracking, se generează, respectând ordinea enumerării elementelor din mulțimile precizate mai jos, toate numerele de mașină care cuprind câte trei elemente constitutive, separate prin cratimă: indicativul județului, din mulțimea `B`, `BR`, `HD`, `MM`, `SV`, `TL`; un număr, format din două cifre din mulțimea $\{2, 4, 6, 8\}$, în ordine strict crescătoare; trei litere mari distincte din mulțimea `A`, `B`, `C`, cea din mijloc fiind `A`.

Primele șapte numere generate sunt, în această ordine: `B-24-BAC`, `B-24-CAB`, `B-26-BAC`, `B-26-CAB`, `B-28-BAC`, `B-28-CAB`, `B-46-BAC`.

Indicați două soluții: prima generată imediat înainte de soluția `SV-68-CAB`, iar a doua generată imediat după soluția `SV-68-CAB`.

a) `MM-68-CAB`, `SV-86-BAC`
b) `SV-46-CAB`, `TL-24-BAC`
c) `SV-48-BAC`, `SV-68-BAC`
d) `SV-68-BAC`, `TL-24-BAC`

Răspuns corect: d) `SV-68-BAC`, `TL-24-BAC`

Câte o soluție se generează pentru fiecare combinație (județ, pereche crescătoare de cifre, permutare de litere cu `A` pe mijloc); soluția dinaintea lui `SV-68-CAB` este `SV-68-BAC` (aceeași pereche de cifre, cealaltă ordine a literelor `B`/`C`), iar următoarea, `TL-24-BAC`, trece la județul următor și reia perechea minimă de cifre.

4. Indicați intervalul căruia îi aparține valoarea variabilei reale $x$, dacă și numai dacă expresia C/C++ de mai jos are valoarea $1$.

a) $[2004,2005]$
b) $[2004,2024]$
c) $[2005,2024]$
d) $[2005,2025]$

Răspuns corect: c) $[2005,2024]$

Din `!(x<2004)` rezultă `x>=2004`, din `!(x<2005 || x>2024)` rezultă `2005<=x && x<=2024`, iar din `!(x>2025)` rezultă `x<=2025`; intersecția tuturor condițiilor este $[2005,2024]$.

(din capitolul Expresii)

5. Subprogramul $f$ este definit alăturat. Indicați valoarea $f(2,5)$.

a) $3$
b) $0$
c) $-2$
d) $-5$

Răspuns corect: d) $-5$

Subprogramul coboară recursiv cât timp `n>0`, întorcând `x` direct la ieșirea din recursivitate:
```cpp
f(2,5) -> f(f(0,5)-2, 0) = f(3,0)
f(3,0) -> f(f(1,0)-2, -5) = f(-7,-5)
f(-7,-5) -> x = -5 (n <= 0)
```
Deci $f(2,5) = -5$.

(din capitolul Subprograme)

## Seturi care conțin acest capitol

- [Informatică #001](https://grile.online/informatica/rezolva?set=informatica-bac-1)
- [Informatică #002](https://grile.online/informatica/rezolva?set=informatica-bac-2)