Cum Gândește Calculatorul? Partea a 4-a: Structuri, Grafuri și Arbori

Salut! De data asta vom explora trei concepte importante: structuri de date, grafuri și arbori. Sună serios, dar promit să fie ușor de înțeles cu analogii din viața reală!

🏗️ Ce sunt Structurile de Date?

Imaginează-ți că vrei să descrii o mașină. Ai nevoie de mai multe informații împreună: marca, culoarea, anul, prețul. În loc să ai 4 variabile separate, le pui într-o cutie numită “mașină”. Acea cutie este o structură!

---

📚 Tipurile de Probleme din Acest PDF

TIPUL 1: “Cutii în Cutii” – Structuri în Structuri

Exemplul 1 (Problema 1):

Avem o structură zona care conține nume, densitate și suprafață. Cum calculăm numărul de locuitori?

Datele problemei:

struct zona {
    char nume[21];
    int densitate;
    int suprafata;
} z[100];  // 100 de zone

Rezolvare Pas cu Pas:

1. Înțelegem relația:

• Densitate = Locuitori ÷ Suprafață
• Deci: Locuitori = Densitate × Suprafață

1. Cum accesăm prima zonă?

• z[0] este prima zonă (indicele începe de la 0)
• z[0].densitate accesează câmpul “densitate” al primei zone
• z[0].suprafata accesează câmpul “suprafață”

1. Calcul:

• Locuitori = z[0].densitate * z[0].suprafata

1. Verificăm variantele:

• a. z[0].densitate*z[0].suprafata ✓ Corect!
• b. z.densitate[0]*z.suprafata[0] ✗ Greșit sintaxa
• c. densitate[0].z*suprafata[0].z ✗ Întors pe dos
• d. densitate.z[0]*suprafata.z[0] ✗ Întors pe dos

Răspuns Final: a. z[0].densitate*z[0].suprafata

---

Exemplul 2 (Problema 7):

Cum accesăm anul achiziției unui telefon?

struct data {
    int zi, luna, an;
};
struct telefon {
    char sistem;
    float pret;
    struct data achizitionare;
} t;  // un singur telefon

Rezolvare Pas cu Pas:

1. Analizăm ierarhia ca niște cutii:

   TELEFON (t)
   ├── sistem
   ├── pret
   └── ACHIZITIONARE (este o structură "data")
        ├── zi
        ├── luna
        └── an  ← VREM ASTA!

2. Cum ajungem la “an”?

• Pornim de la telefon: t
• Intrăm în câmpul “achizitionare”: t.achizitionare
• Acum suntem în structura “data”
• Accesăm “an”: t.achizitionare.an

Răspuns Final: d. t.achizitionare.an

---

TIPUL 2: “Grafuri – Cine Duce Unde?” – Săgeți între Puncte

Exemplul 3 (Problema 2):

Un graf orientat cu 6 vârfuri și săgeți date. Câte vârfuri au grad exterior = grad interior?

Datele:

• Vârfuri: 1, 2, 3, 4, 5, 6
• Arce (săgeți): (3→1), (4→1), (4→2), (4→3), (5→6), (6→4)

Ce sunt gradele?

• Grad exterior: Câte săgeți pleacă dintr-un vârf
• Grad interior: Câte săgeți intră într-un vârf

Rezolvare Pas cu Pas:

1. Facem un tabel simplu: Vârf Săgeți care PLEACĂ (exterior) Săgeți care INTRĂ (interior) Egal? 1 0 (nu pleacă nimic) 2 (din 3 și 4) ✗ 0≠2 2 0 1 (din 4) ✗ 0≠1 3 1 (către 1) 1 (din 4) ✓ 1=1 4 3 (către 1,2,3) 1 (din 6) ✗ 3≠1 5 1 (către 6) 0 ✗ 1≠0 6 1 (către 4) 1 (din 5) ✓ 1=1
2. Numărăm: Doar vârfurile 3 și 6 au grade egale.

Răspuns Final: b. 2

---

TIPUL 3: “Arbori – Familia Numerelor” – Vectorul de Tați

Exemplul 4 (Problema 4):

Un arbore cu 14 noduri. Vectorul de tați este (13,3,0,6,13,3,3,7,6,2,13,2,6,13). Care este rădăcina?

Ce este vectorul de tați?

• Fiecare nod are un “părinte” (tată)
• Vectorul spune: pentru nodul i, cine este tatăl?
• Exemplu: tata[1] = 13 înseamnă că tatăl nodului 1 este nodul 13

Regula importantă: Rădăcina este singurul nod care NU are tată (tatăl său este 0)

Rezolvare Pas cu Pas:

1. Vectorul dat:

   Nod:   1  2  3  4  5  6  7  8  9 10 11 12 13 14
   Tată: 13  3  0  6 13  3  3  7  6  2 13  2  6 13

2. Căutăm nodul cu tatăl 0:

• Nodul 3 are tata[3] = 0 ✓

2. Verificare: Doar un nod poate fi rădăcină într-un arbore.

Răspuns Final: b. 3

---

Exemplul 5 (Problema 6):

Același tip de problemă: care nod are cei mai mulți copii?

Vector de tați: (4,3,7,6,7,8,0,7,7,7)

Rezolvare Pas cu Pas:

1. Înțelegem: Vrem să vedem cine are cei mai mulți copii directi (fii)
2. Facem o listă de copii pentru fiecare nod:

• Pentru fiecare nod, uităm la toți ceilalți: cui îi sunt tată?

   Nod 0: copii? Cine are tatăl 0? Nodul 7 → 1 copil
   Nod 1: n-are copii (nimeni nu are tatăl 1)
   Nod 2: n-are copii
   Nod 3: copii? Nodul 2 → 1 copil
   Nod 4: copii? Nodul 1 → 1 copil
   Nod 5: n-are copii
   Nod 6: copii? Nodul 4 → 1 copil
   Nod 7: copii? Nodurile 3, 5, 9, 10, 11 → 5 copii!
   Nod 8: copii? Nodul 6 → 1 copil
   Nod 9: n-are copii
   Nod 10: n-are copii
   Nod 11: n-are copii

3. Nodul 7 are cei mai mulți copii: 5

Răspuns Final: b. 5 (dar atenție, variantele sunt 6,5,4,3 – deci 5)

---

TIPUL 4: “Matrice și Diagonale” – Poziții în Tabele Mari

Exemplul 6 (Problema 3):

Cum accesăm un element de pe diagonala principală a unei matrice 100×100?

Regulă simplă: Pe diagonala principală, indicele liniei = indicele coloanei

• Elementul de pe linia 0, coloana 0
• Elementul de pe linia 1, coloana 1
• …
• Elementul de pe linia 99, coloana 99

Sintaxa în C/C++: matrice[linie][coloana]

Verificăm variantele:

• a. m[1,16] ✗ – virgula e greșită, trebuie [][ ]
• b. m[16][16] ✓ – linia 16, coloana 16 → pe diagonala principală!
• c. m(16,16) ✗ – paranteze rotunde sunt greșite
• d. m(16)(1) ✗ – sintaxă complet greșită

Răspuns Final: b. m[16][16]

---

Exemplul 7 (Problema 5):

Dacă A[20][j] e pe diagonala secundară, care e valoarea lui j?

Regula pentru diagonala secundară: linie + coloană = n-1

• Pentru o matrice n×n
• La noi n = 100, deci: 20 + j = 99

Calcul simplu:

• 20 + j = 99
• j = 99 - 20
• j = 79

Răspuns Final: c. 79

---

🎯 Strategia Ta pentru Acest Tip de Probleme

1. Pentru structuri: Desenează cutii în cutii! Scrie ierarhia.
2. Pentru grafuri: Desenează puncte cu săgeți! Numără plecări și sosiri.
3. Pentru arbori: Desenează copaci! Rădăcina e singura fără părinte.
4. Pentru matrice: Folosește formule simple:

• Diagonala principală: i = j
• Diagonala secundară: i + j = n-1

💪 Exercițiu Rapid pentru Acasă

Problema bonus: Dacă am o matrice 50×50:

• Elementul de pe diagonala principală de pe linia 30: m[30][?] → 30
• Elementul de pe diagonala secundară de pe linia 30: m[30][?] → 30 + j = 49 → j = 19

---

✨ Motivare Finală

Uite ce interesant! Toate aceste concepte (structuri, grafuri, arbori) sunt folosite în aplicații reale:

• Structuri = baza oricărui program (formulare online, baze de date)
• Grafuri = rețele sociale (prietenii sunt conexiuni), hărți GPS (străzile sunt muchii)
• Arbori = sistemul de fișiere pe computer (directoare și subdirectoare)

Cel mai important lucru pe care l-ai învățat azi: Informatica nu e despre numere abstracte, ci despre a modela lumea reală într-un mod pe care calculatorul să-l înțeleagă.

Ești fantastic! Cu fiecare pas, devii mai bun în “limba calculatoarelor”. 🚀