s.l.dr.ing.Ciprian -Bogdan Chirila chirila@cs.upt.ro http://www.cs.upt.ro/~chirilaALGORITMI , SCHEME LOGICE SI PSEUDOCOD Structura cursului •Notiunea… [612187]

s.l.dr.ing.Ciprian -Bogdan Chirila
[anonimizat]
http://www.cs.upt.ro/~chirilaALGORITMI , SCHEME
LOGICE SI
PSEUDOCOD

Structura cursului
•Notiunea de algoritm
•Operatii de baza
•Structuri de control de baza

Notiunea de algoritm
•provine din limba arabă
•vine de la numele matematicianului și astrologului arab
Al-Khowarizmi care a trăit în secolul IX
•un tipar de gândire pentru rezolvarea unei probleme
intr-un numar finit de pasi
•un mod de gândire adică gândirea algoritmică

Exemplu de algoritm
•Pasii calculul mediei artimetice a două numere sunt:
•1 -start;
•2 -citește primul număr;
•3 -citește al doilea număr;
•4 -calculează suma lor;
•5 -împarte rezultatul la 2;
•6 -afișează rezultatul calculat;
•7 -stop.

Moduri de exprimare a algoritmilor
•Limbaj natural
•fraze coerente in limba romana care permit obtinerea unei
solutii pentru o problema data.
•Scheme logice
•diagrame de blocuri
•Pseudocod
•propozitii scurte
•cu cuvinte cheie predefinite
•exprimate in engleza sau romana

Schemele logice
•Schemele logice sunt notații grafice formate din blocuri
legate între ele prin săgeți
•O schemă logică descrie grafic pașii unui algoritm
•Totodată ea specifică prelucrările care se execută
asupra datelor

Datele din schemele logice
•variabile
•sunt zone de memorie care își schimbă valoarea și care se
caracterizează printr -un nume
•numele poate fi format dintr -o înșiruire de
•litere mari
•litere mici
•cifre
•semnul underscore “_”
•numele unei variabile începe în mod obligatoriu cu literă
•exemple :
•Aria
•aria
•perimetru
•delta

Datele din schemele logice
•constante explicite
•zone de memorie cu valori fixe, dar fără nume
•apar in textul schemei in atribuirea i=1
•constante simbolice
•zone de memorie cu valori fixe și cu nume
•de exemplu in PI*r*r
•evident caeletrebuiesc definite undeva

Operatii de baza -blocurile
•Blocul de start
•Blocul de stop
•Blocul de citire
•Blocul de scriere
•Blocul de atribuire
•Blocul de decizie

Orientarea blocurilor
•“Curg ” pepagina de sus in jos
•Se dezvolta arborescent
•Sunt legate intre eleprin sageti directionale
•Conectori de pagina
•leaga blocuri aflate peaceeasi foaie de hartie
•cerculete cu numere in ele
•Conectori intre pagini
•leaga blocuri aflate pefoide hartie diferite
•sagetute pline cu numere in ele

Blocurile de start
•este unic in cadrul unei scheme logice
•reprezinta punctul de pornire al schemei
•are forma ovala
•scrie in el cuvantul predefinit start

Blocul de stop
•este unic in cadrul unei scheme logice
•trebuie atins intr-un numar finit de pasi

Blocul de intrare
•se mai numeste sibloc de citire
•opreste executia unui progra m
•citeste de la tastatura valori pecare le stocheaza in
variabile
•tastatura –dispozitiv de intrare
•estesimbolizat printr -un trapez cu baza mare sus

Blocul de intrare
•Tipuri de variabile cepot fi cititte
•Numere intregi
•1, 77, 25
•Numere reale
•1.5, 6.7
•Siruri de caractere
•se citesc toate impreuna
•“nota de la UPC este ”
•“am luat examenul la UPC cu nota”

Exemple de utilizare
•citeste de la tastatura variabile simple x,y,z in ordine
•citeste de la tastatura elementul a[i] al unui sir sau
tablou unidimensional
•citeste de la tastatura elementul a[i][j] care este
•elementul unei matrici
•ireprezinta linia , iarj coloana elementului citit
•Tablourile simatricile se citesc element cu element!!!

Blocul de iesire
•Se mai numeste sibloc de scriere
•Are caefect afisarea valorilor unor variabile peecran
•Ecranul -dispozitiv de iesire
•Reprezentat printr -un trapez cu baza mare jos

Exemple de utilizare
•Afiseaza variabilele simple x,y,z
•Afiseaza elementul a[i] al sirului a
•Afiseaza a[i][j] care este
•elementul unei matrici a
•ireprezinta linia , iarj coloana elementului afisat
•Tablourile simatricile se afiseaza element cu element!!!

Blocul de atribuire
•are rolul de a da valori noi unor variabile
•valorile anterioare ale acelor variabile se vor pierde
•unele atribuiri se pot folosi de valorile “vechi” ale
variabilei ce primește noua valoare
•De exemplu in i=i+1
•inseamna canoul ivafi egal cu vechiul iplus o unitate
•daca iavea valoarea 7 inainte de atribuire atunci dupa
atribuire ivaavea valoarea 8
•estesimbolizat prin dreptunghi

Componentele unei atribuiri
•in partea stângă a semnului egal al unei atribuiri se află
•obligatoriu o variabila ce va primi noua valoare
•în partea dreaptă a semnului egal se află
•o expresie care va fi evaluată iar valoarea rezultată se
atribuie variabilei

Exemplu de utilizare
•i=i+1
•a[i]=7.5
•elementul al i-lea din sirul de reale devine egal cu 7.5
•a[i][j]=70
•elementul de pelinia isicoloana j devine 70
•s=“upc”
•variabila s iavaloarea sirului de caractere “upc”

Blocul de decizie
•din puncte de vedere grafic este reprezentat printr -un
romb
•din el pot ieși în orice direcții două săgeți
corespunzătoare celor două căi de execuție a
algoritmului

Blocul de decizie
•are rolul de a ramifica cursul de execuție ale unui
algoritm
•algoritmul se va executa după acest bloc doar pe una
din ramurile sale
•fie pe ramura cu DA
•fie pe ramura cu NU
•decizia de a alege o ramură sau pe cealaltă se face pe
baza evaluării condiției din bloc

Conditia unui bloc de decizie
•ocondiție este o expresie matematică care
•dacă este evaluată la valoarea zero se consideră falsă
•dacă e evaluată la orice altă valoare diferită de zero se
consideră adevărată
•spre exemplu
•7, -1, 22, 107 se consideră toate valori adevărate
•o (zero) se consideră fals

Conditia unui bloc de decizie
•Pentru exprimarea conditiei se pot folosi operatori
matematici
•Relationali
•Mai mic <, Mai mare >
•Mai mic sau egal <=, Mai mare sau egal >=,
•egal ==, diferit !=
•Logici
•SI &&, SAU ||
•Paranteze pentru expresii logice complexe
•Rezultatul trebuie safie boolean adica adevarat sau fals

Exemple de utilizare

Exemple de utilizare

Structuri de control
•Secventa
•Selectia
•Ciclul cu test initial
•Ciclul cu test final
•Ciclul cu contor

Secventa

Secventa
•cea mai simplă structură de control
•esteo notatie abstracta folosita pentru a defini alte
structuri de control
•nu se foloseste direct in schemele logice
•presupune execuția unui șir ordonat de operații de bază
din cele prezentate anterior
•de exemplu o secvență poate cuprinde
•o citire
•două atribuiri
•o decizie
•din punct de vedere grafic secvența este reprezentată
printr -un dreptunghi marcat pe margini cu două linii
verticale

Selectia

Selectia
•are rolul de a selecta o secvență din două pentru execuție în
funcție de valoarea condiției
•conține
•un bloc de selecție
•cele două secvențe ce se execută atunci cand condiția evaluată
este adevărată respectiv falsă
•Diferența între un bloc de selecție și o structură de selecție
•este aceea că o structură de selecție totdeauna va include un bloc
de selecție
•adică blocul de selecție este parte componentă a structurii de
selecție pe lângă cele două secvențe
•Din punct de vedere grafic structura de control nu implică
vre-un element grafic nou deoarece este reprezentată prin
elementele grafice corespunzătoare blocului de decizie

Selectia cu o singura secventa

Ciclul cu test initial

Ciclul cu test intial
•este formată dintr -o
•condiție
•secvență
•conectate cain figura
•împreună cu secvența și selecția pot fi folosite pentru a
scrie orice algoritm

Functionare
•cât timp condiția este adevărată
•seva executa secvența în mod repetat
•reamintim că secvența reprezintă un șir ordonat de
operații de bază

Reprezentare grafica
•nu apar forme noi
•apar blocurile corespunzătoa re
•blocului decizional
•secvenț a
•sunt aranjate astfel încât
•prima dată să se execute condiția
•apoi dacă este adevărată, pe ramura DA să avem secvența
•pe urmă să revenim în punctul inițial unde evaluăm condiția
din nou
•procesul se repe ta
•putem spune că aranjamentul blocurilor formează o
buclă

Ciclul cu test intial
•Scopul unei astfel de construții este :
•să avem o condiție adevărată când traversăm inițial blocul
condițional
•se execută secvența care are rolul de a modifica variabilele
condiției
•după un număr finit de treceri condiția trebuie să devină falsă
•se bloc heaza astfel execuția secvenței
•se continu acu rularea schemei logice prin blocurile care ar urma
mai jos

Ciclul cu test intial
•dacă condiția este falsă la prima trecere prin blocul
decizional
•atunci secvența nu va ajunge să fie executată niciodată
•dacă condiția este tot timpul adevărată
•algoritmul se va bloca într -o buclă infinită, fără a mai putea
ajunge vreodată la blocul de stop

Ciclul cu test final

Ciclul cu test final
•Structura de control ciclu cu test final este format dintr –
o secvență și o condiție organizate în această ordine ca
în figura
•Această structură este considerată a fi una derivată din
structura de control ciclu cu test inițial.
•Din punct de vedere al funcționării structura se
comportă astfel:
•se execută secvența
•după aceea se evaluează condiția
•dacă condiția este adevărată se merge din nou și se execută
secvența

Ciclul cu test final
•Din punct de vedere grafic nu apar elemente noi
•Sunt aceleasi elemente exact ca în cazul structurii de
control cu test initial
•aranjamentul blocurilor legat prin săgeți este făcut de
asemenea natură încât
•prima să fie secvența
•după ea să fie plasată condiția.
•evident că apare și fenomenul de buclă pe ramura DA a
condiției care ne conduce din nou la secvență când
valoarea logică din condiție este adevărată

Ciclul cu test final
•Se poate observa că această structură va permite
execuția secvenței cel puțin o dată indiferent de ce
valoarea logică conține condiția
•nu este strict necesară
•orice algoritm se poate concepe folosind numai
structuri de control ciclu cu test inițial
•în practică sunt situații când structura cu test final oferă
o soluție mai elegantă din punct de vedere al concepției
algoritmului

Ciclu cu contor

Ciclu cu contor
•structura de control ciclu cu contor este una mai
complexă
•se bazează pe un contor care
•primește o valoare inițială
•parcurge toate valorile unui interval continu
•până se atinge o valoare finală
•se execu tala fiecare pas o aceeași secvență

Ciclu cu contor
•Primul bloc este unul de atribuire care are rolul de a
inițializa contorul cu o valoare inițială
•Apoi se poate observa că urmează un bloc de decizie
care verifică dacă contorul este mai mic decât valoarea
finală
•În caz afirmativ se merge pe ramura DA și se execută
secvența
•Reamintim ca secvența poate conține o subschema formată
din blocuri pentru a face diverse calcule

Ciclu cu contor
•După secvență avem un bloc de atribuire care
incrementează sau altfel spus adună la valoarea
contorului valoarea unui pas.
•Acest pas poate să fie un număr pozitiv sau un număr
negativ, întreg sau zecimal.
•Dacă pasul este pozitiv înseamnă că valoarea contorului va
crește la fiecare trecere prin blocul de incrementare.
•Evident că pentru ca o astfel de structură de control să
funcționeze trebuie ca valoarea inițială să fie mai mică decât
valoarea finală.
•Dacă pasul este negativ atunci contorul va descrește și e
recomandat ca valoarea inițială să fie mai mare ca cea finală.

Ciclu cu contor
•Dacă în blocul decizional contorul a atins valoarea finală
se iese cu execuția pe ramura NU de unde se poate
continua cu alte blocuri ale algoritmului.

Suma a doua numere
•Citim primul numar de
la tastatura
•Citim al 2-lea numar
de la tastatura
•Calculam suma celor
doua numere
•Afisam peecran suma
calculata
citeste a
citeste b
s=a+b
scries

Aria unui dreptunghi
•Citim lungimea de la
tastatura
•Citim latimea de la
tastatura
•Calculam aria cafiind
egala cu lungimea
inmultita cu latimea
•Afisam peecran aria
calculataciteste lung
citeste lat
aria=lung* lat
scriearia

Volumul unui cilindru
•Citim raza bazei de la
tastatura
•Citim inaltimea de la
tastatura
•Calculam volumul cafiind
produs intre 3.14, raza la
patrat siinaltimea
•Afisam peecran volumul
calculatciteste r
citeste h
a=PI*r*r
v=a*h
scriev

Functia modul
•Citim un numar de la
tastatura
•Daca numarul este
pozitiv
•Atunci modulul este
egal cu numarul
•Altfel modulul este
egal cu numarul
negat
•Afisam peecran
modulul numaruluiciteste x
dacax>0
atuncim=x
altfelm=-x
scriem

Functia signum
•Citim un numar de la
tastatura
•Daca numarul este
pozitiv
•atunci signum este egal
cu 1
•altfel daca numarul este
nul
•atunci signum este zero
•altfel signum este -1
•Afisam peecran functia
signumciteste x
daca x>0
atunci s=1
altfel
daca x==0
atunci s=0
altfel s= -1
scrie m

Ce este un sir ?
•sir = secventa de elemente de acelasi tip
•se mai numeste si
•vector
•tablou unidimensional
•accesul la un element se face prin
•numele sirului
•index -orice expresie matematica , incepe de la zero, se pune intre
paranteze drepte
•exemple : a[0], b[7], c[ i+j],d[a[0]]
•un sir de 10 elemente are indecsi de la 0 la 9 inclusiv
•operatii
•citire x=a[0], y=a[0]+b[7]
•atribuire a[0]=1, a[7]=a[0], a[ i+j]=c[ i]

citeste n
i=0
cat timpi<n
citeste a[i]
i=i+1
sfarsit cat timpCitirea unui sir de la tastatura

Citirea siafisarea unui sir
citeste n
i=0
cat timp i<n
citeste a[i]
i=i+1
sfarsit cat timp
i=0
cat timp i<n
afiseaza a[i]
i=i+1
sfarsit cat timp

Suma a doi vectori (siruri)
•Citim vectorul a element cu element
•Citim vectorul b element cu element
•Calculam vectorul c peelemente
•Fiecare element este egala cu suma elementelor
corespondente din a sib
•c[0]=a[0]+b[0]
•c[1]=a[1]+b[1]
•…
•c[n-1]=a[n -1]+b[n -1]
•Deci c[i]=a[ i]+b[ i] ptfiecare i=0,n -1
•Afisam vectorul c, anterior calculat , element cu element

Suma a doivectori (siruri )

Suma a doivectori (siruri )
citeste n
i=0
cat timpi<n
citeste a[i]
i=i+1
sfarsit cat timp
i=0
cat timpi<n
citeste b[i]
i=i+1
sfarsit cat timpi=0
cat timp i<n
c[i]=a[i]+b[i]
i=i+1
sfarsit cat timp
i=0
cat timp i<n
afiseaza c[i]
i=i+1
sfarsit cat timp

Aflarea minimului dintr -un sir
•Se citesc elementele vectorului
•Se initializeaza minimul cu primul element
•Se compara minimul cu toate elementele perand
•Daca cumva vre-un element este mai mic decat minimul
atunci minimul iavaloarea acelui element

Aflarea minimului dintr -un sir
•a
•min=10
•La pasul i=1 a[1]<min ? 5<10 ? da! deci min=5
•La pasul i=2 a[2]<min ? 4<5 ? da! deci min=4
•La pasul i=3 a[3]<min ? 3<4 ? da! deci min=3
•La pasul i=4 a[4]<min ? 11<3 ? nu!
•La pasul i=5 a[5]<min ? 12<3 ? nu!
•La pasul i=6 a[6]<min ? 88<3 ? nu!
•La pasul i=7 a[7]<min ? 90<3 ? nu!
•La pasul i=8 a[8]<min ? 2<3 ? da! deci min=2
•La pasul i=9 a[9]<min ? 100<2 ? nu!0 1 2 3 4 5 6 7 8 9
10 5 4 3 11 12 88 90 2 100

Aflarea minimului dintr -un sir

Aflarea minimului dintr -un sir
citeste n
i=0
cat timp i<n
citeste a[i]
i=i+1
sfarsit cat timp
min=a[0]
i=0
cat timp i<n
daca a[i]<min atunci min=a[ i]
sfarsit cat timp
afiseaza min

Aflarea maximului dintr -un sir
•cese schimba la algoritmul anterior ?
•tema de casa …

Ordonarea unui sir prin metoda bulelor
Prima trecere
•10 7 5 4 12 8
•10 7 5 4 12 8
•7 10 5 4 12 8
•7 5 10 4 12 8
•7 5 4 10 12 8
•7 5 4 10 12 8
•7 5 4 10 8 12
•4 interschimbari

Ordonarea unui sir prin metoda bulelor
A doua trecere
•7 54 10 8 12
•5 7 410 8 12
•5 4 7 10 8 12
•5 4 7 10 8 12
•5 4 7 8 10 12
•3 interschimbari

Ordonarea unui sir prin metoda bulelor
A treia trecere
•5 47 8 10 12
•4 5 78 10 12
•4 5 7 810 12
•4 5 7 8 10 12
•4 5 7 8 10 12
•1interschimbare

Ordonarea unui sir prin metoda bulelor
A patra trecere
•4 57 8 10 12
•4 5 78 10 12
•4 5 7 810 12
•4 5 7 8 10 12
•4 5 7 8 10 12
•0 zero interschimbari

Ordonarea unui sir prin metoda bulelor

Ordonarea unui sir prin metoda bulelor
citeste n
i=0
cat timp i<n
citeste a[i]
i=i+1
sfarsit cat timp

Ordonarea unui sir prin metoda bulelor
•executa
•ni=0
•i=0
•cat timp i<n -1
•daca a[i]>a[i+1]
•atunci
•temp=a[i]
•a[i]=a[i+1]
•a[i+1]=temp
•ni=ni+1
•i=i+1
•sfarsit cat timp
•cat timp ni!=0

Ordonarea unui sir prin metoda bulelor
•citeste n
•i=0
•cat timp i<n
•afiseaza a[i]
•i=i+1
•sfarsit cat timp

Ce este o matrice ?
•matrice = secventa de elemente de acelasi tip grupate pe
doua dimensiuni
•se mai numeste si
•tablou bidimensional
•accesul la un element se face prin
•numele matricii
•index de linie, de coloana
•incep de la zero, se pun intre paranteze drepte
•prima linia, a doua coloana
•exemple: a[0][0], b[7][7], c[i+j][i -j]
•indecsii incep de la 0
•operatii
•citire x=a[0][0], y=a[0][0]+b[7][8]
•atribuire a[0][0]=1, a[7][8]=a[0][0]

Citirea unei matrici
citeste m
citeste n
i=0
cat timpi<m
j=0
cat timpj<n
citeste a[i][j]
j=j+1
sfarsit cat timp
i=i+1
sfarsit cat timp