Algoritmi echivalenți: II.1 d

Pe scurt

1 minesențialul, de recitit oricând

Culorile din lecție:termenidee-cheie

• Trei transformări apar în lucrări: din cât timp în test final, din pentru în cât timp și din repetă în pentru.
• Toată dificultatea stă în două locuri: negarea condiției și cazul în care corpul nu se execută.
• Baremul dă puncte chiar și pentru structura corectă de tipul cerut, chiar dacă algoritmul nu iese echivalent.

Urmează · 1 min

Ideea

2 min

Gândește-te la un vânzător. Regula „cât timp e cineva la coadă, servește următorul client” se uită înainte: dacă nu e nimeni, nu face nimic. Regula „servește următorul client, apoi uită-te dacă mai e cineva” se uită după: merge bine, dar nu și când coada e goală de la început. Soluția e să te uiți o dată înainte de a începe. Acesta este testul dacă din fața lui repetă.

Oficial, programa cere „abstractizarea rezolvării prin construirea unor algoritmi echivalenți”. În lucrare, cerința spune: scrieți în pseudocod un algoritm echivalent cu cel dat, înlocuind o structură cu alta.

Urmează · 2 min

Cele trei reguli

3 min 2 întrebări la final

Din cât timp în test final. Forma dată:

┌cât timp C execută
│ corp
└■

Devine:

┌dacă C atunci
│┌repetă
││ corp
│└până când not C
└■

Din pentru în cât timp. Forma dată:

┌pentru i←a,b execută
│ corp
└■

Devine:

i←a
┌cât timp i≤b execută
│ corp
│ i←i+1
└■

Din repetă în pentru, când numărul de pași e fix. Forma dată:

p←1
┌repetă
│ corp
│ p←p+1
└până când p>n

Devine:

┌pentru p←1,n execută
│ corp
└■

Ultima funcționează aici doar pentru că n e nenul, cum spune enunțul. Pentru n=0, repetă ar executa corpul o dată, iar pentru niciodată.

Urmează · 3 min

Oficial: model 2027, cât timp în test final

4 min o întrebare la final

Cerința: înlocuiește prima structură cât timp...execută cu o structură repetitivă cu test final. Prima e cea exterioară, cu condiția x>0. Cea interioară rămâne cum e.

citește x,y (numere naturale)
n←1
┌dacă x>0 atunci
│┌repetă
││ ok←1
││┌cât timp ok=1 execută
│││┌dacă x%2=0 atunci
││││ y←y*y; x←[x/2]
│││altfel
││││ x←x-1; ok←0
│││└■
││└■
││ n←n*y
│└până când x=0
└■
scrie n

Fără dacă, pentru x=0 s-ar executa corpul o dată, deci n ar deveni y, în loc să rămână 1.

Acceptă orice formă: repetă...până când, repetă...cât timp, execută...cât timp. Dacă alegi o formă cu „cât timp”, condiția nu se neagă: execută ... cât timp x>0.

Urmează · 4 min

Oficial: iunie 2025, varianta 1, test final fără un dacă în plus

2 min

Algoritmul are în interior:

│ x←1
│┌cât timp x*x<i execută
││ x←x+1
│└■

Cerința: înlocuiește cât timp cu o structură repetitivă cu test final. Baremul cere „echivalență a algoritmului pentru cazul inițial x*x≥i” și expresia logică pentru test final. Sunt două drumuri bune.

Cu un dacă, ca până acum:

│ x←1
│┌dacă x*x<i atunci
││┌repetă
│││ x←x+1
││└până când x*x≥i
│└■

Sau pornești cu o unitate mai jos, ca prima creștere să aducă x la 1. Așa, corpul executat o dată nu strică nimic, pentru că i≥1:

│ x←0
│┌repetă
││ x←x+1
│└până când x*x≥i

Urmează · 2 min

Oficial: iunie 2026, varianta 3, repetă în pentru

2 min

Algoritmul este cel de la lecția despre urmărire, cu repetă...până când p>n. Cerința: înlocuiește structura repetitivă cu pentru...execută.

citește n (număr natural nenul)
s←0; x←0
┌pentru p←1,n execută
│ citește y (număr natural nenul)
│┌dacă y>x atunci
││ s←s+y; x←y
││altfel
││┌dacă x=y atunci s←s-y
││└■
│└■
└■
scrie s

Barem: structură de tipul cerut 2 p; câte 1 p pentru expresia inițială, expresia finală și actualizarea doar automată a contorului; algoritm complet și corectitudine globală 1 p.

Urmează · 2 min

Oficial: rezervă 2026, varianta 5, pentru în cât timp

2 min

Fragmentul dat:

nr←0
┌pentru i←m,n execută
│ x←i
│ ...
└■

Devine:

nr←0
i←m
┌cât timp i≤n execută
│ x←i
│ ...
│ i←i+1
└■

Barem: câte 1 p pentru inițializarea contorului, expresia de continuare și actualizarea contorului. În lucrare scrii tot corpul, în locul celor trei puncte; aici e prescurtat. Aceeași transformare apare la iulie 2024 var. 3, unde i se cere la fel, cu un repetă în interior, care rămâne neschimbat.

Urmează · 2 min

Ce se cere la BAC

4 mincum apare la examen

Urmează · 4 min

Greșeli care costă puncte

1 mincapcanele de evitat

• Uiți testul din față și corpul se execută și când n-ar trebui.
• Lași condiția nenegată la până când.
• Înlocuiești altă structură decât cea indicată: „prima” și „a doua” se numără în ordinea în care apar în algoritm.
• Lași p←p+1 în corpul lui pentru sau uiți i←i+1 în cât timp, ceea ce dă buclă infinită.
• Scrii doar bucata modificată, nu tot algoritmul.

Urmează · 1 min