CAPITOLUL 1.

ALGORITMI
I.1. Noțiunea de algoritm, caracteristici
Definiție:
Prin algoritm înţelegem o succesiune finită de operaţii cunoscute care se execută într-o succesiune
logică bine stabilită astfel încât plecand de la un set de date de intrare, să obtinem într-un interval de
timp finit un set de date de ieşire.
Caracteristicile algoritmilor
Finitudine – proprietatea algoritmilor de a furniza datele de ieşire într-un timp finit (adicadupa un
număr finit de paşi).
Claritatea - algoritmul trebuie să descrie operaţiile clar şi fără ambiguiăţi.
Generalitatea – proprietatea algoritmilor de a rezolva o intreagă clasă de probleme de acelaşi fel.
Corectitudinea – spunem că un algoritm este corect dacă el furnizează în mod corect datele de ieşire
pentru toate situaţiile regăsite în datele de intrare.
Eficienţă - capacitatea algoritmului de a da o soluţie la o problema într-un timp de executie cât mai
scurt, folosind cât mai puţină memorie.
Etapele rezolvării problemelor
Rezolvarea unei probleme este un proces complex, care are mai multe etape.
1. Analiza problemei, pentru a stabili datele de intrare şi de ieşire.
2. Elaborarea unui algoritm de rezolvare a problemei.
3. Implementarea algoritmului într-un limbaj de programare.
4. Verificarea corectitudinii algoritmului implementat.
5. Analiza complexității algoritmului.
I.2. Obiectele cu care lucrează algoritmii
Date
Orice algoritm lucrează cu date, după cum urmează:
 Date de intrare: datele pe care trebuie sa le primească un algoritm
 Date de manevra: date temporare, necesare algoritmului pentru a obtine datele de iesire pe
baza datelor de intrare
 Date de iesire: datele pe care trebuie sa le furnizeze algoritmul
Datele cu care lucreaza algoritmii pot fi clasificate din mai multe puncte de vedere:
a) În functie de posibilitatea de a-si modifica valoarea, datele sunt:
 Constante: date care nu îsi modifica valoarea pe parcursul algoritmului
 Variabile: date care îsi modifica valoarea pe parcursul algoritmului
b) În functie de valoarea lor, datele sunt:
 Date numerice: au ca valori numere:
  Naturale
 Întregi
 Reale
 Date alfabetice: au ca valori caractere sau siruri de caractere
 Date logice: au valoarea adevarat sau fals
Operatori
Operatorii au rolul de a preciza ce operații se vor realiza asupra datelor cu care lucrăm.
Operatorii se aplică doar anumitor tipuri de date.
Tipuri de operatori
 aritmetici
+ (adunare)
- (scădere)
* (înmulțire)
/ (împărțire)
div (câtul împărțirii a două numere întregi)
mod (restul împărțirii a două numere întregi)
 relaționali < , >, ≤, ≥, =, ≠
 logici
AND (si)
OR (sau)
NOT (negație)
Proprietati (Relatiile lui Morgan):
1) NOT (a AND b)=NOTa OR NOTb
2) NOT (a OR b)=NOTa AND NOTb

Expresii
Ca și la matematică, o expresie este formată din operanzi și operatori. În funcție de tipul de date,
vor fi aplicați operatori specifici.
Evaluarea unei expresii: Pentru evaluarea expresiilor se respectă regulile de bazăînvățate la
matematică. Se evalueazăîntâi expresiile dintre parantezele rotunde, apoi se execută operațiile în
ordinea priorității lor. Dacă există operații cu aceeași prioritate, ele se executăîn ordine, în funcție
de asociativitatea lor. Prioritatea 1 este considerată cea mai mare.
 I.3. Reprezentarea algoritmilor
Operațiile pe care un calculator le poate executa sunt:
 Operații de intrare/ieșire =operațiile de citire/scriere
Operația de citire este operația prin care se preiau date de la un dispozitiv de intrare (ex. de la
tastatură - de la utilizator)
Operația de scriere este operația prin care sa preiau date din memoria interna a calculatorului si se
transfera către un dispozitiv de ieșire (ex: către monitor - către utilizator)
 Operații de atribuire
 Operații decizionale
Vom folosi două modalități de reprezentare a algoritmilor:
PSEUDOCOD = limbaj apropiat limbajului nostru natural, dar care este de asemenea foarte
apropiat și de limbajele de programare in care vor fi transpuși algoritmii.
SCHEMA LOGICĂ = Reprezentare grafică. Fiecărui tip de prelucrare elementară (fiecărei operații)
îi corespunde un simbol grafic. Prelucrările succesive sunt indicate prin conectarea prelucrărilor
elementare şi prin săgeţi.
Blocurile specifice schemelor logice

SIMBOL DENUMIRE SEMNIFICAŢIE

Bloc terminal Marchează începutul

START algoritmului

Bloc terminal Marchează sfârşitul

algoritmului
STOP

Bloc de intrare / citire a Se face transferul de date de

datelor de intrare la utilizator către algoritm
Citeşte a,b
 Bloc de ieşire / scriere a Se face transferul de date
datelor de ieşire către utilizator
Scrie a,b

Bloc de atribuire Variabilei x i se atribuie

valoarea expresiei
x ← expresie

Bloc de prelucrare În interior se scriu

instrucţiunile sau un nume
prelucrare O prelucrare este compusă
ce desemnează un grup de
din mai multe instrucţiuni
instrucţiuni
elementare

Bloc de decizie în care se Dacă condiţia este adevărată

evaluează condiţia se execută ramura “DA”,
NU DA obţinându-se o valoare altfel se execută ramura
Condiţie
logică “Adevarat” sau “Fals” “NU”

Bloc conector logic Conectează mai multe

puncte din algoritm

Bloc conector de pagină Specifică pagina cu care se

continuă schema
3

Limbajul Pseudocod

Limbajul pseudocod este un ansamblu de convenţii (codificări) care definesc operaţiile

(instrucţiunile) permise pentru reprezentarea algoritmilor. Respectand aceste convenţii, chiar în
forme diferite, algoritmii reprezentaţi în pseudocod pot fi citiţi de orice persoană, indiferent că este
sau nu programator.

Limbajul pseudocod nu respectă o sintaxa anume, nu are un standard. Sunt doar nişte convenţii pe
care trebuie să le respectăm atunci când reprezentăm un algoritm. Înstructiunile se pot scrie în limba
engleză sau în limba română. În acest material şi în cele ce urmează vom adopta un limbaj cu
instrucţiuni în limba română.

În pseudocod putem scrie declarări de variabile, specificând numele şi tipul lor. Pe lângă declaraţiile
de variabile, limbajul pseudocod conţine cuvinte cheie, instrucţiuni (început, sfârşit, intrare/ieşire,
atribuire, decizie, selecţie, repetitive), proceduri/funcţii. Toate acestea vor fi prezentate pe larg în
fişa de documentare următoare.
Prezentăm mai jos corespondenţa între instrucţiunile pseudocod şi blocurile din schemele logice.

INSTRUCŢIUNE SIMBOL SCHEMĂ

DENUMIRE
PSEUDOCOD LOGICĂ

a, b, c intregi -
Declaratii de variabile
x,z reale

Citeşte a,b Citirea datelor de intrare Citeşte a,b

Scrie a,b Scrierea datelor de ieşire Scrie a,b

x ← 10
Instrucţiune de atribuire x ← expresie
a ← a+1

| instructiune1 Bloc de Instrucţiuni

| instructiune2 O prelucrare este compusă din prelucrare
mai multe instrucţiuni elementare
| instructiune3
|_▄

┌dacă c atunci Instrucţiune de decizie în care se

evaluează condiţia obţinându-se o NU DA
| execută p Condiţie
valoare logică “Adevarat” sau
|altfel “Fals”

| execută q
|▄

I.4. Principiile programării structurate

Programarea structurată are ca scop dezvoltarea unor programe uşor de realizat în echipă, uşor de
depanat şi de actualizat. Apar deci câteva principii de care un programator trebuie să ţină seama.
Acestea se numesc principiile programării structurate.

Primul principiu este modularizarea. În cadrul unor probleme complexe este necesară
descompunerea acestora în subprobleme mai simple, pentru care se pot scrie module de program
mai simple. Fiecare modul este independent de celelalte, în final ele interacţionând printr-un
program principal, un fel de interfaţă. Modulele pot fi implementate de programatori diferiţi din
cadrul unei echipe. Ele pot fi testate, modificate, depanate în mod independent, neafectând şi
celelalte module.
Modulele au aceeaşi structură ca şi programele principale, putând declara variabile atât în module
(numite variabile locale) cât şi în programul principal (numite variabile globale). Modulele create
sunt proceduri şi funcţiişi vor fi studiate în cadrul unui limbaj de programare.

Un al doilea principiu este structurarea datelor şi a prelucrărilor. Datele se pot grupa în structuri
de date aşa cum am aratat mai sus. Prelucrările asupra datelor se pot grupa şi ele în structuri despre
care vorbim în teorema Bohm-Jacopini.

Teorema Bohm-Jacopini

Teorema Bohm-Jacopini afirmă ca orice algoritm se poate reprezenta folosind 3 tipuri de structuri
fundamentale: structură liniară, structură alternativă şi structură repetitivă.

1. Structura liniară

Structura liniară (numită şisecventială) este alcatuită din urmatoareleinstrucţiuni:

- comentarii

- declararea variabilelor

- instrucţiunea de citire

- instrucţiunea de scriere

- instrucţiunea de atribuire

- instrucţiunea compusă (sau blocul de instrucţiuni)

Comentarii

Putem adaugă comentarii în cadrul algoritmului pentru a descrie operaţiile efectuate sau a da
indicaţii necesare la implementare. Adeseori, când se lucrează în echipă, comentariile sunt foarte
necesare.

Sunt mai multe variante în care putem să scriem comentarii. În general, fiecare programator va
folosi ceea ce crede că este mai uşor de înteles sau mai rapid de scris.

În pseudocod, comentariile sunt scrise între {}.

Declararea variabilelor

La începutul algoritmului trebuie să se precizeze datele de intrare, datele de ieşire, datele de

manevră şi tipul lor. O variabilă nu se poate declara de mai multe ori în cadrul aceluiaşi algoritm.

Exemple
a întreg
b real
x caracter

Instrucţiunea de citire

Efectul instrucţiunii este de a da valori (de la tastatură sau dintr-un fişier) variabilelor de intrare cu
care lucrăm.

Exemplu

Citeste a, b, x
Instrucţiunea de scriere

Instrucţiuneaafişează pe ecran sau în fişier valorile variabilelor.

Exemplu
Scrie a, b

Instrucţiunea de atribuire

Efectul instrucţiunii este acela de a atribui valoarea din dreapta săgeţii variabilei specificată în
stanga. În cazul în care în dreapta avem o expresie, aceasta se va evalua şi apoi valoarea va fi
atribuită variabilei din stanga.

variabilă ← expresie

//Exemplu:
a ← 56
b ← a-2*a
c ← c+1

Ultima atribuire are un sens deosebit, adică variabila c va lua valoarea avută la pasul anterior al
algoritmului mărită cu 1.

Blocul de instrucţiuni

Este folosit pentru a efectua mai multe instrucţiuni, în ordinea în care sunt scrise. Sunt mai multe
variante de marcare a începutului şisfarşitului de bloc de instrucţiuni. Mai jos prezentăm două dintre
ele, urmând ca pe parcursul modulului să folosim varianta cu paranteze.

Exemplu
| instructiune1
| instructiune2
| instructiune3
 |_▄

2. Structura alternativă

Auzim în viaţa de zi cu zi afirmaţii de genul: DACĂobţin note de promovare la toate examenele,

ATUNCI voi lua diploma, ALTFEL trebuie să mai învăţ.

Se remarcă trei cuvinte ce au un rol deosebit: DACĂ, ATUNCI, ALTFEL. Propoziţia are trei
componente şi anume:

 condiţie, transcrisă prin “obţin note de promovare la toate examenele”, condiţie pe care o
notăm cu c;

 acţiune transcrisă prin “ voi lua diploma”, notată cu p, acţiune asociată cu ATUNCI, adică
se execută doar dacă “obţin note de promovare la toate examenele”;

 acţiune transcrisă prin “ trebuie să mai învăţ”, notată cu q, acţiune asociată cu ALTFEL,
adică se execută dacă NU “obţin note de promovare la toate examenele”;

Folosind notaţiile făcute, afirmaţia se poate transcrie în pseudocod sau schemă logică.

Secvenţa de instrucţiuni se numeştestructură alternativăşi se poate reprezenta şi grafic. Structura

alternativă admite şi o formă particulară, caz în care avem o ramură vidă (adică nu se execută nici o
operaţie):

┌dacă c atunci ┌dacă c atunci

| execută p | execută p
|altfel |▄
| execută q
|▄

NU DA NU DA
altfel atunci altfel atunci
Condiţie Condiţie

Execută q Execută p Execută p

Exista cazuri în care condiţia poate fi mai complexă, de genul:

DACA obţin note de promovare la toate examenele ŞI toate notele sunt peste 9, ATUNCI voi putea
beneficia de bursă, ALTFEL nu.
Notând prima condiţie cu c1 (obţin note de promovare la toate examenele), cu c2 a două condiţie
(toate notele sunt peste 9), cu p acţiunea „voi putea găsi un job cu salariu mai mare” şi cu q acţiunea
„salariul va fi mai mic”, se va folosi operatorul logic „and” iar condiţia va fi compusă: „c1 and c2”.

Observaţii

 Atât ramura „ATUNCI” cât şi „ALTFEL” permit executărea unei singure instrucţiuni. În
cazul în care este necesară efectuarea mai multor instrucţiuni, acestea se grupează într-o
singură instrucţiune compusă.
 Uneori avem o instrucţiune de decizie subordonată unei alte instrucţiuni (de decizie sau de
alt fel). Este important ca instrucţiunea subordonată să fie scrisă identatfaţă de instrucţiunea
care o subordonează. Acest mod de scriere nu este obligatoriu pentru funcţionarea
algoritmului însă face programele mai uşor de urmărit şi de actualizat.

3. Structura repetitivă

O structură repetitivă se caracterizează prin posibilitatea efectuării repetitive a unei secvenţe de

instrucţiuni, cât timp este îndeplinită o anumită condiţie sau pâna când se îndeplineşte o anumită
condiţie. Repetiţiasecvenţei de instrucţiuni se numeşte „iteraţie”.

Structurile repetitive se mai întalnesc sub numele de structuri ciclice sau cicluri.

Există trei tipuri de structuri repetitive:

 Structura cu număr necunoscut de repetiţii cu test iniţial (CÂT TIMP)

 Structura cu număr necunoscut de repetiţii cu test final (REPETĂ–PÂNĂ CÂND)
 Structura cu număr cunoscut de repetiţii (PENTRU)

Structura repetitivă cu test iniţial - CÂT TIMP

Structura repetitivă cu test iniţial are două componente:

 conditia, o expresie logică ce poate fi evaluată prin valoarea TRUE sau FALSE, condiţie pe
care o notăm cu c;

 actiune, o secvenţă de instrucţiuni ce se vor execută repetat, notată cu a, acţiune asociată cu

EXECUTĂ;

Folosind notaţiile făcute, structură repetitivă cu test iniţial se poate scrie astfel:

┌cât timp c execută

| a
|▄

Principiul de executăre este următorul:

Cât timp condiţiac este adevarată, se execută secvenţa de instrucţiuni „a”. Execuţia se opreşte când
condiţiac nu mai este adevarată.
Observaţii:

 Pentru ca structură repetitivă să nu intre într-un ciclu infinit, trebuie ca secvenţa de

instrucţiuni să modifice cel puţin una din variabilele care intervin în condiţie astfel încât
aceasta să poată deveni falsă la un moment dat.
 Dacă de la bun început condiţia are valoarea fals, secvenţa de instrucţiuninu se execută
nici măcar o data.

Structura repetitivă cu test final – REPETĂ – PÂNĂ CÂND

Ca şi structură repetitivă cu test iniţial, structură repetitivă cu test final are aceleaşi două
componente:

 condiţia, o expresie logică ce poate fi evaluată prin valoarea TRUE sau FALSE, condiţie pe
care o notăm cu c;

 actiune, o secvenţă de instrucţiuni ce se vor executa repetat, notată cu a, acţiune asociată cu

EXECUTĂ;

În structură repetitivă cu test final mai întâi se execută secvenţa de instrucţiuni “a” şi apoi se
evaluează condiţia. De aici şi numele de structură cu test final.

În pseudocod forma generală a structurii repetitive cu test final este:

┌repetă
| a
└până când NOT c

Observaţii:

 Pentru ca structură repetitivă să nu intre într-un ciclu infinit, trebuie ca secvenţa de

instrucţiuni să modifice cel puţin una din variabilele care intervin în condiţie astfel încât
aceasta să poată deveni adevărată la un moment dat.
 Spre deosebire de structură repetitivă cu test iniţial, structură repetitivă cu test final
efectuează o data secvenţa de instrucţiuni înainte de a testa condiţia.

Structura repetitivă cu număr cunoscut de repetiţii – PENTRU

În pseudocod forma generală a structurii repetitive cu număr cunoscut de repetiţii este:

┌pentru contor ← exp_i, exp_f execută

| a
|▄
unde:
 exp_işiexp_f sunt expresii ale căror valori sunt evaluate în cadrul repetiţiilor;
  contor este o variabilă ce va lua prima dată valoarea expresiei iniţialeexp_i, urmând apoi să
se modifice până la valoarea expresiei finale exp_f;
 a este secvenţă de instrucţiuni ce se va executa repetat;
Principiul de funcţionare al structurii repetitive cu număr cunoscut de repetiţii este următorul (am
făcut presupunerea că exp_i<= exp_f):

Pasul 1: Se evaluează exp_i (expresia iniţială);

Pasul 2: Se atribuie variabilei contor valoarea expresiei exp_i;
Pasul 3: Se evaluează exp_f (expresia finală);
Pasul 4: Dacă valoarea variabilei contor este mai mare decât valoarea expresiei exp_f, atunci se
iese din structură repetitivă. Dacă valoarea varibileicontor este mai mică sau egală cu valoarea
expresiei exp_f, atunci se execută secvenţa de instrucţiuni „a” şi se incrementează (îşimăreşte
valoarea cu 1) valoarea variabilei contor, după care se reia pasul 3.

Observaţii:

 Exp_işiexp_f pot fi expresii de evaluatsaudoarvariabile simple ce au valori date.

 De regulă folosim structuri repetitive cu număr cunoscut de repetiţii în care dorim ca
variabila contor să creasca de la exp_i la exp_f, caz în care evident valoarea exp_i trebuie să
fie mai mica decât exp_f.
 Într-o astfel de structură, secvenţa de instrucţiuni se execută de (exp_f – exp_i +1) ori. Dacă
însă folosind acest tip de structură, valoarea iniţială a lui exp_i este mai mare decât exp_f,
atunci secvenţa de instrucţiuni „a” nu se execută niciodată.

Dacă forma structurii PENTRU este:

┌pentru contor ← exp_i, exp_f, x execută

| a
|▄

unde x este o variabilă numerică, atunci contorul va creşte din x în x. Când x lipseşte din structură
PENTRU, contorul, creşte cu 1.

 În structurile repetitive cu număr cunoscut de repetiţii în care dorim ca variabila contor să

scadă de la exp_ila exp_f, trebuie ca exp_i>= exp_f, iar variabila contor va scădea din x în
x sau cu câte o unitate. Dacă însă folosind acest tip de structură,valoarea iniţiala a lui exp_i
este mai mica decât exp_f, atunci secvenţa de instrucţiuni „a” nu se execută niciodată.
 Se observă că folosind scheme logice nu se poate reprezenta structură PENTRU decât cu
ajutorul uneia din structurile repetitive cu testare iniţială sau finală.

Transformări dintr-un tip de structură repetitivă în altul

1. Simularea structurii repetitive CÂT TIMP cu REPETĂ-PÂNĂ CÂNDse face astfel:

┌cât timp c execută Dacă c atunci
| a |┌repetă
|▄ || a
|└până când NOT c
|▄
Se observă că este necesară testarea iniţială a condiţiei deoarece, spre deosebire de structură
CÂT TIMP, structură REPETĂ – PÂNĂ CÂND efectuează cel puţin o dată secvenţa înainte de
a testa condiţia.

2. Simularea structurii repetitive REPETĂ-PÂNĂ CÂND cu CÂT TIMP se face astfel:

┌repetă a //se execută secvenţa a

| a ┌cât timp c execută
└până când NOT c | a
|▄
Se observă că în acest caz este necesar să executăm o dată secvenţa de intrucţiuni în afara
ciclului.

3. Simularea structurii repetitive PENTRU cu CÂT TIMP se face astfel:

┌pentru contor ← vi,vf execută Contor ← vi

| a; ┌cât timp contor<=vf execută
|▄ | a;
| contor ← contor + 1;
|▄
Se observă că în acest caz este necesar să scriem explicit instrucţiunea care creşte contorul cu 1.

4. Simularea structurii repetitive PENTRU cu REPETĂ–PÂNĂ CÂND se face astfel:

┌pentru contor ← vi,vf execută Contor ← vi

| a; Dacă contor<=vf atunci
|▄ | ┌ repetă
| | a;
| | contor ← contor + 1;
| └până când contor>vf
|▄
Dintre toate aceste structuri repetitive, singura indispensabilă este cea cu test iniţial (CÂT
TIMP), celelalte putând fi obţinute din aceasta, după cum am văzut mai sus.