Algoritmul și structurile de bază în pseudocod

Pe scurt

1 minesențialul, de recitit oricând

Culorile din lecție:termenidee-cheie

• Un algoritm este o succesiune finită și clară de pași, de la date de intrare la rezultat.
• Variabilele păstrează valori, expresiile le calculează, atribuirea (←) le schimbă.
• Orice algoritm se construiește din trei structuri: liniară, alternativă, repetitivă.
• Lucrarea descrie algoritmii în pseudocod, cu o notație fixă. După această lecție o citești fără efort.

Urmează · 1 min

Ce este un algoritm

3 min

Când îi explici cuiva cum să ajungă la tine acasă, îi dai pași. Dacă pașii sunt bine dați, oricine ajunge, de oriunde pornește din zona stabilită, și ajunge într-un timp finit. Asta e ideea de algoritm.

Formal, un algoritm este o succesiune de operații care transformă datele de intrare în date de ieșire (rezultatul). Programa cere și caracteristicile lui, dar nu le enumeră. În materialele de curs apar de obicei acestea:

Urmează · 3 min

Date, variabile, atribuire

2 min

O variabilă e o cutie cu nume. La un moment dat, are o singură valoare. Atribuirea pune în cutie o valoare nouă, iar cea veche dispare.

s←0
s←s+5
s←s+2

După prima linie s este 0, după a doua 5, după a treia 7. Linia s←s+5 se citește așa: iau valoarea actuală a lui s, adun 5, pun rezultatul în s.

Interschimbarea e un exemplu bun de ce contează ordinea. Vrei să schimbi valorile lui x și y:

aux←x
x←y
y←aux

Dacă ai scrie direct x←y; y←x, ambele ar ajunge la valoarea lui y.

Urmează · 2 min

Notația din lucrare

3 min

Lucrările au aceeași notație, iar enunțul II.1 explică de obicei simbolurile speciale.

Pereche des întâlnită: n%10 este ultima cifră a lui n, iar [n/10] e numărul fără ultima cifră. La fel, x%2=0 înseamnă „x este par”.

Urmează · 3 min

Cele trei structuri de bază

5 min 2 întrebări la final

Structura liniară înseamnă pași unul după altul, în ordinea scrierii.

Structura alternativă alege una dintre două ramuri, după o condiție:

┌dacă x%2=0 atunci
│ y←y*y
│altfel
│ x←x-1
└■

Ramura altfel poate lipsi: atunci, dacă nu e adevărată condiția, nu se întâmplă nimic.

Structura repetitivă repetă un corp de instrucțiuni. Are trei forme:

Diferența dintre primele două se vede pe un exemplu mic. Pornește cu x←0:

┌cât timp x>0 execută
│ x←x-1
└■

Corpul nu se execută niciodată. Dar aici se execută o dată, iar x devine -1:

┌repetă
│ x←x-1
└până când x≤0

Exact această diferență e punctată în barem la II.1 d, în lecția despre algoritmi echivalenți.

Urmează · 5 min

Structuri una în alta

3 min o întrebare la final

Algoritmii din lucrare au de obicei o structură în alta. Numărul de bare din față îți spune cât de adâncă e o linie. Iată un fragment din rezerva 2026, var. 5, II.1:

┌pentru i←m,n execută
│ x←i
│┌repetă
││┌dacă x%10=k atunci
│││ nr←nr+1
││└■
││ x←[x/10]
│└până când x=0
└■

Citit în cuvinte: pentru fiecare număr de la m la n, iau pe rând cifrele lui și număr de câte ori apare cifra k. Pentru datele din enunț (120, 126 și k=2), baremul dă răspunsul 8: fiecare dintre cele 7 numere de la 120 la 126 are cifra 2 la zeci, iar 122 o mai are o dată la unități.

Când vezi un algoritm nou, încearcă să-l spui într-o propoziție, ca aici. Te ajută mult la cerința b).

Urmează · 3 min

Ce se cere la BAC

1 mincum apare la examen

• II.1 a: urmărești algoritmul (lecția următoare).
• II.1 b: găsești date pentru un rezultat dat.
• II.1 c: îl traduci în C/C++ (modulul despre limbaj).
• II.1 d: îl rescrii cu altă structură repetitivă (lecția despre algoritmi echivalenți).

Urmează · 1 min

Greșeli care costă puncte

1 mincapcanele de evitat

• [n/10] luat drept cifră: e numărul fără ultima cifră; cifra e n%10.
• Ramură atașată greșit: nu urmărești barele și execuți o linie în afara structurii ei.
• Corp executat în plus sau în minus, pentru că nu ai observat dacă testul e la început sau la sfârșit.
• Condiția de la până când citită ca la cât timp.

Urmează · 1 min