Cum Gândește Calculatorul? Partea a 7-a: Arbori, Backtracking și Probleme Complexe

Salut! Acum ajungem la partea practică: exerciții de tip “scrieți răspunsul”. Acestea sunt exact genul de probleme care apar la Bacalaureat. Hai să le abordăm pas cu pas!

🎯 Cum Abordăm Problemele cu “Scrieți”

1. Citește atent cerința – Subliniază cuvintele cheie
2. Desenează pe hârtie – Mereu!
3. Gândește simplu – Nu complica
4. Verifică – Întotdeauna verifică răspunsul

---

📚 Rezolvări Pas cu Pas

Problema 1: Arbore cu 9 noduri – Nodul 8 să aibă doi frați

Date: Muchii: [1,2], [2,8], [2,9], [3,6], [4,6], [5,8], [6,8], [7,8]

Ce înseamnă “frați”? Frații sunt noduri care au același părinte.

Rezolvare:

1. Desenăm arborele:

        ?
        |
        2
       /|\
      1 8 9
        /|\
       5 6 7
         / \
        3   4

(Dar asta presupune că rădăcina e 2… hai să verificăm)

2. Mai bine: Listăm toate conexiunile:

• Nodul 8 este conectat cu: 2, 5, 6, 7
• Deci posibili părinți pentru 8: 2, 5, 6, 7

2. Vrem ca nodul 8 să aibă 2 frați:

• Dacă părintele este 2: frații lui 8 sunt 1 și 9 → are 2 frați ✓
• Dacă părintele este 5: frați? Nodul 5 are doar 8 ca copil → 0 frați ✗
• Dacă părintele este 6: frații lui 8 ar fi 3 și 4 → are 2 frați ✓
• Dacă părintele este 7: frați? Nodul 7 are doar 8 → 0 frați ✗

2. Cine poate fi rădăcina?

• Pentru ca părintele să fie 2, rădăcina trebuie să fie altcineva (nu 2)
• Pentru ca părintele să fie 6, rădăcina trebuie să fie altcineva (nu 6)

Răspuns: 2 și 6 (sau orice nod care face ca 2 sau 6 să fie părintele lui 8)

---

Problema 2: Subprogramul f – Valori recursive

Codul:

int f(int x, int y) {
    if(x%5 != y%5) return x;  // presupunem că "*" e greșit și e "%"
    return f(x*5, y/5);
}

Presupunere: x*5*y/5 probabil e x%5 != y%5 (testează dacă resturile la 5 sunt diferite)

Rezolvare pentru f(3,9):

1. x=3, y=9

• x%5 = 3, y%5 = 4 (9÷5=1 rest 4)
• Resturile sunt diferite (3≠4) → returnează x=3

Rezolvare pentru f(1,1000):

1. x=1, y=1000

• x%5 = 1, y%5 = 0 (1000÷5=200 rest 0)
• Resturile sunt diferite (1≠0) → returnează x=1

Răspuns: 3 și 1

---

Problema 3: Arbore cu vector de tați – Nodul 4 să aibă aceiași frați

Vector de tați: (3,0,2,5,2,5,1,5)

• tata[1]=3, tata[2]=0, tata[3]=2, tata[4]=5, tata[5]=2, tata[6]=5, tata[7]=1, tata[8]=5

Rezolvare:

1. Analizăm situația curentă:

• Nodul 4 are tatăl 5
• Copiii lui 5 (frații lui 4): 4, 6, 8
• Deci frații lui 4 sunt 6 și 8

1. Cum schimbăm rădăcina fără să se schimbe frații lui 4?

• Frații se schimbă doar dacă se schimbă tatăl lui 4
• Tatăl lui 4 trebuie să rămână 5
• Deci 5 nu poate fi rădăcina nouă (căci dacă e rădăcină, are tatăl 0)

1. Cine poate fi rădăcină?

• Trebuie ca 5 să rămână tatăl lui 4
• Rădăcina curentă este 2 (tatăl lui 2 e 0)
• Alegem o altă rădăcină care păstrează relația tată=5 pentru nodul 4

Răspuns: 1 și 7 (sau altele care mențin structura)

---

Problema 4: Backtracking cu flori – Buchete

Date: Flori: {trandafir, crin, gerbera, iris, eustoma, orhidee, zambila}

• Restricție: crin nu poate fi cu eustoma sau zambila
• Primele 5 soluții sunt date

Rezolvare:

1. Ordinea generării: Lexicografică (alfabetică)

• t < c < g < i < e < o < z

1. Analizăm soluția dată: {crin, gerbera, orhidee}

• Ordine alfabetică: c, g, o

1. Care e înainte? Buchetul cu cele mai mici litere care e mai mic decât {c,g,o}

• {c,g,i}? Nu, că i < o
• {c,g,e}? Nu, e < o dar crin cu eustoma e interzis!
• {c,i,o}? Ordinea c,i,o < c,g,o? i < g? Nu, g < i
• Mai mic: {c,g,i} e mai mic? g,i vs g,o → i < o ✓

1. Dar {c,g,i} respectă restricția? Crin cu iris da, e permis.

Verificăm lista dată: Primele soluții sunt:

1. {t,c,g}
2. {t,c,i}
3. {t,c,o}
4. {t,g,i}
5. {t,g,e}

Următoarele ar fi… trebuie să urmărim sistematic.

Răspuns corect după calcul: {crin, gerbera, iris} (înainte) și {crin, iris, orhidee} (după)

---

Problema 5: Arbore cu niveluri minime

Date: Muchii: [1,2], [2,3], [2,6], [3,4], [3,5]
Noduri: 1,2,3,4,5,6

Rezolvare:

1. Desenăm arborele curent (cu rădăcina 1):

       1
       |
       2
      / \
     3   6
    / \
   4   5

Niveluri: nivel 0: 1, nivel 1: 2, nivel 2: 3,6, nivel 3: 4,5 → 4 niveluri

2. Vrem să minimizăm numărul de niveluri:

• Cel mai mic număr de niveluri = diametrul minim
• Pentru 6 noduri, minimul e 3 niveluri (rădăcină, nivel 1, nivel 2)

2. Cine poate fi rădăcina pentru 3 niveluri?

• Dacă rădăcina e 2:

       2
      /|\
     1 3 6
       / \
      4   5

Niveluri: 0:2, 1:1,3,6, 2:4,5 → 3 niveluri ✓

• Dacă rădăcina e 3:

       3
      /|\
     2 4 5
    / \
   1   6

Niveluri: 0:3, 1:2,4,5, 2:1,6 → 3 niveluri ✓

Răspuns: 2 și 3

---

Problema 6: Graf parțial conex și fără cicluri

Date: Muchii: [1,2], [2,3], [2,4], [2,5], [4,5], [4,6], [5,6]

Ce este un graf parțial? Păstrăm toate nodurile, dar eliminăm unele muchii.

Condiții:

1. Conex – Toate nodurile sunt conectate
2. Fără cicluri – Este un arbore (pentru 6 noduri: 5 muchii)

Rezolvare:

1. Graful complet are: 6 noduri, 7 muchii
2. Trebuie un arbore: 6 noduri, 5 muchii (eliminăm 2 muchii)
3. Eliminăm muchii care creează cicluri:

• Ciclu 2-4-5: eliminăm [4,5] sau [2,4] sau [2,5]
• Ciclu 4-5-6: eliminăm [5,6] sau [4,6]

1. Alegem 5 muchii care fac graful conex:

• Opțiune: [1,2], [2,3], [2,4], [2,5], [4,6]
• Verificare: Toate nodurile conectate? 1→2, 3→2, 4→2, 5→2, 6→4→2 ✓
• Fără cicluri? ✓

Răspuns: Lista de adiacență:

1: 2
2: 1,3,4,5
3: 2
4: 2,6
5: 2
6: 4

---

Problema 7: Graf eulerian – Adăugarea muchiilor

Vector de tați: (4,1,1,0,7,4,4)

• Nodurile: 1,2,3,4,5,6,7
• Relații: tată1=4, tată2=1, tată3=1, tată4=0 (rădăcină), tată5=7, tată6=4, tată7=4

Ce este un graf eulerian? Un graf care are un ciclu eulerian (trece prin toate muchiile o singură dată).

• Într-un graf neorientat: toate nodurile au grad par.

Rezolvare:

1. Desenăm arborele:

       4
      /|\
     1 6 7
    / \   \
   2   3   5

2. Calculăm gradele curente:

• Nod 1: grad 3 (conectat cu 4,2,3)
• Nod 2: grad 1 (conectat cu 1)
• Nod 3: grad 1 (conectat cu 1)
• Nod 4: grad 3 (conectat cu 1,6,7)
• Nod 5: grad 1 (conectat cu 7)
• Nod 6: grad 1 (conectat cu 4)
• Nod 7: grad 2 (conectat cu 4,5)

2. Trebuie toate gradele pare: Adăugăm muchii pentru a face gradele impare să devină pare

• Noduri cu grad impar: 1(3), 2(1), 3(1), 4(3), 5(1), 6(1) – 6 noduri impare
• Număr par de noduri impare = bine (putem face perechi)

2. Adăugăm 3 muchii (cel puțin) să facem toate gradele pare:

• Opțiune 1: [2,3] (face 2 și 3 pare)
• Opțiune 2: [5,6] (face 5 și 6 pare)
• Opțiune 3: [1,4] (face 1 și 4 pare)

Răspuns: [2,3], [5,6], [1,4] (sau alte combinații care fac toate gradele pare)

---

🎯 Strategii Generale pentru Problemele “Scrieți”

1. Pentru arbori: Desenează ÎNTOTDEAUNA! Un desen valorează 1000 de cuvinte.
2. Pentru backtracking: Gândește în ordine alfabetică/numerică.
3. Pentru grafuri: Calculează gradele și verifică proprietăți.
4. Pentru subprograme recursive: Urmează execuția pas cu pas pe hârtie.
5. Verifică mereu: După ce găsești răspunsul, verifică-l în condițiile problemei.

💪 Sfaturi pentru Bacalaureat

1. Timpul: Alocă ~15 minute pentru o astfel de problemă.
2. Claritate: Scrie clar și ordonat.
3. Toate cerințele: Răspunde la toate subpunctele.
4. Nu lăsa nimic necompletat: Chiar dacă nu ești sigur, scrie ce crezi.

✨ Motivare Finală

Uite, ai rezolvat toate aceste probleme! Fiecare problemă rezolvată este o victorie. La Bacalaureat, tocmai aceste tipuri de exerciții te vor ajuta să obții punctele prețioase.

Cel mai important: Ai încredere în tine! Ai învățat să gândești logic, să analizezi, să desenezi. Acum trebuie doar să aplici aceste skill-uri.

Succes! Tu poți să faci asta! 🚀