Cum Gândește Calculatorul? Partea a 6-a: Analiza Algoritmilor în Pseudocod

Salut! Astăzi vom învăța cel mai important skill pentru Bacalaureatul la Informatică: cum să analizezi un algoritm scris în pseudocod. Nu te speria de toate acele simboluri! O să le descompunem pas cu pas.

🎯 Ce este Pseudocodul?

Pseudocodul este o limbă simplă, semi-formală, folosită pentru a descrie algoritmi fără să folosești o limbă de programare reală. E ca o rețetă de gătit scrisă în română!

Reguli importante în pseudocod:

• ← înseamnă “primește valoarea” (ex: x ← 5 = “x primește valoarea 5”)
• [c] = partea întreagă a lui c (ex: [5.7] = 5)
• a%b = restul împărțirii lui a la b
• citește = citește de la tastatură
• scrie = afișează pe ecran

---

📚 Tipurile de Probleme din Acest PDF

TIPUL 1: “Algoritmul Euclid” – CMMDC-ul prin Scăderi Repetate

Exemplul 1 (Primul algoritm):

citeşte m,n (numere naturale, 1<m<n)

repetă
    x←m; y←n; n←n-1
    repetă
        dacă x>y atunci x←x-y 
        altfel y←y-x
    până când y=0
până când x≠1
scrie n+1

Rezolvare Pas cu Pas pentru punctul a:

a. Pentru m=27, n=38

1. Înțelegem algoritmul:

• Prima buclă repetă...până când x≠1 se execută cât timp x=1
• În interior, se copiază m în x și n în y, apoi n scade cu 1
• Apoi se calculează CMMDC prin scăderi repetate până y=0
• Dacă la final x=1, algoritmul se oprește

1. Rulăm pentru 27 și 38:

   Pas 1: m=27, n=38
   x=27, y=38, n=37
   Calculez CMMDC(27,38) prin scăderi:
   27<38 → y=38-27=11
   27>11 → x=27-11=16
   16>11 → x=16-11=5
   5<11 → y=11-5=6
   5<6 → y=6-5=1
   5>1 → x=5-1=4
   4>1 → x=4-1=3
   3>1 → x=3-1=2
   2>1 → x=2-1=1
   1=1 → y=1-1=0 → STOP
   x=1 → continuă bucla principală

   Pas 2: m=27, n=37 (n a scăzut)
   x=27, y=37, n=36
   CMMDC(27,37)=1 (27 și 37 sunt prime între ele)
   x=1 → continuă

   Pas 3: m=27, n=36
   x=27, y=36, n=35
   CMMDC(27,36)=9 (27=3³, 36=3²×4)
   Calcul: 27<36→y=9, 27>9→x=18, 18>9→x=9, 9=9→y=0
   x=9 ≠1 → oprește!

3. La sfârșit: scrie n+1 unde n=35 (ultima valoare a lui n)

• Afișează: 35+1 = 36

Răspuns pentru a: 36

---

b. Pentru m=5, găsiți n astfel încât să se afișeze 10

1. Știm că se afișează n+1 = 10, deci n = 9 la sfârșit
2. Dar atenție: n se schimbă în algoritm!

• La început citim n
• În buclă: n ← n-1 (scade cu 1 la fiecare pas)
• La sfârșit se afișează n+1 (unde n e ultima valoare)

1. Gândim invers: Dacă la sfârșit n=9, și el scade cu 1 la fiecare iterație…

• Fie k numărul de iterații
• n_final = n_initial – k
• 9 = n_initial – k

1. Știm că algoritmul se oprește când găsește CMMDC ≠ 1

• Pentru m=5, căutăm n astfel încât:
  • În prima iterație: CMMDC(5,n) ≠ 1
  • Sau în a doua, etc.

1. Testăm variante:

• Dacă n=10 la început: CMMDC(5,10)=5 ≠1 → se oprește imediat
  • n scade la 9, se afișează 10 ✓
• Dacă n=15 la început: CMMDC(5,15)=5 → se oprește imediat
  • n scade la 14, se afișează 15 ✗ (nu e 10)

1. Trebuie să meargă mai multe iterații până n_final=9:

• n_initial = 14: 14→13→12→11→10→9 (5 iterații)
• Verificăm: CMMDC(5,14)=1, CMMDC(5,13)=1, CMMDC(5,12)=1, CMMDC(5,11)=1, CMMDC(5,10)=5
• Se oprește la a 5-a iterație, n_final=9 ✓

Răspuns pentru b: 14 și 19 (ambele merg)

---

TIPUL 2: “Manipularea Cifrelor” – Descompunerea și Recompunerea Numerelor

Exemplul 2 (Al doilea algoritm):

citeşte x,y (numere naturale distincte)
cx←0; cy←0
cât timp x≥10 sau y≥10 execută
    cât timp x+y≠0 execută
        cx←cx+x%10; x←[x/10]
        cy←cy+y%10; y←[y/10]
    x←cx; cx←0; y←cy; cy←0
dacă x=y atunci scrie "DA ", x
altfel scrie "NU ", x, " ", y

Rezolvare pentru punctul a cu x=9767, y=8204:

1. Înțelegem algoritmul:

• Calculează suma cifrelor lui x și y
• Pune suma în cx și cy
• Apoi face x=cx, y=cy
• Repetă până când ambele sunt <10

1. Rulăm pas cu pas:

   Iteratia 1:
   x=9767, y=8204 (ambele ≥10)
   Bucla interioara:
   cx=0+7=7, x=976
   cy=0+4=4, y=820
   cx=7+6=13, x=97
   cy=4+0=4, y=82
   cx=13+7=20, x=9
   cy=4+2=6, y=8
   cx=20+9=29, x=0
   cy=6+8=14, y=0
   x=29, y=14 (ambele ≥10, continuă)

   Iteratia 2:
   x=29, y=14
   cx=0+9=9, x=2
   cy=0+4=4, y=1
   cx=9+2=11, x=0
   cy=4+1=5, y=0
   x=11, y=5 (x≥10, continuă)

   Iteratia 3:
   x=11, y=5
   cx=0+1=1, x=1
   cy=0+5=5, y=0
   cx=1+1=2, x=0
   y rămâne 5
   x=2, y=5 (ambele <10? x=2<10, y=5<10 → STOP)

3. Verificare finală: x=2, y=5, diferite → afișează “NU 2 5”

Răspuns pentru a: NU 2 5

---

TIPUL 3: “Căutarea Numerelor cu Proprietăți” – Verificarea Ultimei Cifre

Exemplul 3 (Al treilea algoritm):

citeşte m,n (numere naturale nenule, m≤n)
pentru i←n,m,-1 execută
    x←i
    c←x%10
    repetă
        x←[x/10]
    până când x%10≠c
    dacă x=0 atunci
        scrie i, ' '

Rezolvare pentru punctul a cu m=75, n=90:

1. Înțelegem algoritmul: Caută numere între n și m (descrescător) care au toate cifrele egale
2. Cum funcționează:

• Pentru fiecare număr i
• Salvează ultima cifră în c
• Îndepărtează cifre până când ultima cifră ≠ c sau x=0
• Dacă x=0, înseamnă că toate cifrele erau egale

1. Testăm pentru 75-90 (descrescător):

• i=90: cifre 9,0 → diferite → nu afișează
• i=89: cifre 8,9 → diferite → nu
• …
• i=88: cifre 8,8 → egale → AFIȘEAZĂ 88
• i=87: cifre 8,7 → diferite → nu
• …
• i=77: cifre 7,7 → egale → AFIȘEAZĂ 77

1. Atenție la ordine: De la n la m descrescător: 90,89,88,87,…,77,76,75

Răspuns pentru a: 88 77

---

TIPUL 4: “Structuri Repetitive Echivalente” – Transformarea Pseudocodului

Exemplul pentru punctul d din primul algoritm:

Cerința: Înlocuiește repetă...până când cu cât timp...execută

Regulă de transformare:

• repetă ... până când condiție
• Echivalent cu: execută ... cât timp NOT(condiție)

Transformare pentru bucla interioară:

repetă
    dacă x>y atunci x←x-y 
    altfel y←y-x
până când y=0

Devine:

execută
    dacă x>y atunci x←x-y 
    altfel y←y-x
cât timp y≠0

---

🎯 Strategii pentru Analiza Algoritmilor

1. “Rulează-l în cap” cu valori mici

• Ia o foaie și simulează execuția pas cu pas
• Folosește valori simple (1,2,3…) mai întâi

1. Identifică ce calculează algoritmul

• CMMDC? Suma cifrelor? Numere cu proprietăți?
• Gândește la scopul algoritmului

1. Pentru punctul b (găsirea valorilor)

• Gândește invers de la rezultat la date
• Folosește ecuații simple

1. Pentru punctul c (scrierea în C/C++)

• Tradu direct fiecare linie
• Atenție la tipuri de date

1. Pentru punctul d (transformarea structurilor)

• Învață echivalențele:
  • repetă...până când cond = execută...cât timp NOT(cond)
  • cât timp cond execută = dacă cond atunci repetă...până când NOT(cond)

💪 Exercițiu Rapid pentru Acasă

Ultimul algoritm din PDF:

citeşte n (număr natural nenul)
x←-1; y←-1
cât timp n>9 execută
    dacă x=-1 atunci x←n%100
    altfel y←n%100
    n←[n/10]
dacă x<y atunci n←(n*100+x)*100+y
altfel n←(n*100+y)*100+x
scrie n

Pentru n=412531:

1. Extrage ultimele 2 cifre la fiecare pas
2. x primește prima pereche, y a doua
3. Apoi reconstruiește numărul

Încearcă să-l rulezi pe hârtie! O să vezi că ia ultimele 2 cifre, le sortează, și le atașează la numărul rămas.

---

✨ Motivare Finală

Analiza algoritmilor este ca rezolvarea unui puzzle sau descifrarea unui cod secret. Fiecare algoritm spune o poveste, iar tu trebuie să-i descoperi logica.

Cel mai important lucru pe care îl poți face: NU ÎNCEPE SĂ SCRII COD ÎNAINTE SĂ ÎNȚELEGI ALGORITMUL! Petrece 5 minute să-l analizezi, să-l rulezi mental cu valori mici. Apoi totul va fi mult mai ușor.

Uite ce bine te descurci! Cu fiecare algoritm analizat, devii mai bun în a “citii gândurile” celui care l-a scris. 🚀