Algoritmi si Programare

Algoritmi şi programare – Curs 3 1

3. Limbajul de programare Pascal

3.1. Structura programelor Pascal În continuare este prezentat un exemplu de program Pascal, care deşi este foarte simplu, el conţine elemente care permit ilustrarea structurii unui program Pascal, a vocabularului limbajului şi a unităţilor sale lexicale.

PROGRAM Exemplu; CONST n = 1; VAR x,y,z:integer;

BEGIN x := 20; writeln(‘Introduceti un nr. intreg:’); readln(z); y:= (x+y)/2; writeln(’Rezultatul este:’, y); readln; END.

Un program sursă Pascal este o succesiune de caractere, care, la fel ca o frază a limbajului natural, respectă anumite reguli sintactice, ca de exemplu: se utilizează „semne de punctuaţie”, cuvintele sunt folosite într-o anumită succesiune, „propoziţiile” au anumite legături între ele.

Un program Pascal este alcătuit din următoarele părţi: Antet; Parte declarativă; Parte executabilă. Dintre aceste părţi, obligatorie este doar partea executabilă.

3.2 Vocabularul limbajului

În scrierea programelor Pascal pot fi folosite doar anumite caractere (simboluri) care alcătuiesc vocabularul limbajului. Acesta cuprinde: literele mari şi mici ale alfabetului latin, precum şi caracterul „_” inclus tot în

categoria literelor, fiind folosit ca element de legătură într-un identificator compus; cifrele zecimale din intervalul 0 – 9 .

antet parte declarativă

parte executabilă

2 Algoritmi şi programare – Curs 3

simboluri speciale, reprezentând operatori şi delimitatori operatori: - , +, *, / , = , := , < , >, etc. delimitatori: ( , ) , [ , ] , { , } , ’ , etc.

cuvinte cheie: and, asm, array, begin, case, const, else, if, end, etc. Cuvintele cheie pot fi folosite doar în scopul pentru care au fost definite, ele nu pot fi redefinite de către utilizatori.

3.3. Unităţile lexicale ale limbajului Pascal

Unităţile lexicale sunt grupuri de caractere cu semnificaţie de sine stătătoare. Acestea sunt:

Identificatorii. Un identificator este o secvenţă de litere şi cifre, prima fiind obligatoriu literă. El desemnează variabile, constante, tipuri, nume de proceduri, funcţii. O parte a identificatorilor sunt predefiniţi (standard) iar o altă parte sunt definiţi de către utilizator. Spre deosebire de cuvintele cheie, identificatorii predefiniţi pot fi redefiniţi de către utilizatori.

Numerele. Un număr desemnează o valoare numerică întreagă sau reală. Sintaxa (modul de scriere al unui număr) în limbajul Pascal este:

parte_întreagă.parte_fracţionară E cifre_exponent exemplu: 3,1415926536E+00 este modul implicit de afişare al constantei PI

Şirurile de caractere, care reprezintă o secvenţă de caractere cuprinse între apostroafe. De exemplu, ‘ Introduceti un nr. intreg’.

Comentariile care sunt reprezentate de o secvenţă de caractere incluse între paranteze acolade. Comentariile nu influenţează execuţia programului şi au doar un rol explicativ.


Tipuri de date, constante, variabile, expresii Un program Pascal conţin o descriere a acţiunilor ce trebuie executate de calculator, precum şi o descriere a datelor ce sunt manevrate de aceste acţiuni. Acţiunile sunt descrise prin instrucţiuni, iar datele prin declaraţii. Un tip de date defineşte atât o mulţime de valori, cât şi o mulţime de operaţii ce se pot efectua cu aceste valori. Fiecărei date i se asociază un tip unic. Tipurile de date implementate în limbajul Turbo Pascal se pot clasifica astfel: - Tipuri simple: - tipuri predefinite - întregi - reale

- logice - caracter

- tipul enumerare - tipul subdomeniu (interval) - Tipuri de date structurate: - tipul de date tablou (array) - tipul de date şi de caractere (string) - tipul de date mulţime (set) - tipul de date înregistrare (second) - tipul de date fişier (file) - tipul de date obiect (object) - Tipuri de date pointer (referinţă) - Tipul procedural Tipurile date simple: întregi, logice, caracter, enumerare şi subdomeniu constituie tipuri ordinale de date, adică tipuri caracterizate printr-o mulţime finită de valori, tipuri caracterizate printr-o mulţime finită de valori, pe care este definită o ordine liniară şi, astfel, pentru orice element al unui asemenea tip se poate stabili numărul său de ordine (cu ajutorul funcţiei ORD), elementul predecesor (cu funcţia PRED) şi elementul succesor (cu funcţia SUCC). Tipurile reale nu sunt tipuri ordinale. Declararea tipurilor de date definite de utilizator se face în secţiunea declarării type, având următoarea sintaxă: type nume_tip_1 = tip_1; nume_tip_2 = tip_2; ....................


unde nume_tip_1, nume_tip_2,... reprezintă identificatori cu noilor tipuri de date, iar tip_1, tip_2, ... sunt tipuri de date standard sau definite de utilizator. Tipuri de date simple, predefinite - Tipuri întregi, desemnate prin identificatorii standard: byte, shortint, integer, word, logint, reprezintă submulţimi de numere întregi. Domeniile de valori şi modul lor de reprezentare în memoria internă a calculatorului sunt prezentate în tabelul următor:

Tip Domeniu de valori Reprezentare internă

Semn

Byte 0..255 1 octet fără semn ShortInt -128..127 1 octet cu semn Integer -32768..32767 2 octet cu semn Word 0..65535 2 octet fără semn

LongInt -2147483648..2147483647 4 octet cu semn Datele corespunzătoare tipurilor întregi cu semn sunt reprezentate în cod complementar. Operaţii efectuate cu date întregi: Operaţii aritmetice: +, -, *, / (cu rezultat real) MOD, DIV - rest şi cât. Operaţii aritmetice pe biţi:

- not (negaţia aritmetică) - operator folosit pentru complementarea reprezentării binare a unui număr întreg.

- shl - deplasare la stânga a reprezentării interne a unui număr întreg cu un număr specificat de poziţii binare. Sintaxa folosirii acestui operator este:

a shl b - şi are ca rezultat deplasarea la stânga a reprezentării interne a lui a cu b poziţii binare. - shr - operator de deplasare la dreapta a reprezentării interne a unui număr întreg cun

un anumit număr de poziţii binare. Sintaxa este asemănătoare cu a operatorului shl. - and, or, xor sunt operatorii şi aritmetic, sau aritmetic şi sau exclusiv aritmetic. Ei se

aplică bit cu bit reprezentărilor interne a celor două numere. Observaţie. În limbajul Turbo Pascal există constantele simbolice predefinite MaxInt şi

MaxLongint reprezentând cel mai mare număr de tip integer, respectiv cel mai mare număr de tip longint. - Tipuri reale - desemnat prin identificatori standard real, single double, extended şi comp, reprezintă submulţimi de numere reale. Elementele tipurilor reale sunt reprezentate, în


memoria internă a calculatorului în virgulă mobilă. Domeniile de valori, dimensiunea reprezentării şi precizia valorilor se prezintă conform tabelului.

Tip Domeniu de valori Reprezentare internă

Cifre semnificative

Real 2.9E-29..1.7E38 6 octeţi 11-12 Single 1.5E-29..3.4E38 4 octeţi 7-8 Double 5.0E-324..1.7E308 8 octeţi 15-16

Extended 3.4E-4932..1.1E4932 10 octeţi 19-20 Comp -2.0E-63+1..2.0E63-1 8 octeţi 19-20

Tipul de date comp este o mulţime de numere întregi, cu valori în intervalul specificat, dar în calcule intră ca un număr real fără parte fracţionară. Asupra datelor de tip real se pot aplica operatorii aritmetici +, -, *, / precum şi operatorii relaţionali (=, <>, <, <=, >, >=). Observaţii În limbajul Turbo Pascal exista constanta simbolică de tip real PI reprezentând numărul . Asupra datelor de tip numeric (întregi sau reale) se pot aplica şi funcţiile standard prezentate mai jos: ABS(x) - valoarea absolută (modulul) numărului x; SQR(x) - x la puterea a doua; SQRT(x) - radical din x; EXP(x) - funcţia exponenţială ex; LN(x) - logaritm natural din x; SIN(x), COS(x), ARCTAN(x) - funcţiile trigonometrice sin, cos, arctg; INT(x) - partea întreagă a lui x; FRAC(x) - partea fracţionară a lui x; - Tipul boolean (logic) desemnat prin identificatorul standard boolean, este reprezentat printr-o mulţime formată din 2 elemente false şi true (fals şi adevărat). Pentru a se asigura compatibilitatea cu sistemul Windows, în versiunea 7.0 a limbajului Turbo Pascal au fost introduse tipurile bytebool, wordbool şi longbool. Cele 4 tipuri booleene sunt reprezentate astfel: - Boolean - pe 8 biţi (1 octet) - Bytebool - pe 8 biţi (1 octet) - Wordbool - pe 16 biţi (2 octeţi) - Longbool - pe 32 biţi (4 octeţi) Deoarece tipul boolean este un tip ordinal, avem relaţiile: - false < true - ord (false) = 0


- ord (true) = 1 - succ (false) = true - pred (true) = false

Tipul de date caracter CHAR Tipul CHAR este definit de o mulţime finită şi ordonată de caractere care cuprinde: litere, cifre, caracterul spaţiu, caractere speciale, etc. Setul de caractere utilizat este setul ASCII. Un caracter se reprezintă în memoria internă printr-un grup de 8 cifre binare (1 octet). Valoarea unui caracter se poate scrie în mai multe moduri: - un caracter imprimabil cuprins între apostrofe: ‘a’, ‘+’, ‘$’, ‘F’, etc.

- un număr în intervalul 0 255 (codul ASCII), precedat de caracter #: #65 (‘A’), #40(‘0’).

Tipul char este un tip ordinal, deci mulţimea caracterelor este ordonată, în consecinţă se pot aplica funcţiile ord, pred şi succ. Funcţia ord reprezintă şi codul ASCII al caracterului. O altă funcţie, specifică tipului CHAR este funcţia chr care furnizează caracterul corespunzător unui anumit cod ASCII. Exemple: - ORD (‘0’) = 48 - chr(‘50’) = ‘2’ - succ (‘B’) = ‘C’ - ORD (‘1’) = 49 - chr(‘66’) = ‘B’ - pred (‘A’) = ‘@’ - ORD (‘A’) = 65 - chr(‘90’) = ‘Z’ - succ (‘a’) = ‘b’ Se observă că funcţiile ord şi chr sunt funcţii inverse. Astfel, dacă C este o variabilă de tip CHAR, iar x o variabilă de tip byte care reprezintă codul ASCII al caracterului C, vom avea: ORD(C) = x; CHR(x) = C sau ORD(CHR(x)) = x CHR(ORD(C)) = C. Caracterele pot fi comparate între ele pe baza poziţiei lor în setul de caractere ASCII; astfel: C1< C2 ORD(C1) < ORD(C2) Asupra datelor de tip CHAR se poate aplica funcţia predifinită UPCASE. Această funcţie converteşte literele mici în litere mari; iar celelalte caractere nu sunt afectate de ea.

Instrucţiunile limbajului Pascal

Instrucţiuni simple


O instrucţiune se numeşte simplă dacă nu conţine alte instrucţiuni. - Instrucţiunea de atribuire are forma: v: = e; unde v este o variabilă, iar e este o expresie. Prin execuţia unei instrucţiuni de atribuire, expresia e este evaluată şi rezultatul se atribuie variabilei v. Variabila şi rezultatul evaluării trebuie să fie de tipuri identice sau de tipuri compatibile. Două tipuri sunt compatibile dacă ambele sunt subdomenii ale aceluiaşi tip de bază sau unul este subdomeniul al celuilalt. Excepţie de la această regulă fac variabilele de tip real şi expresiile de tip întreg. Exemple: delta: = b*b-4*a*c; h: = (x<y+z) or (a>=b+c); Instrucţiunea apel de procedură realizează, aşa cum sugerează şi denumirea, apelul unei proceduri. Acest apel se face prin numele procedurii urmat eventual de o listă de argumente (variabile şi expresii) separate prin virgulă: nume(p1, p2,...,pn); Parametrii p1, p2, ...,pn pot fi constante, variabile, expresii, funcţii, proceduri. Procedura se defineşte la începutul programului şi se inserează în locul în care se doreşte executarea ei. Exemple:

1. Instrucţiunea de citire care constă din apelul procedurii read sau readln : read(v1,v2, . . . vn); sau readln(v1,v2, . . . vn); unde v1,v2, . . . ,vn sunt variabilele ce urmează a fi citite.

2. Instrucţiunea de scriere care constă din apelul procedurii write sau writeln: Write(e1,e2, . . en); sau Writeln(e1,e2,. . .,en); unde write şi writeln sunt procedurile standard de scriere iar e1,e2, . . ., en sunt expresii. În urma execuţiei instrucţiunii de scriere pe ecranul utilizator vor fi afişate valorile celor n expresii în ordinea în care au fost precizate în instrucţiunea de scriere. Deosebirea dintre cele două forme ale instrucţiunii de scriere este , la fel ca la instrucţiunea de citire : în primul caz , după afişarea celor n valori cursorul va rămâne după ultima valoare afişată iar în cazul al doilea cursorul va trece în prima poziţie din rândul următor .


Formatele de scriere utilizate în instrucţiunea de scriere Există trei formate de afişare prezentate mai jos : a) e Acesta este formatul implicit , în care o expresie reală se afişează utilizându-se 17 caractere : semn, 11 cifre semnificative, punct zecimal şi 4 caractere pentru exponent (dintre care unul pentru semnul exponentului). Exemplu : -5.4790000000E+04 adică numărul -54790. b) e:nn Acest format este un format cu exponent în care numărul este aliniat la dreapta într-un câmp de cel puţin nn caractere ; tipărirea cu exponent a unei valori reale necesită cel puţin 8 caractere : semn, punct zecimal , o cifră la partea întreagă, una la partea zecimală şi 4 caractere pentru reprezentarea exponentului. Dacă cu acest format se va afişa un număr întreg sau un caracter atunci el se va afişa în cadrul a nn poziţii încadrat la dreapta în această zonă. Exemplu : Write(x:4); unde x are valoarea 23. În urma execuţiei acestei instrucţiuni se va afişa : _ _ 23 c) e:nn:zz Acesta este un format fără exponent care se aplică numai numerelor reale . Numărul real afişat cu acest format se va afişa într-un câmp de cel puţin nn caractere cu un număr de zz zecimale. Exemplu: Write(x:5:2); unde x are valoarea 12.5. Se va afişa : _12.5 Dacă x are valoarea 12.456 atunci se va afişa : 12.45

Instrucţiunea IF Instrucţiunea IF are rolul de a decide care este instrucţiunea ce urmează să se execute dintre două alternative posibile.


Condiţia este o expresie de tip logic (boolean) . Efectul execuţiei acestei instrucţiuni este următorul : se evaluează condiţia de tip logic ; dacă aceasta este adevărată se execută instrucţiune_1 iar în caz contrar se execută instrucţiune_2. Instrucţiunea CASE Instrucţiunea CASE utilizează o expresie (selector) de tip ordinal şi o listă de instrucţiuni, fiecare instrucţiune fiind asociată cu una sau mai multe constante ale tipului selector. Fiecare constantă se asociază cel mult unei instrucţiuni. Forma generală a instrucţiunii este: CASE selector OF lista_1:instrucţiune_1; lista_2:instrucţiune_2; . . . lista_n:instrucţiune_n ELSE instrucţiune_n+1 END; Instrucţiunea CASE are următoarea semnificaţie: se compară pe rând valoarea selectorului cu lista_1, lista_2, . . . lista_n; în cazul în care se găseşte o egalitate a selectorului cu una din constantele din cele n liste, se execută instrucţiunea corespunzătoare, altfel se execută instrucţiune_n+1. Observaţie: partea cu ELSE este opţională. Exemplu: Se consideră următoarea funcţie:

f x

x x dacă xx daca xx daca x

daca x

2

2

2

5 1 35 101 10 20

5 1 20 350 35

unde x este un număr întreg. Se cere un program care să calculeze valoarea acestei funcţii pentru un x oarecare citit de la tastatură.


Vom rezolva această problemă în două variante: cu instrucţiunea IF şi cu instrucţiunea CASE. Reprezentăm algoritmul de rezolvare prezentat în schema logică din figură. Varianta a II-a Se observă din varianta anterioară că variabila x este comparată pe rând cu domeniul (-35 ,10), [10,20),şi [20,35). Din acest motiv vom putea considera pe x ca fiind selector într-o instrucţiune CASE, întrucât x este de tip întreg deci de un tip ordinal. Programul care utilizeată instrucţiunea CASE este următorul: PROGRAM Exemplul_8_3; VAR x,f:integer; BEGIN write('x='); readln(x); CASE x OF -34..9: f:=x*x-5*x+1;


10..19: f:=sqr(x-1); 20..34: f:=sqr(5*x-1) ELSE f:=0; END; writeln('f=',f); readln;

Algoritmi si Programare

Documents

Transcript of Algoritmi si Programare