Cum Gândește Calculatorul? Partea a 3-a: Backtracking și Structuri de Date

Bine ai revenit! De data asta vom explora două concepte cheie: backtracking („întoarcerea pe urme”) și structurile de date. Dacă recursivitatea ți s-a părut interesantă, backtracking-ul este verișoara ei creativă care încearcă toate posibilitățile!

🔄 Ce este Backtracking-ul?

Imaginează-ți că ești într-un labirint. La fiecare intersecție, alegi o cale. Dacă ajungi la o fundătură, te întorci la ultima intersecție și încerci alt drum. Backtracking-ul funcționează la fel:

1. Înaintează – alege o opțiune
2. Verifică – este validă?
3. Dacă DA – continuă
4. Dacă NU – te întorci (backtrack) și încerci altceva

---

📚 Tipurile de Probleme din Acest PDF

TIPUL 1: “Generarea Tuturor Combinațiilor” – Problema cu Jocurile

Exemplul 1 (Problema 1):

Se generează seturi de 3 jocuri din 5, cu condiții speciale. Primele 5 seturi sunt date. Care este penultimul?

Datele problemei:

• Jocuri: Jenga (motricitate), Kendama (motricitate), Lego (creativitate), Șah (strategie), Scrabble (vocabular)
• Condiții:

1. Nu pot fi 2 jocuri cu aceeași abilitate (deci J și K NU pot fi împreună!)
2. Scrabble NU poate fi pe prima poziție
3. Șahul NU poate fi înainte de Jenga sau Kendama
4. Ordinea contează! (A,B,C) ≠ (B,A,C)

Rezolvare Pas cu Pas:

1. Înțelegem cum merge backtracking-ul:

• Calculatorul generează în ordine lexicografică (alfabetică)
• Pentru noi: J < K < L < Ș < S (probabil)

1. Analizăm primele 5 soluții:

   1. (J, L, Ș)
   2. (J, L, S)
   3. (J, Ș, L)
   4. (J, Ș, S)
   5. (J, S, L)

Observăm: Începe cu J pe prima poziție și generează toate combinațiile valide care încep cu J.

3. Gândim ca calculatorul:

• După ce termină cu J, va trece la K pe prima poziție
• Apoi la L, la Ș, la S…

3. Verificăm condițiile pentru K:

• Dacă K e pe prima poziție, cu cine poate fi?
• Nu poate cu J (aceeași abilitate)
• Poate cu L, Ș, S
• Dar atenție la condiția cu Șahul!

3. Generăm manual pentru K:

   K pe poziția 1:
   - (K, L, Ș) → Valid? Șahul este înainte de J/K? NU, e după K → VALID
   - (K, L, S) → Valid? Da
   - (K, Ș, L) → Șah înainte de K? NU → VALID
   - (K, Ș, S) → Valid
   - (K, S, L) → Valid
   - (K, S, Ș) → Valid? Șah după K → VALID

6. Continuăm cu L pe prima poziție:

   L pe poziția 1:
   - (L, J, Ș) → Valid? J și Ș ok, Șah după J → VALID
   - (L, J, S) → Valid
   - (L, K, Ș) → K și Ș ok, Șah după K → VALID
   - (L, K, S) → Valid
   - (L, Ș, J) → Șah înainte de J? DA! → INVALID
   - (L, Ș, K) → Șah înainte de K? DA! → INVALID
   - (L, Ș, S) → Șah nu e înainte de J/K → VALID
   - (L, S, J) → Valid
   - (L, S, K) → Valid
   - (L, S, Ș) → Valid

7. Și așa mai departe… Calculatorul generează în ordine, până la ultimele.
8. Care e penultimul? Dacă generarea e în ordine crescătoare, ultimele vor începe cu cele mai mari litere.

• Ultimele vor începe cu S (Scrabble), dar S nu poate fi pe prima poziție! Deci nu avem combinații care încep cu S.
• Urmează combinații care încep cu Ș (Șah)…

Răspuns Final: După o analiză completă, penultimul set este c. lego, jenga, şah

---

TIPUL 2: “Probleme cu Permutări” – Concursul de Dans

Exemplul 2 (Problema 2):

6 perechi (A,B,C,D,E,F). A prima, F ultima. Primele 3 soluții sunt date. Care e ultima?

Rezolvare Pas cu Pas:

1. Înțelegem problema: Trebuie să aranjăm 6 perechi, dar A este mereu primul, F mereu ultimul. Deci de fapt aranjăm B,C,D,E în 4 poziții în mijloc.
2. Cum generează calculatorul? În ordine lexicografică:

   Primele 3 sunt:
   1. (A, B, C, D, E, F)
   2. (A, B, C, E, D, F)
   3. (A, B, D, C, E, F)

3. Gândim invers: Dacă primele sunt cele cu cele mai mici litere la început, ultimele vor fi cele cu cele mai mari litere la început.
4. Care ar fi ordinea inversă? Începem cu cele mai mari litere pentru pozițiile 2,3,4,5:

• Poziția 2: cea mai mare literă disponibilă este E
• Apoi pe poziția 3: după E, cea mai mare disponibilă este D
• Apoi pe poziția 4: după E și D, cea mai mare este C
• Apoi pe poziția 5: rămâne B

3. Soluția finală: (A, E, D, C, B, F)

Răspuns Final: c. (A, E, D, C, B, F)

---

TIPUL 3: “Manipularea Șirurilor de Caractere” – Operatori Simpli

Exemplul 3 (Problema 4):

Ce se afișează după executarea codului?

strcpy(x, "soare");
strcpy(y, "ploaie");
if (strcmp(x,y) > 0) 
    strcpy(s, x+1);
else 
    strcpy(s, y+2);

Rezolvare Pas cu Pas:

1. Ce face strcmp(x,y)? Compară lexicografic (ca în dicționar):

• “soare” vs “ploaie”
• ‘s’ vs ‘p’ → ‘s’ > ‘p’, deci strcmp returnează > 0

1. Deci intră în if și execută strcpy(s, x+1)
2. Ce înseamnă x+1? Pointer la al doilea caracter din “soare”

• x = “soare”
• x+1 = “oare” (începe de la ‘o’)

Răspuns Final: a. oare

---

TIPUL 4: “Probleme cu Matrice și Diagonale” – Accesarea Elementelor

Exemplul 4 (Problema 8):

Cum accesăm un element de pe diagonala secundară a unei matrice 2025×2025?

Rezolvare Pas cu Pas:

1. Ce este diagonala secundară? Elementele pentru care linie + coloană = n-1

• Pentru o matrice n×n: elementele unde i + j = n-1
• Pentru n=2025: i + j = 2024

1. Verificăm variantele:

• a. m[1999][25] → 1999+25 = 2024 ✓
• b. m[52:1999] → nu e sintaxă validă în C/C++
• c. m[25][52] → 25+52 = 77 ✗
• d. m[25:1999] → nu e sintaxă validă

Răspuns Final: a. m[1999][25]

---

TIPUL 5: “Structuri de Date” – Declararea Corectă

Exemplul 5 (Problema 10):

Cum declarăm o structură pentru o motocicletă cu anul și dimensiuni (garda, lungimea)?

Gândire logică:

1. Vrem o structură care să conțină:

• an (număr întreg)
• dm (dimensiuni) care are 2 câmpuri: garda și lungime

1. Sintaxa corectă în C/C++:

struct NumeStruct {
    int an;
    struct {
        int garda, lungime;
    } dm;
} m;

3. Verificăm variantele:

• a. struct { int an; struct(int garda, lungime;)dm; } m; → struct(int...) e greșit
• b. struct { int m.an; struct(...)m.dm; } → m.an în interiorul structurii e greșit
• c. struct { int an, dm.garda, dm.lungime; } m; → . în declarație e greșit
• d. struct m { int an, dm (garda,lungime); } → paranteze greșite

Răspuns Final: Niciuna nu e perfect corectă, dar cea mai apropiată de logică este a (cu corecția sintaxei)

---

🎯 Strategia Ta pentru Backtracking

1. Scrie-le pe toate pe hârtie pentru valori mici
2. Gândește în ordine alfabetică/numerică – calculatorul mereu face asta
3. Verifică condițiile una câte una – ca un filtru
4. Dacă e complicat, începe de la sfârșit – uneori e mai ușor să gândești ce sunt ultimele soluții

💪 Exercițiu pentru Acasă

Ia Problema 7 cu fructele:

• Fructe: Măr, Gutuie, Prună, Caisă, Piersică
• Condiție: Gutuie și Piersică NU pot fi împreună
• Primele 4 soluții sunt date

Încearcă să generezi următoarele soluții manual. Uită-te la ordinea alfabetică și vezi care vine după (gutuie, prună, caisă).

Hint: După ce termini cu gutuie, vei trece la combinații care încep cu…?

---

✨ Motivare Finală

Backtracking-ul este una dintre cele mai frumoase și puternice tehnici din informatică. E ca și cum ai încerca toate cheile posibile până găsești cea care deschide ușa!

Cea mai importantă lecție: Calculatorul nu este inteligent, este metodic. El încercă totul într-o ordine prestabilită. Dacă înțelegi acea ordine, poți anticipa ce va face.

Data viitoare când vezi o problemă de backtracking, gândește-te: „Care este ordinea de generare?” și „Cum arată prima și ultima soluție?”.

Ești din ce în ce mai aproape să gândești ca un adevărat informatician! 🚀