Limbaje De Programare

www.cartiaz.ro – Carti si articole online gratuite de la A la Z

LIMBAJE DE PROGRAMARE CAPITOLUL 1. ELEMENTE DE LOGICĂ MATEMATICĂ ŞI ALGEBRĂ BOOLEANĂ 1.1. Calculul propoziţiilor 1.1.1. Noţiunea de propoziţie DEFINIŢIA 1.1. Se numeşte propoziţie un enunţ (un ansamblu de cuvinte cărora li s-a dat un sens) despre care se ştie că este sau adevărat sau fals, însă nu simultan şi una şi alta. Exemple de propoziţii: 1) În orice triunghi suma unghiurilor sale este egală cu 180o; 2) 3+2=5; 3) 2>5; 4) Balena este un mamifer. 5) Planeta Saturn este satelit al Pamântului. Propoziţiile 1), 2) şi 4) sunt adevărate dar 3) şi 5) sunt false. O clasă foarte largă de propoziţii adevărate o constituie teoremele din matematică. Contraexemple (enunţuri care nu sunt considerate propoziţii): 1) x+2=5; (enunţurile cu variabile sunt predicate) 2) Deschide uşa !; (enunţ imperativ) 3) Numărul x divide numărul y; (predicat) 4) Atomul de aur este galben. (enunţ absurd) 1.1.2. Valoare de adevăr Notăm cu P2 mulţimea propoziţiilor definite după definiţia 1.1. DEFINIŢIA 1.2. Funcţia v : P2 → {0,1} se numeşte funcţia valoare de adevăr. Fiecărei propoziţii din mulţimea propoziţiilor P2 i se ataşează valoarea 1 dacă propoziţia este adevărată, şi valoarea 0 dacă este falsă. De obicei se vor nota propoziţiile prin litere mici: p,q,r ... şi cu v(p), v(q), 1

www.cartiaz.ro – Carti si articole online gratuite de la A la Z

v(r)... valorile lor de adevăr.

1.1.3. Operatori (operaţii cu propoziţii) Cu ajutorul operatorilor definiţi în continuare se pot construi propoziţii compuse. Negarea propoziţiilor. Negarea propoziţiei este propoziţia "non p", care se notează !p şi care este adevărată când p este falsă şi falsă când p este adevărată. Valoarea de adevăr a propoziţiei !p este dată în tabela următoare: v(p) 1 0

v(!p) 0 1

Conjucţia propoziţiilor. Conjucţia propoziţiilor p,q este propoziţia care se citeşte "p şi q", notată cu pΛq, care este adevărată atunci şi numai atunci când fiecare din propoziţiile p, q este adevărată. Valoarea de adevăr a propoziţiei pΛq este dată în tabela următoare: v(p) v(q) v(p∧q) 0 0 1 1

0 1 0 1

0 0 0 1

Disjuncţia propoziţiilor. Disjuncţia propoziţiilor p, q este propoziţia care se citeşte "p sau q" (notată pVq) şi care este adevărată, atunci şi numai atunci când este adevărată cel puţin una dintre propoziţiile p, q. 2

www.cartiaz.ro – Carti si articole online gratuite de la A la Z

Valoarea de adevăr a propoziţiei pVq este dată în tabela următoare: v(p) v(q) v(p∨q) 0 0 0 1 0 Implicaţia propoziţiilor. Să 1considerăm 1 1

0 1 1 propoziţia compusă (p)Vq a cărei 1

valoare de adevăr rezultă din tabela urmatoare

v(p) v(q) v(!p) v((!p)∨ q) 0 0 1 1

0 1 0 1

1 1 0 0

1 1 0 1

Propoziţia (!p)Vq se notează p → q şi se numeşte implicaţia propoziţiilor p,q (în acestă ordine); p este ipoteza iar q este concluzia. Observăm că (!p)Vq este falsă atunci şi numai atunci când p este adevărată şi q falsă, în celelalte cazuri fiind adevărată. Echivalenţa propoziţiilor. Cu propoziţiile p, q putem forma propoziţia compusă (p→q) Λ (q→p) care se notează p ↔ şi se citeşte "p dacă şi numai dacă q". Din tabela următoare se vede că propoziţia p ↔ q este adevărată atunci şi numai atunci când p şi q sunt în acelaşi timp adevărate sau false.

v(p) 0 0 1 1

v(q) v(p→q) 0 1 0 1

v(q→p) v(p↔q)

1 1 0 1

1 0 1 1

1 0 0 1

Formule echivalente în calculul propoziţional 3

www.cartiaz.ro – Carti si articole online gratuite de la A la Z

Cu operaţiile anterioare se pot construi diverse expresii numite formule ale calculului propoziţional (notate cu a,b...). O formulă a(p,q,r, ...) care are valoarea o propoziţie adevărată indiferent cum sunt propoziţiile p, q, r, ... se numeşte formulă identic adevărată sau tautologie.

Proprietăţi: 1) pV(qΛr) ↔ (pVq)Λ (pVq) 2) pΛ (qVr) ↔ (pΛq)V(pΛr) 3) p ↔ !(!p) 4) ! (pVq) ↔ !p Λ !q 5) ! (pΛq) ↔ !p V !q 6) p →q ↔ !p → !q 7) pVq ↔ qVp 8) pΛq ↔ qΛp

distributivitaţi negarea negaţiei legile lui De Morgan principiul reducerii la absurd comutativităţi

1.2. Elemente de algebră booleană Elementele pe care le vom prezenta în cele ce urmează sunt strict necesare pentru a putea explica, în capitolele următoare, principiile funcţionării calculatoarelor. Ne vom mărgini doar la prezentarea elementelelor de strictă necesitate, fără a intra în detalii referitoare la calculul propoziţiilor, formele normale etc. 1.2.1. Mulţimea B2, operaţii Unul dintre capitolele importante ale logicii matematice este calculul propoziţiilor, având ca principale operaţii negarea propoziţiilor, conjuncţia propoziţiilor şi disjuncţia propoziţiilor. Valoarea de adevăr a unei propoziţii este notată cu "1", iar valoarea de fals cu "0", simbolurile "1" şi "0" fiind aici simboluri fără înţeles numeric. Mulţimea formată din elementele 0 şi 1, cu operaţiile + şi ⋅ definite în clasa de resturi modulo 2, formează un inel. După cum se va vedea, mulţimea formată din elementele 0 şi 1 are extrem de multe aplicaţii în informatică. 4

www.cartiaz.ro – Carti si articole online gratuite de la A la Z

Fie mulţimea B2 = {0,1}. Peste această mulţime se definesc mai multe operaţii. DEFINIŢIA 1.3. Operaţia binară notată ∨, definită prin tabelul 1.1. se numeşte disjuncţie ∨

0

1

0 1

0 1

1 1

Tabelul 1.1. Definirea operaţiei ∨ DEFINIŢIA 1.4. Operaţia binară notată ∧ sau ⋅, definită prin tabelul 3.2. se numeşte conjuncţie. ∧

0

1

0 1

0 0

0 1

Tabelul 1.2. Definirea operaţiei ∧ DEFINIŢIA 1.5. Operaţia unară notată ! definită prin tabelul 3.3. se numeşte negaţie. x

!x

0 1

1 0

Tabelul 1.3. Operaţia ! În ordinea priorităţilor, aceste operaţii se succed astfel: !, ⋅, ∨ (negaţia, conjuncţia, disjuncţia). În continuare vor fi prezentate principalele proprietăţi ale acestor operaţii. Ele pot fi demonstrate uşor, folosindu-se tabelele de adevăr. TEOREMA 3.1. Următoarele 10 grupuri de proprietăţi sunt adevărate: 5

www.cartiaz.ro – Carti si articole online gratuite de la A la Z

1. a ⋅(b ⋅ c) = (a ⋅ b) ⋅ c 2. a ⋅(b∨c) = a ⋅ b∨a ⋅ c 3. a ⋅ a = a 4. a ⋅ b = b ⋅ a 5. a ⋅ (a∨b) = a 6. ! ! a = a 7. ! (a ⋅ b) = !a ∨ !b 8. a ⋅ 0 = 0 9. a ⋅ 1 = a 10. a ⋅ !a = 0

a∨(b∨c) = (a∨b)∨c a∨b⋅c = (a∨b)⋅(a∨c) a∨a = a a∨b = b∨a a∨a ⋅ b = a ! (a∨b) = !a ⋅ !b a∨0 = a a∨1 = 1 a∨!a = 1

(Asociativităţi) (Distributivităţi) (Idempotenţe) (Comutativităţi) (Absorbţii) (Dubla negaţie) (Legile lui De Morgan)

DEFINIŢIA 1.6. Structura algebrică (B2, ∨, ⋅, !) formează o algebră booleană DEFINIŢIA 1.7. Operaţia binară notată ⊕, definită prin tabelul 1.4. se numeşte suma modulo 2 sau sau-exclusiv.

⊕

0

1

0 1

0 1

1 0

Tabelul 1.4. Definirea operaţiei ⊕ TEOREMA 1.2. Structura algebrică (B2, ⊕, ⋅) formează un inel comutativ cu element unitate. Acest inel poartă numele de inel boolean.1 1.2.2. Funcţii booleene şi reprezentări ale lor Vom nota prin B2n produsul cartezian al mulţimii B2 cu ea însăşi de n ori. Deci B2n = B2×B2×...×B2. DEFINIŢIA 1.8. O funcţie f : B2n --- > B2 se numeşte funcţie booleană. Un n-uplu x = (x1, x2, ..., xn) ∈ B2n va fi numit punct din B2n. Prin f(x) = 6

www.cartiaz.ro – Carti si articole online gratuite de la A la Z

f(x1,x2,...,xn) vom înţelege valoarea funcţiei în punctul x. Este uşor de văzut că în B2n sunt 2n puncte. Deci, pentru a reprezenta o funcţie booleană este necesară construcţia tabelului cu valorile funcţiei în fiecare dintre aceste puncte. Un astfel de tabel va avea 2n linii şi n+1 coloane, ca în tabelul 1.5. x1

x2

...

xn-1

xn

f(x)

0

0

...

0

0

y0

0

0

...

0

1

y1

0

0

...

1

0

y2

0

0

...

1

1

y3

...

...

...

...

...

...

1

1

...

1

0

y2n-2

1

1

...

1

1

y2n-1

Tabelul 1.5. Definirea unei funcţii Booleene de n variabile Prin yi ∈ B2, i ∈ {0, 1, ... , 2n-1 } am notat valorile funcţiei f în toate punctele din B2n. De exemplu, se poate defini astfel funcţia booleană de trei variabile din tabelul 1.6. a

B

c

f(a,b,c)

0

0

0

0

0 0

0 1

1 0

0 1

0 1

1 0

1 0

1 0

1 1

0 1

1 0

0 1 7

www.cartiaz.ro – Carti si articole online gratuite de la A la Z

1

1

1

0

Tabelul 1.6. O funcţie Booleană de 3 variabile Pe lângă reprezentarea prin tabel, funcţiile booleene pot fi reprezentate şi cu ajutorul expresiilor booleene. În aceste expresii sunt folosiţi operatorii: !, ⋅ şi ∨. Operanzii sunt formaţi din variabilele funcţiei şi eventual din simbolurile 0 şi 1 având rolul de constante. Pentru schimbarea ordinii de efectuare a operaţiilor se folosesc parantezele ( şi ). În continuare vom da trei reguli după care se poate construi o expresie ce defineşte o funcţie booleană dată prin tabelul ei de valori. R1. Pentru fiecare linie din tabel pentru care yi=1 se va construi un termen conjunctiv în conformitate cu regula R2. Termenii conjunctivi se vor lega între ei prin operatori de disjuncţie. R2. La un termen conjunctiv participă cele n variabile, în conformitate cu regula R3. Acestea variabile sunt legate între ele prin operatori de conjuncţie. R3. Dacă valoarea unei variabile în linia i este 1 atunci în termenul conjunctiv apare variabila; dacă valoarea ei este 0, atunci în termenul conjunctiv apare negaţia variabilei respective. Urmând aceste reguli, funcţia de trei variabile dată ca exemplu în tabelul 1.6 va fi definită astfel: f : B23 → B2

f(a,b,c) = !a ⋅ b ⋅!c ∨ !a ⋅ b ⋅ c ∨ a ⋅ b ⋅!c

Cei trei termeni conjunctivi corespund liniilor y2, y3 şi y6. Valorile celor trei variabile în aceste linii sunt respectiv 010, 011 şi 110. Aplicând cele trei reguli, se obţine formula de mai sus. După cum este cunoscut din calculul propoziţiilor, o funcţie booleană 8

www.cartiaz.ro – Carti si articole online gratuite de la A la Z

poate avea mai multe reprezentări prin expresii. Acelaşi calcul al propoziţiilor defineşte diverse forme normale şi descrie metode de simplificare a expresiilor care reprezintă funcţii booleene. Obţinerea unei expresii prin regulile R1-R3 de mai sus conduce la forma normală disjunctivă perfectă.

9

CAPITOLUL 2. SISTEME ŞI BAZE DE NUMERAŢIE Numim sistem de numeraţie totalitatea regulilor folosite pentru scrierea numerelor, cu ajutorul unor simboluri numite cifre. În decursul istoriei s-au impus mai multe sisteme de numeraţie. 2.1. Tipuri de sisteme de numeraţie Cel mai primitiv mod de reprezentare a numerelor este răbojul. Pe un băţ numit răboj, omul primitiv cresta câte o linie pentru fiecare obiect sau animal care-i aparţinea (blănuri, oi etc.). Tot pe un astfel de răboj se marcau datoriile unui gospodar faţă de altul (de unde şi cunoscuta expresie "am scris pe răboj"). S-a constatat că acest mod de scriere a numerelor este deosebit de incomod. Pentru numere mari trebuie folosite multe semne, eventual trebuie folosite semne diferite pentru numere mai deosebite (10, 50, 100 etc.). Aceste semne se combină în diferite moduri. După felul de grupare şi ordonare a semnelor se deosebesc două sisteme de numeraţie: sistemul aditiv şi sistemul poziţional. 2.1.1. Sistemul de numeraţie aditiv (roman) Sistemul de numeraţie roman foloseşte pentru scrierea numerelor cifrele: I, V, X, L, C, D, M care corespund valorilor: unu, cinci, zece, cincizeci, o sută, cinci sute, respectiv o mie. Trei reguli importante guvernează acest sistem de numeraţie: Regula 1. Mai multe cifre de aceeaşi valoare, scrise consecutiv, reprezintă suma acestor cifre. De exemplu: XXX = 30; II = 2; MM = 2000.

Regula 2. O pereche de cifre de valori diferite, în care cifra de valoare mai mare se află în faţa cifrei de valoare mai mică reprezintă, 9

de asemenea, suma acestor cifre. De exemplu:

XI = 10+1 = 11; VI = 5+1 = 6.

Regula 3. O pereche de cifre de valori diferite, în care cifra de valoare mai mică se află în faţa cifrei de valoare mai mare reprezintă diferenţa acestor cifre. De exemplu: IX = 10-1 = 9;

IC = 100-1 = 99.

Sistemul de numeraţie roman prezintă dezavantajul unei scrieri greoaie şi a lipsei unei reprezentări unice a numerelor. Astfel avem: 49 = IL = LIC Alte neajunsuri ale acestui mod de scriere: numerele mari sunt în general lungi şi adesea de necuprins cu privirea, iar operaţiile aritmetice cu aceste semne sunt foarte anevoioase. 2.1.2. Sistemul de numeraţie poziţional (arab) Acest sistem a fost introdus de către indieni şi chinezi şi a fost preluat de către europeni datorită arabilor. El este un sistem poziţional, în care aportul unei cifre în stabilirea valorii numărului depinde atât de valoarea ei cât şi de poziţia pe care o ocupă în scrierea numărului. Această caracteristică asigură superioritatea sistemului de numeraţie arab faţă de sistemul de numeraţie roman. În scrierea arabă, fiecare grup de 10 elemente numărate (unităţi) formează o grupă de rang superior (zeci), 10 grupe de zeci formează o grupă de rang superior grupei zeci (sute) ş.a.m.d., conform celor cunoscute de elevi încă din clasa I primară. Datorită faptului că numărul zece este pragul de trecere la un rang superior, se spune că este folosită baza de numeraţie 10. Pentru scrierea în baza 10 sunt folosite cifrele: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 În secţiunile următoare vom dezvolta acest sistem de numeraţie folosind nu numai baza 10, ci şi alte baze de numeraţie.

10

2.2. Sisteme poziţionale de numeraţie în diverse baze 2.2.1. Reprezentarea numerelor naturale într-o bază b Fie b ∈ N, b > 1 un număr numit bază de numeraţie. Întreaga teorie aritmetică a reprezentării numerelor în baza b este fundamentată pe teorema care urmează. TEOREMA 2.1. Pentru orice număr natural nenul x, există în mod unic un număr natural n numit rang şi n+1 numere naturale c0, c1, ... cn numite cifre în baza b, care satisfac relaţiile: 1) x = cnbn + cn-1bn-1 +...+ c1b + c0, 2) ci ∈ { 0, 1, ... , b-1 }, ∀ i ∈ { 0, 1, ..., n } 3) cn ≠ 0. Demonstraţie: Deoarece x ≥ 1, iar b > 1, rezultă că există, în mod unic, un număr natural n pentru care este verificată dubla inegalitate (axioma lui Arhimede): bn ≤ x < bn+1 Acest număr n este cel din enunţul teoremei. În continuare, vom aplica inducţia completă după n. Pentru n = 0, avem chiar c0 = x şi alegerea este unică. Presupunem teorema adevărată pentru n şi să demonstrăm că rămâne valabilă şi pentru n+1. Scriind teorema împărţirii cu rest, unde deîmpărţitul este x şi împărţitorul este b, rezultă: x = y⋅b + r, cu 0 ≤ r < b Vom pune acum c0 = r, care este determinat în mod unic. Dacă bn+1 ≤ x < bn+2, rezultă că bn ≤ y < bn+1. Pentru y este valabilă ipoteza de inducţie, deci pentru el există n+1 cifre, pe care le vom nota c1, c2, ..., cn+1 şi care sunt de asemenea unic determinate. Rezultă că avem: x = cn+1bn+1 + cnbn +...+ c1b + c0 11

şi că sunt verificate celelalte două relaţii din teoremă. Cu aceasta, teorema este complet demonstrată. Să ataşăm acum fiecărui număr din mulţimea { 0, 1, ..., b-1 } câte un simbol (caracter, semn etc.) în aşa fel, încât la numere diferite să ataşăm simboluri diferite. Convenim, de asemenea, că atunci când ne referim la o cifră ci, să-i scriem de fapt simbolul Ci asociat numărului ci. Cu aceste convenţii (şi cu ipoteza că simbolurile "(" şi ")" nu reprezintă cifre, avem reprezentarea numărului x în baza b: (CmCm-1...C1C0)b În tot ceea ce urmează, vom identifica cifrele ci din teoremă cu simbolurile ataşate lor Ci (şi le vom scrie tot ci). Observaţie: Din definiţia dată reprezentării unui număr într-un sistem de numeraţie poziţional cu baza b, rezultă că o cifră indică o valoare de b ori mai mare decât aceeaşi cifră situată într-o poziţie de rang mai mic cu o unitate. Din acest motiv sistemele de numeraţie poziţionale mai sunt numite sisteme ponderate. În sistemul de numeraţie cu baza 10, numit sistem zecimal, sunt folosite simbolurile de cifre: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 Acest sistem este utilizat pe scară largă în prelucrarea manuală a datelor, precum şi în comunicarea cu un sistem de calcul. Sistemul de numeraţie cu baza doi, numit sistem binar, foloseşte numai cifrele 0 şi 1. El stă la baza construcţiei sistemelor de calcul. Sistemul de numeraţie cu baza 16, numit sistem hexazecimal foloseşte cifrele: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F ultimele şase simboluri, de fapt primele şase litere ale alfabetului, scrise fie cu majuscule fie cu minuscule, desemnează numerele 10, 11, 12, 13, 14 şi 15 ca cifre în baza 16. Din raţiuni de scriere comodă, şi pentru evitarea unor confuzii, simbolurile de cifre dintr-o anumită bază sunt preluate în bazele de numeraţie superioare. Astfel, în orice bază de numeraţie cu b ≤ 16 se folosesc simbolurile indicate mai sus, fiecare simbol indicând acelaşi număr, indiferent de bază. De exemplu, în baza 7 se folosesc simbolurile 0 ÷ 6, iar 12

în baza 13 se folosesc simbolurile 0 ÷ 9, A ÷ C; simbolul B este cifră doar începând cu baza 12 şi reprezintă cifra care are valoarea 11. Este momentul să precizăm că sunt folosite şi alte reprezentări ale cifrelor decât cea prin simboluri grafice. Această afirmaţie este, aparent, neobişnuită, deoarece majoritatea covârşitoare a populaţiei nu cunoaşte alt sistem de numeraţie decât cel zecimal! Dar, spre exemplu, atunci când se foloseşte calculatorul pentru lucrul cu baze de numeraţie foarte mari, fiecare cifră este reprezentată prin conţinutul unui cuvânt din memoria calculatorului. 2.2.2. Reprezentarea numerelor reale într-o bază b Definiţia dată reprezentării numerelor naturale poate fi extinsă şi la numerele reale. Fie x > 0 un număr real. DEFINIŢIA 2.1. Reprezentarea unui număr real x > 0 în baza b este (şi se scrie): x = (cncn-1...c1c0,c-1c-2c-3...)b dacă sunt îndeplinite condiţiile: 1) 2) 3) 4)

x = cnbn+cn-1bn-1+...+c1b+c0+c-1b-1+c-2b-2+c-3b-3... ci ∈ {0,1,...,b-1} , ∀ i ∈ {n,...,1,0,-1,-2,-3,...} cn ≠ 0 ∀ k≤ 0 ∃ j < k astfel, încât cj < b-1

Comparând definiţia dată reprezentării numerelor reale cu cea dată reprezentării numerelor întregi, se observă că la numerele reale avem în plus condiţia 4). Această condiţie cere să nu existe un rang la partea fracţionară după care toate cifrele reprezentării să fie egale cu b-1. Ea este necesară pentru a asigura unicitatea reprezentării numerelor. Drept contraexemplu, considerăm egalităţile: 1/2 = 0,5 = 0,499999… numerele fiind scrise în baza 10.

Are loc următoarea: TEOREMA 2.2. Fiind dată o bază de numeraţie b, pentru orice număr real x > 0 există o reprezentare unică în baza b conform definiţiei 4.1. Numărul: 13

(cncn-1...c1c0)b reprezintă, în baza b, partea iintreagă a numărului x, iar numărul (0,c-1c-2c-3...)b reprezintă, în baza b, partea fracţionară a numărului x. DEFINITIA 2.2 Reprezentarea unui număr real x în baza b (extinderea definiţiei 4.1 la toate numerele reale). a) Dacă x > 0, atunci numărul se reprezintă conform def. 2.1. b) Dacă x = 0, atunci x se reprezintă 0. c) Dacă x < 0, atunci se pune mai întâi semnul -, după care urmează reprezentarea numărului -x, conform definiţiei 2.1.

2.2.3. Conversii între baze de numeraţie Existenţa şi utilizarea mai multor baze de numeraţie ridică problema conversiei dintr-o bază în alta. Pentru fixarea ideilor, să presupunem că numărul x este reprezentat într-o bază (baza veche) p şi se doreşte conversia lui într-o bază (baza nouă) q. Cele mai cunoscute metode de conversie sunt: a) Metoda împărţirii la bază a numerelor întregi, cu calcule în baza p (baza veche); b) Metoda înmulţirii cu baza a părţilor fracţionare, cu calcule în bază p (baza veche); c) Metoda substituţiei, cu calcule în baza q (baza nouă).

2.2.3.1. Conversia întregilor prin împărţiri succesive Esenţa metodei este descrisă în demonstraţia teoremei 4.1 şi constă în faptul că cifra unităţilor unui număr natural x scris într-o anumită bază q coincide cu restul împărţirii lui x la q. Această metodă se aplică cu toate calculele efectuate în baza veche pentru a obţine reprezentarea lui x în noua bază q. Algoritmul de conversie este descris în figura 4.1., folosind un limbaj de tip pseudocod. În esenţă, se fac împărţiri succesive ale numărului x la q. Se 14

reţine de fiecare dată restul, iar câtul va deveni noul deîmpărţit. Resturile, luate în ordinea inversă a apariţiei, vor fi cifrele în noua bază q.

DATE x ( din N*, scris în baza p), q (noua bază) ; n := -1; d := x; CAT TIMP d > 0 EXECUTA n := n + 1; cn := d mod q; Cn := simbolul asociat cifrei cn în baza q; d := d div q; SF CAT TIMP ; REZULTATE Cn Cn-1 ... C1 C0 Figura 2.1 Conversia întregilor prin împărţiri succesive Exemple: Să considerăm numărul (985437)10 pe care vrem să-l reprezentăm pe rând în bazele 6 şi 16. Organizarea calculelor depinde de fantezia celui care face conversia. Noi vă propunem organizarea sub formă de tabel. Aşa cum am mai spus, toate calculele se fac în baza p, în cazul de faţă baza 10. Conversia în baza 6 este prezentată în tabelul 2.1. Citind ultima coloană din tabelul 2.1 de jos în sus, obţinem rezultatul conversiei: (985437)10 = (33042113)6 n

Deîmpărţit (baza 10)

Impărţitor (q) (baza 10)

Cât (baza 10)

Rest (cn) (baza 10)

Simbol cifră (Cn) (baza 6)

0 1 2 3 4 5 6 7

985437 164239 27373 4562 760 126 21 3

6 6 6 6 6 6 6 6

164239 27373 4562 760 126 21 3 0

3 1 1 2 4 0 3 3

3 1 1 2 4 0 3 3

Tabelul 2.1 Conversia unui număr în baza 6 15

Acum conversia în baza 16 este dată în tabelul 2.2.

n 0 1 2 3 4

Deîmpărţit (baza 10) 985437 61589 3849 240 15

Impărţitor (q) (baza 10) 16 16 16 16 16

Cât (baza 10)

Rest (cn) (baza 10)

Simbol cifră (Cn) (baza 16)

61589 3849 240 15 0

13 5 9 0 15

D 5 9 0 F

Tabelul 2.2 Conversia unui număr în baza 16 Citind ultima coloană de jos în sus, obţinem rezultatul conversiei: (985437)10 = (F095D)16 În fine, aplicăm aceeaşi metodă pentru a trece din baza 6 în baza 16, cu calculele făcute în baza 6. Tabelul 2.3 redă aceste calcule, toate numerele din tabel fiind în baza 6.

n 0 1 2 3 4

Deîmpărţit Impărţitor (baza 6) (q) (baza 6) 33042113 1153045 25453 1040 23

24 24 24 24 24

Cât (baza 6)

Rest (cn) (baza 6)

Simbol cifră (Cn) (baza 16)

1153045 25453 1040 23 0

21 5 13 0 23

D 5 9 0 F

Tabelul 2.3 Conversia din baza 6 în baza 16 Citind acum ultima coloană de jos în sus, obţinem rezultatul conversiei: (33042113)6 = (F095D)16 16

2.2.3.2. Conversia părţilor fracţionare prin înmulţiri succesive Ne interesează acum să găsim cifrele zecimale la trecerea dintr-o bază veche p într-o bază nouă q. Să notăm cu y partea fracţionară. După obţinerea cifrei c -1 = [ q ⋅ y ] în baza q, se aplică din nou metoda înlocuind pe y cu { q ⋅ y } ş.a.m.d. Acest algoritm este descris în figura 2.2. DATE y ( din (0,1), scris în baza p), q (noua bază) ; n := 0 ; f := y; CAT_TIMP (f > 0) sau (nu s-au obţinut suficiente cifre) sau (nu s-a obţinut perioadă: f nu coincide cu unul anterior) EXECUTA n := n - 1; cn := [ f ⋅ q ]; Cn := simbolul asociat cifrei cn în baza q; f := { f ⋅ q } SF_CATTIMP REZULTATE Cn Cn-1 ... C1 C0 Figura 2.2 Conversia părţii fracţionare prin înmulţiri succesive Prezentăm în continuare câteva exemple. Pentru simplificarea calculelor, presupunem că baza p este 10. Mai întâi, vom trece numărul (0,43359375) 10 în baza 8 (deci vom înmulţi mereu părţile fracţionare cu 8). 0 43359375 .8 3 46875 3 75 6 0 Rezultă că (0,43359375)10 = (0,336)8 şi s-au obţinut un număr finit de cifre la partea fracţionară. În continuare vom converti tot în baza 8 numărul 0,51437, dar vom reţine numai trei cifre după virgulă: 0

51437 ⋅8

17

4 0 7 -

11496 91968 35744 ----

Rezultă că (0,51437)10 = (0,407...)8. Să convertim acum, tot în baza 8, numărul (0,45)10. 0 45 3 4 6 3

60 8 4 2

1 4 6 3 1 -

6 8 4 2 6 --

⋅8

Rezultă că (0,45)10 = (0,346314631...)8. Se observă că se obţine o fracţie periodică mixtă, deci (0,45)10 = (0,3(4631))8. Să trecem acum numărul (0,85)10 în baza 16. 0 13 9 9 -

8 5 6 0 6 6 ---

⋅ 16

Rezultă că (0,85)10 = (0,D(9))16, unde D este simbolul cifrei cu valoarea (13)10. Observaţii: 1. Procesul de conversie se încheie fie când dat partea fracţionară devine zero, fie când se consideră că s-au extras suficiente cifre, fie când se 18

observă apariţia perioadei. Dacă conversia se face cu ajutorul calculatorului, depistarea perioadei este dificilă, motiv pentru care se foloseşte doar prima sau a doua condiţie de oprire. 2. Calculele se fac întotdeauna cu un număr finit de cifre după virgulă, indiferent dacă conversia se face manual sau cu ajutorul calculatorului. Din această cauză, teoretic întotdeauna apare perioada. Întradevăr, dacă se reţin k cifre după virgulă, după maximum bk încercări variabila f din algoritmul 4.2 se va repeta. 3. Din cauza observaţiilor de mai sus, o conversie dublă conduce la erori de trunchiere. Spre exemplu, să trecem numărul (0,6)10 în baza 8 şi să reţinem patru cifre. Avem că (0,6)10 = (0,4631...)8. Acum să aplicăm acelaşi algoritm pentru trecerea numărului (0,4631)8 în baza 10, cu calculele în baza 8. 0 4631 5 11 11 10

7772 7704 6650 422

⋅ (12)8 ; (11)8 = (9)10 ; (10)8 = (8)10

5 264 3 410 -- ----Rezultă că (0,4631)8 = (0,599853...)10. Aceasta înseamnă că în loc de (0,6)10, în urma dublei conversii, se obţine (0,599853...)10. 2.3. Relaţii între bazele 2, 8 şi 16 2.3.1. Cifre binare, octale, zecimale, hexazecimale În informatică, bazele 2, 8 şi 16 au o deosebită importanţă. După cum se va vedea imediat, conversiile între aceste baze se pot realiza deosebit de simplu. Ca terminologie, vom spune că lucrăm în sistemul binar dacă baza este 2, sistemul octal dacă baza este 8 şi sistemul hexazecimal dacă baza este 16. În acest context, este firesc să folosim termenul de sistem zecimal dacă baza este 10. Tabelul 2.4. conţine corespondenţa între cele patru reprezentări ale numerelor de la 0 la 15. Pentru o manevrare uşoară între aceste patru baze de numeraţie, recomandăm memorarea acestui tabel. 19

Zecim al

Binar

Octal

Hexa

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

0 1 2 3 4 5 6 7 10 11 12 13 14 15 16 17

0 1 2 3 4 5 6 7 8 9 A B C D E F

Tabelul 2.4. Corespondenţa între cifrele bazelor 10, 2, 8 şi 16. Orice grup de 3 cifre binare determină, în mod unic, o cifră octală; reciproc, o cifră octală se reprezintă în binar printr-un grup de 3 cifre binare, completând zerourile necesare la stânga. Un astfel de grup de 3 cifre binare îl numim triadă. Analog, orice grup de 4 cifre binare determină, în mod unic, o cifră hexazecimală; reciproc, o cifră hexazecimală se reprezintă în binar printr-un grup de 4 cifre binare, completând cu zerourile necesare la stânga. Un astfel de grup de 4 cifre binare îl vom numi tetradă. 2.3.2. Conversii binar - octal Să considerăm numărul x = (cncn-1...c1c0,c-1c-2c-3...c-k)2. Fără a restrânge generalitatea, presupunem că n+1 este multiplu de 3, iar k este de asemenea un multiplu de 3 (deci atât partea întreagă a numărului, cât şi partea fracţionară a lui au câte un număr de cifre multiplu de 3). Dacă nu este aşa, se adaugă, după necesităţi, zerouri înaintea lui cn, şi/sau după c-k. Aceste zerouri nu modifică valoarea numărului. Să scriem acum valoarea numărului x, grupând în triade cifrele din 20

stânga şi din dreapta virgulei zecimale şi să evidenţiem astfel câteva triade: X = cn⋅2n+cn-1⋅2n-1+cn-2⋅2n-2 + cn-3⋅2n-3+cn-4⋅2n-4+cn-5⋅2n-5 + ... +c5⋅25+c4⋅24+c3⋅23+c2⋅22+c1⋅2+ c0 + c-1⋅2-1+c-2⋅2-2+c-3⋅2-3 + ... + c-k+2⋅2-k+2+c-k+1⋅2k+1 +c-k⋅2-k = = (cn⋅22+cn-1⋅2+cn-2)⋅2n-2 + (cn-3⋅22+cn-4⋅2+cn-5)⋅2n-5 + ... + (c5⋅22+c4⋅2+c3)⋅23 + c2⋅22+c1⋅2+c + (c-1⋅22+c-2⋅2+c-3)⋅2-3 + ... + (c-k+2⋅22+c-k+1⋅2+c-k k)⋅2 Să notăm j=(n-2)/3 şi s= k/3. Se observă că numerele: n-2, n-5, ..., 3, 0, -3, ..., -k sunt multiplii lui 3 dintre -s⋅3 şi j ⋅3. Fiecare paranteză de forma: (cl+2⋅22+cl+1⋅2+cl), l ∈ {n-2, n-5, ..., 3, 0, -3, ..., -k} este un număr de trei cifre în baza 2, deci un număr între 0 şi 7. Altfel spus, o astfel de paranteză este o cifră în baza 8. Vom nota cu ri , cu i = l / 3 această cifră. Fiecare dintre puterile lui 2 care apar pe lângă cifrele ri cu aceşti exponenţi poate fi transformată astfel: 2l = 23⋅(l/3) = 8l/3 = 8i, unde l ∈ {n-2, n-5, ..., 3, 0, -3, ..., -k}, respectiv i ∈ {j, j-1, ..., 1, 0, -1, ..., -s} Cu aceste notaţii, avem: x = rj⋅8j + rj-1⋅8j-1 + ... + r1⋅8 + r0 + r-1⋅8-1 + ... + r-s⋅8-s deci x = (rj rj-1 ... r1 r0 ,r-1 r-2 r-3 ... r-s)8. Raţionând invers, dacă avem un număr scris în octal, reprezentarea lui binară se obţine păstrând virgula zecimală, iar spre stânga şi spre dreapta ei se înlocuieşte fiecare cifră octală cu triada corespunzătoare ei. 21

Sintetizând cele demonstrate mai sus, avem următoarele două reguli practice de trecere între bazele 2 şi 8: - Pentru trecerea din baza 2 în baza 8, se grupează cifrele reprezentării binare în triade, pornind de la virgulă spre stânga şi spre dreapta. Dacă cel mai din stânga grup al părţii întregi, respectiv cel mai din dreapta grup al părţii fracţionare, nu are exact trei cifre, se completează cu zerouri la stânga pentru partea întreagă, respectiv la dreapta pentru partea fracţionară. Se înlocuieşte fiecare triadă cu cifra octală corespunzătoare. - Pentru trecerea din baza 8 în baza 2, pornind de la virgulă, spre stânga şi spre dreapta, se înlocuieşte fiecare cifră octală cu triada binară corespunzătoare ei (fiecara cifră octală se va înlocui cu exact trei cifre binare!). Să considerăm câteva exemple: (100 101 110 , 111 011 001)2 = (456,731)8 (1001101011.0110100100101011)2 = (001 001 101 011.011 010 010 010 101 100)2 =(1153.322254)8 (11100111000001101)2 = (011 100 111 000 001 101)2 = (347015)8 (0,001000000111011011)2 = (000,001 000 000 111 011 011)2 = (0,100733)8 2.3.3. Conversii binar - hexazecimal Să considerăm numărul x = (cncn-1...c1c0,c-1c-2c-3...c-k)2. Fără a restrânge generalitatea, presupunem că n+1 este multiplu de 4, iar k este de asemenea un multiplu de 4 (deci atât partea întreagă a numărului, cât şi partea fracţionară a lui au câte un număr de cifre multiplu de 4). Dacă nu este aşa, se adaugă după necesităţi zerouri înaintea lui cn, şi/sau după c-k. Aceste zerouri nu modifică valoarea numărului. Analog conversiilor binar - octal, aici se scrie valoarea numărului x, grupând în tetrade spre stânga şi spre dreapta virgulei zecimale. Întreaga demonstraţie decurge analog celei prezentate în secţiunea precedentă, motiv pentru care nu o mai reluăm. Dăm numai două reguli practice de trecere între bazele 2 şi 16: - Pentru trecerea din baza 2 în baza 16, se grupează cifrele reprezentării binare în tetrade, pornind de la virgulă spre stânga şi spre dreapta. Dacă cel mai din stânga grup al părţii întregi, respectiv cel mai din dreapta grup al părţii fracţionare, nu are exact patru cifre, se completează cu zerouri la stânga 22

pentru partea întreagă, respectiv la dreapta pentru partea fracţionară. Se înlocuieşte fiecare tetradă cu cifra hexazecimală corespunzătoare. - Pentru trecerea din baza 16 în baza 2, pornind de la virgulă, spre stânga şi spre dreapta, se înlocuieşte fiecare cifră hexazecimală cu tetrada binară corespunzătoare ei (fiecara cifră hexazecimală se va înlocui cu exact patru cifre binare!). Să considerăm câteva exemple: (110100101010,00111101)2 =

(D2A,3D)16

( 1001101011.0110100100101011)2 = (0010 0110 1011,0110 1001 0010 1011)2 = =(26B,692B)16 ( 11100111000001101)2 = (0001 1100 1110 0000 1101)2 = (1CE0D)16 ( 0,001000000111011011)2 = =(0,2076C)16

(0000,0010

0000

0111

0110

1100)2

2.3.4 Conversii octal - hexazecimal Este evident că cel mai simplu mod de a face conversii între aceste două baze de numeraţie este acela al folosirii bazei 2 ca intermediar. Pentru a nu opera cu şiruri nesfârşite de cifre binare, facem următoarele recomandări: - Pentru trecerea din baza 8 în baza 16, se grupează la stânga şi dreapta virgulei, câte 4 cifre octale. Acestea vor fi transformate mai întâi în 12 cifre binare, care apoi vor fi transformate în 3 cifre hexazecimale. - Pentru trecerea din baza 16 în baza 8, se procedează analog, adică se grupează la stânga şi dreapta virgulei, câte 3 cifre hexazecimale. Acestea vor fi transformate mai întâi în 12 cifre binare, care apoi vor fi transformate în 4 cifre octale. De exemplu, (27354357,3576)8 = intermediare în baza 2 se pot organiza astfel:

(5DD8EF,77E)16.

Grupările

( 2735 4357, 3576 )8 = (010 111 011 101 100 011 101 111 , 011 101 111 110)2 = (0101 1101 1101 1000 1110 1111 , 0111 0111 1110 )2 = ( 5DD 8EF , 77E )16

23

CAPITOLUL 3. CODIFICAREA INFORMAŢIEI 3.1. Noţiunea de cod; exemple Codificarea a apărut din necesitatea de a se face schimb de mesaje care să poată fi înţelese numai de către persoanele care cunosc cheia codificării. Aceste schimburi de mesaje sunt necesare atunci când se manipulează informaţii secrete. În astfel de comunicaţii este esenţial mecanismul de codificare, care trebuie să fie suficient de complex încât să împiedice descifrarea lui de către persoane neautorizate sau rău intenţionate. Ca parte integrantă a prelucrării informaţiilor cu ajutorul calculatorului, codificarea urmăreşte transpunerea informaţiei din forma ei primară într-o formă accesibilă calculatorului. Mecanismul codificării trebuie să fie simplu, astfel încât să poată fi automatizat în mod eficient. 3.1.1. Definirea codului Trecând peste particularităţi şi diferenţe de exprimare, se poate crea un model matematic cuprinzător şi general al procesului de codificare. Să notăm prin: S = { s1, s2, ..., sp } mulţimea simbolurilor primare de informaţie. După caz, S poate fi mulţimea caracterelor ce se pot tipări, o mulţime de cuvinte dintr-un anumit limbaj sau limbă, o submulţime finită de numere etc. Să notăm prin: A = { a1, a2, ..., aq } un alfabet al codificării, în care elementele ai le vom numi litere. Cu ajutorul literelor alfabetului A, elementele mulţimii S vor fi reprezentate într-o nouă formă, forma codificată. Vom nota prin An mulţimea tuturor cuvintelor de lungime n formate cu litere din A. Deci An = { w  w = ai1ai2...ain / aij∈A, j = 1,n } Prin A+ vom nota mulţimea tuturor cuvintelor ce se pot forma cu litere din A. Deci 24

A+ = A ∪ A2 ∪ ... ∪ An ∪ ... DEFINIŢIA 3.1. O aplicaţie injectivă C : S → A+ se numeşte codificare a simbolurilor din S, sau mai simplu, cod. DEFINIŢIA 3.2. Un cod pentru care toate cuvintele de cod au aceeaşi lungime n se numeşte uniform, iar n se numeşte lungimea codului. În acest caz avem că C : S → An Codurile care nu sunt uniforme se numesc coduri neuniforme. 3.1.2. Exemple simple de coduri Să stabilim o corespondenţă între cifrele zecimale şi reprezentarea lor binară. În acest caz avem de-a face cu un cod uniform, în care: S = { 0, 1, ..., 9 }, A = B2 = { 0 , 1 }, n = 4 Codificarea prin funcţia de codificare C este cea cunoscută, adică: C(0) = 0000, C(1) = 0001, C(2) = 0010, ..., C(9) = 1001 Este binecunoscut alfabetul Morse. El este un cod pentru care S este mulţimea literelor mici, a cifrelor zecimale şi a unor semne speciale. Mulţimea A este formată din "." (punct); "-" (linie), care are ca lungime echivalentul a trei puncte; "pauza" care poate avea trei lungimi: lungime de un punct între două semne din A, de trei puncte între două semne din S, de cinci puncte între două cuvinte din S. Tabelul 3.1 defineşte funcţia C pentru alfabetul Morse. Mesajele în cod Morse sunt afişate de regulă pe o bandă îngustă şi continuă de hârtie. Până la apariţia mijloacelor moderne de comunicaţie, acest cod s-a folosit pe scară largă în telegrafie şi în transportul feroviar. Codul Morse a fost astfel conceput încât caracterele mai frecvente să aibă codificarea mai scurtă. Din punctul de vedere al modelului matematic, codul Morse este cod neuniform, deoarece cuvintele de codificat au lungimi cuprinse între 1 şi 6 litere din A. a

.-

n

-.

1

.----

ă

.-.-

o

---

2

..---

25

b

-...

ö

---.

3

...--

c

-.-.

p

.--.

4

....-

d

-..

q

--.-

5

.....

e

.

r

.-.

6

-....

f

..-.

s

...

7

--...

g

--.

ş

----

8

---..

h

....

t

-

9

----.

i

..

u

..-

0

-----

j

.---

ü

..--

.

......

k

-.-

v

...-

,

.-.-.-

l

.-..

w

.--

;

-.-....

m

--

x

-..-

:

---...

y

-.--

?

..--..

z

--..

!

--..--

Tabelul 3.1. Codificarea în alfabetul Morse 3.1.3. Problema decodificării Deoarece funcţia de codificare C este injectivă, rezultă că funcţia: C : S → C(S) ⊆ A+ este bijectivă. În acest caz problema decodificării se pune astfel: fiind dat un cuvânt w ∈ A+ să se determine si ∈ S astfel încât C(si) = w sau să se răspundă că nu există un astfel de si. Cu alte cuvinte, trebuie evaluată în w funcţia: C-1 : C(S) → S Pentru codurile uniforme, problema decodificării este simplă. În schimb, ea se complică la codurile neuniforme. O posibilă rezolvare a decodificării la codurile neuniforme constă în introducerea unui simbol consacrat ca element despărţitor între două secvenţe C(w1) şi C(w2) consecutive. Codul Morse foloseşte în acest scop "pauza" de diverse lungimi. Utilizarea unui astfel de 26

simbol determină creşterea numărului de litere cu care se codifică o succesiune de simboluri din S. Există coduri neuniforme pentru care decodificarea se poate face fără folosirea simbolurilor despărţitoare. Clasa acestor coduri este dată de definiţia care urmează.

DEFINIŢIA 3.3. Un cod C poartă numele de cod unic decodificabil dacă pentru orice două simboluri si şi sj din S, nici una dintre secvenţele de cod C(si) şi C(sj) nu este prefix pentru cealaltă. De exemplu, dacă unui simbol s1 îi atribuim codul a1a1a2, atunci nu mai putem avea, pentru alte caractere, secvenţele de cod a1, a1a1,a1a1a2a4 etc. . În tabelul 3.2 este redată o codificare unic decodificabilă pentru mulţimile S = { 0, 1, ..., 9 } şi A = { 1, 2, 3 } 0

1

2

3

4

5

6

7

8

9

11

12

212

222

31

321

322

211

3321

3312

Tabelul 3.2. Un cod unic decodificabil

3.2. Codificarea datelor în calculator 3.2.1. Codificarea caracterelor Fie S = { _, a, b, . . ., z, A, B, . . ., Z, 0, 1, . . ., 9, +, ., ;, :, $, . . .} mulţimea caracterelor tipăribile, existente la fiecare imprimantă, tastatură etc. Pentru codificarea acestor caractere în vederea prelucrării lor automate, standardele internaţionale impun o serie de restricţii. După cum se va vedea, aceste restricţii sunt benefice pentru prelucrarea automată a caracterelor. Să considerăm mulţimile: l mulţimea literelor mici ale alfabetului latin, L mulţimea literelor mari (în aceste mulţimi nu intră caracterele româneşti ă, â, î, ş, ţ), c mulţimea cifrelor zecimale, s mulţimea caracterelor speciale (spaţiul îl vom nota cu _), iar f mulţimea caracterelor funcţionale, cele care nu apar la tipărire (afişare), ci doar dirijează tipărirea (afişarea). Aşadar: 27

l = { a, b, ..., z }, L = { A, B, ..., Z }, c = { 0, 1, ..., 9 }, s = { _, +, ;, :, $, ... }, f = {CR, LF, TAB, FF, BEL, BS, . . . } În continuare, vom nota S = l ∪ L ∪ c ∪ s ∪ f. Înainte de a descrie condiţiile codificării, să prezentăm rolul câtorva dintre caracterele funţionale, simbolizate mai sus prin grupuri de litere mari. CR provoacă deplasarea dispozitivului de afişare (tipărire) la început de rând (Carriage Return). LF provoacă deplasarea dispozitivului cu un rând mai jos (Line Feed), păstrânduse poziţia în cadrul rândului. De obicei, se foloseşte succesiunea de caractere CR LF pentru a separa două linii de afişat, efectul lor cumulat fiind trecerea la începutul rândului următor. TAB este caracterul de tabulare, deci avansul dispozitivului la poziţia următorului stop de tabulare (de obicei peste 5-8 caractere). FF (Form Feed) provoacă trecerea la pagina (ecranul) următoare (următor). BEL provoacă emiterea unui semnal sonor, iar BS provoacă deplasarea dispozitivului de afişare (tipărire) cu o poziţie spre stânga, în vederea ştergerii (supraimprimării) ultimului caracter. Funcţia de codificare se defineşte astfel: C: S → [0,m] , unde m este 127 sau 255. Dacă considerăm reprezentarea binară, avem de-a face cu un cod uniform pe 7 biţi, respectiv pe 8 biţi. Având în vedere faptul că octetul este unitatea de adresare a memoriei, codul pe 7 biţi se extinde la 8 biţi punând 0 la bitul cel mai semnificativ. Deci codificarea unui caracter este un număr care încape pe un octet. 0 1 2 3 4 5 6 7 8 9 10 11

00 01 02 03 04 05 06 07 08 09 0A 0B

NUL SOH STX ETX EOT ENQ ACK BEL BS TAB LF VT

32 20 33 21 34 22 35 23 36 24 37 25 38 26 39 27 40 28 41 29 42 2A 43 2B

64 40 @ 65 41 A 66 42 B 67 43 C 68 44 D 69 45 E 70 46 F 71 47 G 72 48 H 73 49 I 74 4A J 75 4B K

! " # $ % & ' ( ) * + 28

96 60 ` 97 61 a 98 62 b 99 63 c 100 64 d 101 65 e 102 66 f 103 67 g 104 68 h 105 69 I 106 6A j 107 6B k

12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

0C 0D 0E 0F 10 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D 1E 1F

FF CR SO SI DLE DC1 DC2 DC3 DC4 NAK SYN ETB CAN EM SUB ESC FS GS RS US

44 2C 45 2D 46 2E 47 2F 48 30 49 31 50 32 51 33 52 34 53 35 54 36 55 37 56 38 57 39 58 3A 59 3B 60 3C 61 3D 62 3E 63 3F

, . / 0 1 2 3 4 5 6 7 8 9 : ; < = > ?

76 4C L 77 4D M 78 4E N 79 4F O 80 50 P 81 51 Q 82 52 R 83 53 S 84 54 T 85 55 U 86 56 V 87 57 W 88 58 X 89 59 Y 90 5A Z 91 5B [ 92 5C \ 93 5D ] 94 5E ^ 95 5F _

108 6C l 109 6D m 110 6E n 111 6F o 112 70 p 113 71 q 114 72 r 115 73 s 116 74 t 117 75 u 118 76 v 119 77 w 120 78 x 121 79 y 122 7A z 123 7B { 124 7C | 125 7D } 126 7E ~ 127 7F _

Tabelul 3.3 Codul ASCII Standardele de codificare a caracterelor impun următoarele 4 condiţii de definire a funcţiei C. 1. ∀ x ∈ f ==> C(x) < C('_') 2. ∀ x ∈ S \ f ==> C(x) ≥ C('_') 3. C('a') < C('b') < ... < C('z') C('A') < C('B') < ... < C('Z') C('1') = C('0')+1 ... C('9') = C('8')+1 4. Intervalele: [C('a') , C('z')], [C('A') , C('Z')], [C('0') , C('9')] şi mulţimea C(s) au intersecţiile vide două câte două. 128 80 Ç 129 81 ü

160 A0 á 161 A1 í

192 C0 193 C1 29

224 E0 α 225 E1 ß

130 82 é 131 83 â 132 84 ä 133 85 à 134 86 å 135 87 ç 136 88 ê 137 89 ë 138 8A è 139 8B ï 140 8C î 141 8D ì 142 8E Ä 143 8F Å 144 90 É 145 91 æ 146 92 Æ 147 93 ô 148 94 ö 149 95 ò 150 96 û 151 97 ù 152 98 _ 153 99 Ö 154 9A Ü 155 9B ¢ 156 9C £ 157 9D ¥ 158 9E _ 159 9F ƒ

162 A2 ó 163 A3 ú 164 A4 ñ 165 A5 Ñ 166 A6 ª 167 A7 º 168 A8 ¿ 169 A9 _ 170 AA ¬ 171 AB ½ 172 AC ¼ 173 AD ¡ 174 AE « 175 AF » 176 B0 177 B1 178 B2 179 B3 180 B4 181 B5 182 B6 183 B7 184 B8 185 B9 186 BA 187 BB 188 BC 189 BD 190 BE 191 BF

194 C2 195 C3 196 C4 197 C5 198 C6 199 C7 200 C8 201 C9 202 CA 203 CB 204 CC 205 CD 206 CE 207 CF 208 D0 209 D1 210 D2 211 D3 212 D4 213 D5 214 D6 215 D7 216 D8 217 D9 218 DA 219 DB 220 DC 221 DD 222 DE 223 DF

226 E2 Γ 227 E3 π 228 E4 Σ 229 E5 σ 230 E6 μ 231 E7 τ 232 E8 Φ 233 E9 Θ 234 EA Ω 235 EB δ 236 EC ∞ 237 ED φ 238 EE ε 239 EF ∩ 240 F0 ≡ 241 F1 ± 242 F2 ≥ 243 F3 ≤ 244 F4 ⌠ 245 F5 ⌡ 246 F6 ÷ 247 F7 ≈ 248 F8 ° 249 F9 ⋅ 250 FA ⋅ 251 FB √ 252 FC _ 253 FD ² 254 FE  255 FF Tabelul 3.4 Extinderea codului ASCII

Un prim sistem de codificare stabilit a fost EBCDIC (Extended Binary Decimal Interchange Code), care foloseşte pentru codificare numerele întregi din intervalul [0,255]. Calculatoarele medii-mari de tip IBM-360, IBM-370, precum şi FELIX-C folosesc codul EBCDIC. În prezent, cel mai folosit sistem de codificare este ASCII (American Standard Code for Information Interchange), care foloseşte pentru codificare numerele întregi din intervalul [0, 127]. 30

Faţă de condiţiile 1-4 de mai sus, acest standard de codificare mai verifică condiţia: 5. C('z') = C('a') + 25, C('Z') = c('A') + 25 Tabelul 3.3 conţine standardul ASCII. Fiecare coloană a tabelului conţine mai întâi numărul de cod în zecimal, apoi acelaşi număr în hexazecimal, urmate de simbolul din alfabet care se codifică. Corespunzător coloanei caracterelor funcţionale, se precizează şi simbolul pe care-l codifică maşinile IBM-PC, precum şi prescurtarea internaţională corespunzătoare caracterului funcţional codificat. Calculatoarele IBM-PC folosesc codificarea ASCII extinsă, folosind întregii din intervalul [0,255]. Dintre aceste numere, cele din intervalul [0,127] păstrează codificarea ASCII standard, iar celelalte coduri desemnează o serie de caractere noi. Tabelul 3.4 prezintă extinderea codificărilor pe intervalul [128,255].

31

CAPITOLUL

4.

Algoritmică şi programare

Rezolvarea unei probleme cu ajutorul calculatorului presupune parcurgerea următoarelor faze: 1) Precizarea completă a problemei de rezolvat (specificarea); 2) Proiectarea algoritmilor de rezolvare a problemei (proiectarea); 3) Programarea propriu-zisă a algoritmilor într-un limbaj de programare (codificarea); 4) Testarea şi verificarea (testarea); 5) Elaborarea documentaţiei de realizare şi a domentaţiei de exploatare (documentaţia); 6) Exploatarea şi întreţinerea programului (exploatarea). Toate aceste faze constituie ciclul de viaţă al programului sau al produsului program. Prin produs program se înţelege tot ceea ce se produce prin activităţile de mai sus. Nu detaliem mai mult fiecare din fazele anterioare, aceasta ar depăşi cadrul acestei cărţi. Ne vom axa mai mult pe fazele 1), 2) şi 3) pentru problemele didactice care le vom rezolva.

4.1. Algoritm Noţiunea de algoritm nu se poate defini foarte uşor. O definiţie matematică, riguroasă este greu de dat chiar şi cu ajutorul altor noţiuni. Vom încerca în continuare să descriem ce se înţelege prin algoritm. Prin algoritm vom înţelege un set finit de reguli – propoziţii scrise într-un limbaj de descriere a algoritmilor - care procesează, calculează, rezolvă o problemă. Mai în detaliu, pentru fiecare problemă P există date presupuse cunoscute (date iniţiale pentru algoritmul corespunzător, A) şi rezultate care se cer a fi găsite (date finale). Evident, s-ar putea ca problema să nu aibă sens pentru orice date iniţiale. Vom spune că datele pentru care problema P are sens fac parte din domeniul D al algoritmului A. Rezultatele obţinute fac parte dintr-un domeniu R, astfel că executând algoritmul A cu datele de intrare x∈D vom obţine rezultatele r∈R. Vom spune că A(x)=r şi astfel algoritmul A defineşte o funcţie: A : D  R Algoritmii au următoarele caracteristici: generalitate, finitudine şi generalitate. Prin generalitate se înţelege faptul că un algoritm este aplicabil pentru orice date iniţiale x. Deci un algoritm A nu rezolvă problema P numai cu anumite date de intrare particulare, ci o rezolvă în general, oricare ar fi aceste date din D. Astfel algoritmul lui Euclid de determinarea a 32

celui mai mare divizor comun al două numere naturale a şi b rezolvă problema pentru orice alegere a lui a şi b şi nu numai pentru, să zicem, a > b. Prin finitudine se înţelege că regulile algoritmului sunt în număr finit şi numărul transformărilor ce trebuie aplicate unei informaţii admisibile x∈D pentru a obţine rezultatul final corespunzător este finit. Deci rezulatele se obţin după un număr finit de transformări. Prin unicitate se înţelege că toate transformările prin care trece informaţia iniţială pentru a obţine rezultatul r∈R sunt bine determinate de regulile algorimului. Aceasta înseamnă că fiecare pas din execuţia algoritmului dă rezultate bine determinate şi precizează în mod unic pasul următor. Astfel spus, ori de câte ori am executa algoritmul, pornind de la aceeaşi informaţie admisibilă x∈D, transformările prin care se trece şi rezultatele obţinute sunt aceleaşi. În descrierea algoritmilor se folosesc mai multe limbaje de descriere, dintre care cele mai des folosite sunt: - schemele logice; - limbajul pseudocod. Ne vom referi în continuare la limbajul pseudocod.

4.2. Limbajul pseudocod Limbajul pseudocod este un limbaj inventat în scopul proiectării algoritmilor şi este format din propoziţii asemănătoare propoziţiilor limbii române, care corespund structurilor de calcul şi structurilor de control folosite în construirea algoritmilor. Limbajul pseudocod are două feluri de propoziţii: - propoziţii standard; - propoziţii nestandard. Deoarece realizarea unui algoritm pentru rezolvarea unei probleme nu este întotdeauna o problemă uşoară se vor obţine forme intermediare a algoritmului. În acest proces de rafinare se vor folosi pentru elementele nefinisate la un anumit nivel propoziţiile nestandard. Acestea sunt texte care descriu părţi ale algoritmului incomplet elaborate asupra cărora se va reveni la un alt nivel de detaliere. Începutul propoziţiilor nestandard se marchează printr-un semn special (# sau @ de exemplu) iar sfârşitul prin punct. Propoziţiile standard au sintaxă şi semantică bine precizate şi reflectă în algoritm structurile de calcul şi de control ale procesului de rezolvare a problemei. Pe langă aceste propoziţii se pot folosi şi comentarii scrise între acolade şi de obicei scrise pe linia propoziţiilor standard şi nestandard. 33

Pentru marcarea începutului foloseşte propoziţia standard: ALGORITMUL Sfârşitul standard:

unui

descrierii

numele_algoritmului

algoritm

se

marchează

unui

algoritm

se

ESTE: prin

propoziţia

SFÂRŞIT ALGORITM. Cele două propoziţii standard nu au decât semnificaţia delimitării descrierii unui algoritm de restul contextului în care apare. Pentru citirea datelor iniţiale, care se presupun că sunt cunoscute în problemă se folosesc propoziţiile standard: DATE listă; sau CITEŞTE listă; unde listă conţine toate numele variabilelor a căror valoare iniţială este cunoscută. Afişarea (tipărirea) sau precizarea rezultatelor obţinute se face cu ajutorul propoziţiilor standard: TIPĂREŞTE listă; sau REZULTATE listă; unde listă conţine toate variabilele ce doresc să fie afişate sau care s-au obţinut în urma procesului de calcul descris de algoritm. Calculele se descriu propoziţiei standard: [FIE]

prin

atribuiri

cu

ajutorul

variabilă := expresie;

unde expresie este de obicei o expresie de calcul (sau o variabilă) iar variabilă este o variabilă căruia i se atribuie rezultatul obţinut după efectuarea calculelor indicate în expresie. Structura de control de alternativă este de 3 tipuri: - alternativa simplă; - alternativa completă; - alternativa generalizată. Alternativa simplă se descrie prin propoziţia standard: DACĂ

condiţie

ATUNCI 34

S

SFÂRŞITDACĂ;

unde condiţie este de obicei o expresie relaţională sau logică iar S este un grup de propoziţii standard (poate fi şi doar o propoziţie standard). Execuţie: 1) Se evaluează condiţia; 2) Dacă condiţia este adevărată atunci se execută S şi se trece la propoziţia următoare; dacă condiţia nu este îndeplinită (falsă) atunci se trece automat la propoziţia următoare. Alternativa

completă DACĂ

se descrie prin propoziţia standard:

condiţie

ATUNCI ALTFEL

S1 S2

SFÂRŞITDACĂ Execuţie: 1) Se evaluează condiţia; 2) Dacă condiţia este adevărată atunci se execută S1 şi se trece la propoziţia următoare; dacă condiţia nu este adevărată (falsă) atunci se execută S2 şi se trece la propoziţia următoare. Alternativa generalizată se descrie prin propoziţia standard: SELECTEAZĂ i DINTRE V1 : S1; V2 : S2; . . . Vn : Sn SFÂRŞITSELECTEAZĂ Execuţie: 1) Dacă valoarea lui i este egală cu Vi atunci se execută secvenţa Si. 2) Se dă controlul propoziţiei de după SFÂRŞITSELECTEAZĂ. Structura de control repetitivă are trei forme: - repetiţia anterior testată (pretestată); - repetiţia posterior testată (posttestată); - repetiţia cu un număr determinat (şi aprioric cunoscut) de execuţii. Repetiţia pretestată se descrie prin propoziţia standard: CÂTTIMP condiţie EXECUTĂ S; SFÂRŞITCÂTTIMP; Execuţie: 1) Se evaluează condiţia; 2) Dacă condiţia este adevărată atunci se execută S şi se reia 35

evaluarea condiţiei; dacă condiţia nu este adevărată atunci se trece la propoziţia imediat următoare. În S trebuie modificată într-un fel oarecare condiţia, altfel ciclul ar deveni infinit dacă la prima evaluare condiţia ar fi adevărată. Repetiţia posttestată se descrie prin propoziţia standard: REPETĂ

S; PÂNĂCÂND condiţie; SFÂRŞITREPETĂ; Execuţie: 1) Se execută S; 2) Dacă condiţia este falsă se reia execuţia S; dacă condiţia este adevărată atunci se trece la propoziţia imediat următoare. În S trebuie modificată într-un fel oarecare condiţia, altfel ciclul ar deveni infinit dacă la prima evaluare condiţia ar fi falsă. Structura posttestată REPETĂ … de mai sus este echivalentă cu următoarea secvenţă: S; CÂTTIMP not condiţie EXECUTĂ S; SFÂRŞITCÂTTIMP;

Repetiţia predefinită, cu număr determinat de execuţii se descrie prin propoziţia standard: PENTRU contor:=liminiţială;limfinală[;pas] S; SFÂRŞITPENTRU

EXECUTĂ

Această structură este echivalentă cu secvenţa următoare:

limfinală

contor:=liminiţială; REPETĂ S; contor:=contor+pas; PÂNĂCÂND (contor > limfinală şi pas > 0) sau (contor < şi pas < 0) SFÂRŞITREPETĂ; 36

Execuţie: 1) Se iniţializează contorul cu liminiţială; 2) Se execută S; şi se incrementează contorul cu pas (dacă pasul este 1 nu este obligatoriu să fie pus în evidenţă, e implicit); 3) Se testează dacă contorul nu depăşeşte limita finală şi se reia punctul 2); dacă contorul depăşeşte limita finală atunci se trece controlul la propoziţia următoare. Exemple: 1) Să se determine dacă un număr natural, n este palindrom sau nu. Precizăm că un număr este palindrom dacă valoarea sa este egală cu valoarea oglinditului său (citit de la dreapta spre stânga). Algoritmul Palindrom Este: { Problema palindromului } Date n; x := n; { x variabilă internă de lucru egală la început cu n} m := 0; { în m se va construi oglinditul lui n} CatTimp x > 0 Executa c := x modulo 10; { în c se izolează ultima cifră a lui x, pas cu pas} m := m*10 + c; { se adaugă c la m} x := x div 10; { se imparte x la 10 şi se reţine câtul } Sfarsit CatTimp ; Daca m = n atunci Tipăreşte “numarul este palindrom” altfel Tipăreşte “numarul este palindrom” SfarsitDaca;

Sfarsit Algoritm

2) Să se determine cel mai lung platou dintr-un vector de numere întregi, ordonat crescător. Specificaţia problemei este: Intrare: n, a[i], i∈{0,1,...,n-1} Un platou este caracterizat de o pereche de indici (j,k) cu: 37

j≤k ∧ (a[j-1] a[k]≠a[k+p])

prima abordare Algoritmul platou Este: i:=1; scanare a tabloului a } lp:=1; platoului maxim } CatTimp i≤n-1 Executa # determină lp Sfarsit CatTimp Sfarsit Algoritm

{ Problema platoului } { i este indicele de {

lp conţine lungimea

{ propoziţie nestandard }

a doua rafinare Algoritmul platou Este: i:=1; scanare a tabloului a } lp:=1; platoului maxim } CatTimp i≤n-1 Executa Daca a[i-lp] ═ a[i] Sfarsit Daca; i:=i+1; Sfarsit CatTimp Sfarsit Algoritm.

4.3.

STRUCTURA 4.3.1.

GENERALĂ

ISTORIC,

{ Problema platoului } { i este indicele de {

Atunci

A

lp conţine lungimea

lp:=lp+1;

UNUI

CONCEPŢIE , 38

PROGRAM EVOLUŢIE

C

Limbajul C a fost finalizat în 1972 de Dennis M. Ritchie şi Brian W. Kernighan de la firma americană Bell Laboratories. Prima versiune a limbajului se numeşte BCPL apoi următoarele poartă numele de A, B şi C. Cei doi autori au dezvoltat aceste prime versiuni în jurul sistemului de operare UNIX. La vremea respectivă din aproximativ 13000 linii sursă ale UNIX-ului doar 200 de linii sursă nu erau scrise în limbajul C. De acest fapt se leagă detractorii limbajului care spun că limbajul C nu este un limbaj deosebit ci doar un fel de limbaj “oficial” al sistemului de operare UNIX. În anul 1978 apare manualul The C Programming Language care este de fapt şi prima standardizare a limbajului. Cei doi autori intră astfel în istorie... După anul 1980 odată cu dezvoltarea hardware apar şi primele PC-uri iar acestea implică şi produse software adecvate. Principalele firme producătoare de sofware MICROSOFT şi BORLAND - au dezvoltat unelte adecvate pentru programarea şi utilizarea limbajului C. Deocamdată firma BORLAND deţine supremaţia prin versiunile mediului BORLAND C. Cele mai folosite sunt versiunile 2.0, 3.1, 4.0. În ultimii doi ani au apărut aşa numitele medii “visuale”: VISUAL C versiunile 4.5 şi 5.0 care sunt de fapt extensii ale mediului BORLAND C adaptate programării orientate obiect şi interfeţei grafice WINDOWS 95. Mediile de programare BORLANDC pot compila 3 tipuri de programe sursă C: - fişiere cu extensia .C (fişiere cu programe standard C); - fişiere cu extensia .CP (fişiere cu programe C+, un C extins); - fişiere cu extensia .CPP (fişiere cu programe C+ +). Menţionăm că limbajul C++ a fost elaborat de Bjarne Stroustrup de la AT&T. El este un superset al limbajului C şi permite principalele concepte ale programării prin abstractizarea datelor şi programării orientate spre obiecte. Limbajul C este un limbaj hibrid având facilităţi caracteristice limbajelor de asamblare cât şi facilităţi ale limbajelor de înalt nivel. Câteva dintre principalele caracteristici ale limbajului C sunt: a) portabilitate: chiar dacă acest concept nu-i definit foarte riguros spunem că că un program este portabil dacă el poate fi transferat uşor de la un tip de calculator la altul; limbajul C este un astfel de limbaj; b) flexibilitate: compilatorul face un număr mai redus de controale (face multe 39

conversii implicite); b) programare structurată: limbajul are principalele structuri ale programării structurate: structura secvenţială, structuraiterativă structura de selecţie; d) compactizare: unele instrucţiuni sunt scrise foarte compact; de exemplu i:=i+1 se poate scrie mai scurt ca i++; e) lucrul pe biţi şi calcule cu adrese.

4.3.2.

CONCEPTUL

DE

FUNCŢIE

Un program C se compune din una sau mai multe funcţii. Funcţia este o unitate lexicală de program compilabilă independent. Una dintre funcţii este funcţie principală, numele ei este predefinit şi anume main. Execuţia programului începe cu prima instrucţiune din funcţia principală. Dăm în continuare 2 exemple de structuri de program (fişiere sursă): 1)

directive de preprocesare directive de preprocesare declaraţii declaraţii de date globale

implementare funcţia f1 . . . implementare funcia fn

2) de

date

declaraţie

prototip

funcţia .

declaraţie

prototip

void

void main(void) {

globale

{

declaraţii

.

funcţia

f1 . fn

main(void) declaraţii instrucţiuni

instrucţiuni

}

} implementare funcţia f1 . . . implementare funcţia fn Funcţia principală main este 40

obligatorie pentru orice

program celelalte elemente fiind optionale. Pentru ca o anumită funcţie să poată fi apelată e necesar ca ea să aibă declarat prototipul dacă implementarea (definiţia) ei se află după funcţia main (exemplul 1). Dacă funcţia principală se află la sfârşitul fişierului atunci nu mai e necesar prototipul funcţiei apelate ci doar implementarea ei (exemplul 2). Comparând structura unui program C cu structura unui program PASCAL se observă nivelul de imbricare diferit. În PASCAL apare o imbricare a procedurilor şi funcţiilor pe când în C nu există o astfel de imbricare (rămâne la nivelul fiecărei funcţii dacă e cazul). PASCAL C

...

4.3.2.1.

Definiţia

unei

funcţii

Definiţia unei funcţii în limbajul C se compune din antet şi corp. O funcţie poate fi apelată dacă este precedată de definiţia sau de prototipul ei. Aceste lucruri care sunt valabile în limbajul C se regăsesc şi în limbajul C++.

4.3.2.2. Antet

şi

prototip

Antetul simplificat al unei funcţii în C are formatul: tip

nume_funcţie (lista_parametrilor_formali)

unde: tip - reprezintă tipul valorii returnate de funcţie sau dacă funcţia nu returnează nici o valoare se pune cuvântul cheie void; nume_funcţie reprezintă un identificator clasic format dintr-un mixaj de litere şi cifre, primul caracter fiind obligatoriu litera; 41

printre litere se numără şi liniuţa de subliniere; lista_parametrilor_formali – nume de variabile separate prin virgule. Exemple: 1) double radical (double x) returneaza valoarea gasita

// calculeaza radacina patrata din x si

2) double radical_n (double x, int n) // calculeaza radacina de ordinul n din x

Prototipul unei funcţii este sfârşit se pune caracterul “;”

4.3.2.3.

asemănător

Corpul

unei

antetului

dar

la

funcţii

Corpul unei funcţii C se compune din declaraţii de variabile locale şi instrucţiuni scrise între acolade conform figurii de mai jos. { declaraţii instrucţiuni } Şi pentru că autorii limbajului C consideră că un limbaj de programare se învaţă mai repede scriind şi executând programe căt mai timpuriu vom da un mic exemplu de funcţie. int modul (int i) retruneaza aceasta valoare { if (i < 0) return –i; if (i = = 0) return 0; else return i; }

4.4. EXPRESII,

// determina valoarea absoluta a intregului i si

OPERANZI, 4.4.1.

OPERATORI EXPRESII

O expresie în limbajul C este formată fie dintr-un operand fie din mai mulţi operanzi legaţi între ei prin operatori. O expresie are o valoare şi un tip care se determină aplicând operatorii conform priorităţilor şi asociativităţii acestora. În limbajul C operatorii se asociază de la stânga la dreapta, exceptând operatorii unari şi de atribuire, care se asociază de la dreapta la stânga.. Totodată pot fi folosite parantezele rotunde pentru a impune o anumită ordine în executarea operaţiilor.

4.4.2. OPERANZI 42

Un operand în limbajul C poate fi una din următoarele elemente: - o constantă; - o constantă simbolică; - numele unei variabile simple; - numele unui tablou; - numele unei structuri; - numele unei funcţii; - referirea la elementul unui tablou (variabilă cu indici); - referirea la elementul unei structuri; - apelul unei funcţii; - o expresie inclusă în paranteze rotunde. Exemple:

9876

- constantă întreagă; x - variabilă simplă; t[i][3] -

variabilă cu indici; constantă hexazecimală; nume de tablou;

0xabcd

-

t

-

(expresie) expresie inclusă în paranteze rotunde. f1 numele unei funcţii

4.4.3.

-

OPERATORI

Operatorii limbajului C pot fi grupaţi în mai multe clase, dar oricum ei pot fi folosiţi împreună într-o aceeaşi expresie. Operatorii au arităţi diferite: unari, binari, ternari şi totodată o anumită prioritate implicită care e redată în tabelul de mai jos. Operatorii de aceeaşi prioritate se află trecuţi în aceeaşi linie. Liniile tabelulul conţin operatorii limbajului C în ordinea descrescătoare a priorităţilor. Astfel în prima linie se află operatorii de prioritate maximă, iar în ultima linie operatorul virgulă cu prioritatea cea mai mică. Cu excepţia operatorilor “.”, “>”,”&”,”*”, a parantezelor rotunde (folosite la definiţia şi apelul funcţiilor) şi a parantezelor drepte (folosite la variabilele cu indici) ceilalţi operatori vor fi explicaţi în această lecţie. ( ) [ ] . -> - (unar) +(unar) (tip) sizeof * / % + << >> < <= >= >

*(unar)

&(unar)

43

!

~

++ --

= = != & ^ | && | | ? : (ternar) = op= op poate fi: *(binar) (binar) << >> & ^ | ,

4.4.3.1.

/

%

Operatori

+(binar) –

aritmetici

Lista operatorilor aritmetici este redată mai jos: (minus unar); (plus unar); * / % operatori binari multiplicativi; (înmulţire, împărţire, restul împărţirii întregi); + - operatori binari aditivi (adunare şi scădere). +

Operatorii de pe aceeaşi linie au aceeaşi prioritate. Cei unari au prioritate mai mare decât cei binari. Operatorii multiplicativi au prioritate mai mare decât cei aditivi. Exemple: int i,j,k; float x,y; double t[10]; // se dau cateva exemple de expresii folosind operatorii aritmetici i*x+t[5]; -y+k; i%j; i/j; x*-y;

4.4.3.2.

// daca i=9 si j=4 atunci i%j are valoarea 1 // daca i=9 si j=4 atunci i/j are valoarea 2 // - este operatorul unar deci avem x*(-y)

Operatori

relaţionali

Lista operatorilor relaţionali este redată astfel: < (mai mic) <= (mai mic sau egal; cele două caractere ce operatorul sunt concatenate) > (mai mare) >= (mai mare sau egal; cele operatorul sunt concatenate)

două

caractere

ce

compun

compun

Toţi operatorii relaţionali au aceeaşi prioritate. Ea este mai mică decât prioritatea operatorilor aditivi. Rezultatul aplicării unui operator relaţional este 1 sau 0, după cum operanzii se află în relaţia definită de operatorul respectiv sau nu. 44

Exemple: atunci

a= 4 şi b= -5 a>0 a<=0 are a+b>0 a>=b are a<0 are a+b>=b-a are a+b>=(b-a)*(b-a)

4.4.3.3.

are valoarea 1; valoarea 0; are valoarea 0; valoarea 1; valoarea 0; valoarea 1; are valoarea 0;

Operatori

de

egalitate

Lista operatorilor de egalitate este redată mai jos: = = (egal; două semne “=” concatenate) != (diferit; semnele sunt concatenate). Operatorii de egalitate au ambii aceeaşi prioritate şi este imediat mai mică decât a operatorilor relaţionali. Operatorul “= =” testează egalitatea a doi operanzi. Dacă operanzii sunt egali atunci rezultatul operaţiei “= =” este 1, în caz contrar este 0. Operatorul “!=” furnizează rezultatul 1 când cei doi operanzi sunt diferiţi şi 0 când sunt egali. Exemple: a= 2 şi b=-1 atunci a= =b are valoarea 0; a!=b are valoarea 1; a*b!=a+b are valoarea 1;

4.4.3.4. ! && ||

Operatori

logici

Lista operatorilor logici este redată mai jos: (negaţia logică - operator unar); (ŞI logic); (SAU logic).

Operatorul “!” are aceeaşi prioritate cu operatorii unari “+” şi “-“. Operatorul “&&” este mai prioritar decât operatorul “||”, dar are o prioritate mai mică decât operatorii de egalitate. În limbajul C nu există valori logice speciale. Valoarea fals se reprezintă prin zero. Orice valoare diferită de zero reprezintă valoarea adevărat. Dacă operatorul “!” se aplică la un operand a cărui valoare este zero, atunci rezultatul este 1. Dacă acelaşi operator se aplică la un operand a cărui valoare este diferită de zero, atunci rezultatul este 0. Dăm în continuare tabelele operatorilor logici binari aplicate valorilor 0 şi 1. &&

0

1

|| 45

0

1

sau exclusiv 0

1

1

1

0 0

1

1

0

0

0

1

0

1

1

1

0

0

0

1

Chiar dacă pentru “sau exclusiv” nu există operator el se poate realiza prin expresia următoare aplicată operanzilor a şi b: !a&&b||!b&&a sau folosind parantezele rotunde ((!a) &&b)||((!b)&&a). Operatorii logici se evaluează de la stânga la dreapta. Dacă la evaluarea unei expresii se ajunge într-un punct în care se cunoaşte valoarea întregii expresii, atunci restul expresiei nu se mai evaluează. Dacă a=0 şi b=1 atunci expresia ! a||b are valoarea 1 pentru că !a are deja valoarea 1.

4.4.3.5.

Operatori

logici

pe

biţi

Lista operatorilor logici pe biţi este redată mai jos în ordinea descrecătoare a priorităţilor: ~ (operator unar; complement faţă de 1) >> << (deplasări la dreapta, respectiv la stânga) & (ŞI pe biţi) ^ (SAU-EXCLUSIV pe biţi) | (SAU pe biţi) Operatorul “~”, fiind unar, are aceeaşi prioritate ca şi ceilalţi operatori unari ai limbajului C. El schimbă fiecare bit 1 al operandului în 0 şi invers. Operatorul “>>” realizează deplasarea la dreapta care este echivalentă cu o împărţire întreagă cu puteri a lui 2; a >> 3 este echivalentă cu [a/23]. Operatorul “<<” realizează deplasarea la stânga care este echivalentă cu o înmulţire cu puteri a lui 2; a << 3 este echivalentă cu a*8. Pentru operatorii &, operaţiilor: ^

0

0

1

1

1

1

&

0

|,

1

^ dăm în continuare tabelele |

0

0

0

1

0

1

0

1

0

0

1

1

1

0

0 1

Observaţii: 1o. Operanzii care nu ocupă un cuvânt (16 biţi) se extind la un 46

cuvânt. De exemplu expresia ~0 are ca rezultat un cuvânt cu toţi biţi egali cu 1. 2o. Operatorii logici pe biţi se execută bit cu bit spre deosebire de operatorii logici care se evaluează global. De exemplu dacă x=2 i y=1 sunt variabile de tip int atunci: x&&y are valoarea 1 pentru că ambii operanzi sunt diferiţi de 0. x&y are valoarea 0 conform schemei de mai jos 0000 0000 0000 0010 0000 0000 0000 0001 & 0000 0000 0000 0000 3o. Operatorul & se foloseşte frecvent pentru a anula biţi din configuraţia unui cuvânt, iar operatorul | pentru a seta (pune) biţi într-un anumit mod; 4o. Operanzii trebuie să fie întregi (de tipul int sau long). 5o. Atenţie la deplasări nu se modifică valoarea operandului; deci trebuie să facem o atribuire; de exemplu a = a << 3 va modifica valoarea lui a pe când a << 3 nu modifică valoarea lui a. Exemple: 1) Fie declaraţia: int i; atunci expresia i >> 8 & 255 are ca rezultat valoarea celui mai semnificativ octet a lui i; i >> 8 deplasează octetul mai semnificativ al lui i în poziţia mai puţin semnificativă; se face apoi un ŞI logic pe biţi cu masca 255 care păstrează octetul mai puţin semnificativ. 2)

Fie expresia: (x >> 6) & ~(~ 0 << 3) Să presupunem că x are valoarea în biţi 1010 1011 1000 1101. Atunci x>>6 are valoarea 1111 1110 1010 1110 Al doilea operand pregăteşte o mască astfel: ~0 ~0<<3 ~(~0<<3)

1111 1111 1111 1111 1111 1111 1111 1000 0000 0000 0000 0110

Rezultatul final este dat de: 0000 0000 0000 0111 1111 1110 1010 1110 0000 0000 0000 0110 Practic s-a obţinut valoarea biţilor 8,7,6 a lui x (numerotaţi de la dreapta la stânga începând cu 0). 47

4.4.3.6.

Operatori

de

atribuire

În forma cea mai simplă operatorul de atribuire notează cu “=” şi se utilizează în construcţii de forma: v=expresie;

se

(v este fie o variabilă simplă, fie variabilă cu indici sau un element de structură). Această construcţie se mai numeşte expresie de atribuire. Ea este considerată ca fiind un caz particular de expresie. Tipul ei coincide cu tipul lui v, iar valoarea întregii expresii este chiar valoarea atribuită lui v. O expresie de forma:

v1=(v=expresie);

este şi ea legală şi se efectuează în felul următor : - se evaluează expresia expresie şi valoarea ei se atribuie lui v; - valoarea lui v se atribuie apoi şi lui v1. Deoarece operatorii de atribuire se asociază de la dreapta la stânga, expresia de mai sus se poate scrie şi fără paranteze: v1=v=expresie; În general, putem expresie de forma:

realiza

atribuiri

multiple

printr-o

vn =. . . =v1=v=expresie Dacă expresia din dreapta semnului egal are un tip diferit de cel al variabilei v, atunci întâi valoarea ei se converteşte spre tipul variabilei v şi pe urmă se realizează atribuirea, Pentru operaţia de atribuire, în afara semnului egal se mai poate folosi şi succesiunea : op= unde prin op se înţelege unul din operatorii binari aritmetici sau logici pe biţi, adică unul din următorii: % / * - + & ^ | << >> Acest mod de construcţie se foloseşte pentru a compacta un anumit tip de atribuire. Astfel expresia: v op = expresie; este identică cu expresia de atribuire: v = op expresie; Exemple: int i, j; double x, y; int v[10];

48

i=5; j=10; x=y=10.01; i +=1; x*=3; j<<=10; v[i]*=i x /= x-y

4.4.3.7.

// // // // //

echivalenta echivalenta echivalenta echivalenta echivalenta

Operatori

cu i=i+1 si cu i++ cu x=x*3 cu j=j<<10 cu v[i]=v[i]*i cu x = x/(x-y)

de

incrementare

şi

decrementare

Aceşti operatori sunt unari şi au aceeaşi prioritate cu ceilalţi operatori unari ai limbajului C. Operatorul de incrementare se notează prin “++” şi măreşte valoarea operandului cu unu, iar operatorul de decrementare se notează prin “- -“ şi micşorează valoarea operandului cu unu. Operatorii sunt folosiţi prefixat şi postfixat. Astfel operatorii prefixaţi au notaţia: ++operand; - - operand; Ei se aplică mai întâi şi apoi se foloseşte valoarea lor. Astfel operatorii postfixaţi au notaţia: operand++; operand - -; Se foloseşte valoarea operanzilor şi apoi se aplică incrementarea sau decrementarea. Menţionăm că aceşti operatori se pot aplica numai la următorii operanzi: - variabilă simplă; - variabilă cu indici; - referire la elementul unei structuri. Exemple: int i,j; double x,y; int vector [5]; j=i++; y=--x; i=++vector[j]

// este echivalent cu j=i si i=i+1; // este echivalent cu x=x-1 si y=x; // este echivalent cu vector[j]=vector[j]+1 si i=vector[j]

4.4.3.8. Operatorul de conversie explicită (expresie cast) Pentru forţarea tipului unui operand se foloseşte o construcţie de forma: (tip) operand Prin aceasta valoarea operandului se converteşte spre tipul indicat în paranteze. Exemplu: int i,j; double y; i=8; j=5; y=i/j;

// y are valoarea 1, pentru ca se face impartirea intreaga i/j

Dacă vom converti operanzii i şi j spre tipul double se va obţine rezultatul corect adică 1.6. 49

Deci: int i,j; double y; i=8; j=5; y=(double) i / (double) j;

// y are valoarea 1.6,

Construcţia (tip) este un operator unar prin care se explicitează conversia dorită. Are aceeaşi prioritate ca restul operatorilor unari.

4.4.3.9. Operatorul dimensiune (sizeof) Pentru a determina lungimea în octeţi a unei date se poate folosi construcţia: sizeof (data) unde data poate fi: - numele unei variabile simple; - numele unui tablou; - numele unei structuri; - numele unui tip; - referirea la elementul unui tablou sau structură. Exemple: int i; long l; float f; double d; char c; int itablou[5]; double dtablou[5]; sizeof (i) sizeof (l) sizeof (f) sizeof (d) sizeof (c) sizeof (itablou[1]) sizeof (dtablou[1]) sizeof (itablou) sizeof (dtablou)

// // // // // // // // //

are valoarea 2; are valoarea 4; are valoarea 4; are valoarea 8; are valoarea 1; are valoarea 2; are valoarea 8; are valoarea 10; are valoarea 40;

50

4.4.3.10. Regula conversiilor implicite În general o expresie C conţine operanzi de tipuri diferite. Pentru operatorii binari există situaţii când operanzii nu sunt de acelaşi tip şi trebuie executate conversii astfel încât operatorii să se aplice pentru operanzi de acelaşi tip. Aceste conversii le face automat compilatorul. Există o regulă a conversiilor implicite care are următorii paşi: - fiecare operand de tip char se converteşte spre tipul int şi fiecare operand de tipul float se converteşte spre double; - dacă unul dintre operanzi este de tip double atunci şi celălalt se converteşte spre tipul double şi rezultatul va avea tipul double; - dacă unul dintre operanzi este de tip long, atunci şi celălalt se converteşte spre tipul long şi rezultatul va avea tipul long; - dacă unul dintre operanzi este de tip unsigned, atunci şi celălalt se converteşte spre tipul unsigned şi rezultatul va fi de tipul unsigned; - la acest pas se ajunge numai dacă ambii operanzi sunt de tip int şi deci operaţia se execută cu operanzii respectivi, iar rezultatul va fi de tip int. Aplicând regula de mai sus pas cu pas (la fiecare operator în momentul efectuării lui), se ajunge în final la evaluarea întregii expresii şi prin acesta se determină tipul expresiei. Regula conversiilor implicite nu se aplică pentru operatorul de atribuire (valoarea expresiei din partea dreaptă a semnului de atribuire se converteşte spre tipul variabilei din stânga semnului egal). Exemple: int i, j, k; float a, b; double x, y; unsigned p; long r; char c;

expresii

conversii

i-j/k a/b

nu int a spre double b spre double double nu double a spre double i spre double double i spre double double nu int i spre double double c spre int int 10 spre double double 10 spre unsigned unsigned 5 spre long long se realizează împărţirea întreagă între i şi j şi rezultatul se converteşte spre double

x+y i+a i-3.14 i+3 i+x i-c x+10 p-10 r*5 (double)(i/j)

tipul expresiei

Dacă rezultatul unei operaţii depăşeşte domeniul de valori ce corespunde tipului rezultatului, valoarea respectivă se trunchiază şi rezultatul este eronat. 48

4.4.3.11. Operatori condiţionali Operatorii condiţionali sunt ? şi : şi se folosesc împreună în construcţii de forma: exp1 ? exp2 : exp3 Evaluarea se face astfel: - se evaluează expresia exp1; - dacă exp1 este diferită de zero, atunci valoarea şi tipul expresiei condiţionale sunt egale cu valoarea şi tipul expresiei exp2; altfel cu expresia exp3. Exemplu: procesul de determinare a maximului a două numere a şi b este: dacă a>b

atunci max=a altfel max=b

sfdacă În limbajul C se poate realiza acest proces cu ajutorul operatorilor condiţionali astfel: max= a>b ? a : b Dacă a>b atunci expresia condiţională are valoarea şi tipul lui a altfel expresia condiţională are valoarea şi tipul lui b.

4.4.3.12. Operatorul virgulă Operatorul “,” este folosit pentru gruparea mai multor expresii într-una singură. Cu ajutorul acestui operator (care are prioritatea cea mai mică) se construiesc expresii de forma: exp1, exp2,. . ., expn Această expresie are valoarea şi tipul ultimei expresii (deci a lui expn). Exemplu: k= (i=10, j=j+5; i+j) Se execută pe rând cele două atribuiri de la stânga la dreapta din parantezele rotunde apoi se face suma i+j şi în final se atribuie această sumă lui k.

4.5. INSTRUCŢIUNI 4.5.1.

SCURT

ISTORIC

AL

METODELOR

DE

PROGRAMARE

Vom prezenta în continuare câteva metode de programare dar nu exhaustiv, nefiind aici cadrul adecvat (eventual întrun curs de Software Engineering). O clasificare cronologică a ceea ce vrem să prezentăm ar fi următoarea: a) programarea artizanală; b) programarea procedurală; c) programarea modulară; d) programarea structurată; e) programarea prin abstractizarea datelor; 49

f) programarea

orientată spre obiecte.

4.5.1.1.

Programare

artizanală

Această metodă de fapt nu este o metodă propriu-zisă ci este prima modalitate de programare odată cu apariţia calculatoarelor. Intuiţia şi experienţa programatorului joacă un rol important. Fiecare programator îşi are propriile reguli de programare. Programele sunt monolitice (un singur corp de instrucţiuni), lungi şi greu de înţeles de alt programator. Însuşi cel ce a elaborat un astfel de program întâmpină dificultăţi de înţelegere a propriului program după un timp oarecare. 4.5.1.2.

Programare

procedurală

Odată cu apariţia primelor limbaje de înalt nivel se utilizează programarea procedurală. Necesitatea ca anumite secvenţe de program să fie folosite de mai multe ori duce la organizarea acestora în unităţi distincte de program numite în diverse limbaje subprograme, subrutine, proceduri, etc. De multe ori procedurile trebuie să fie generale deci procesarea să facă abstractizare de valorile datelor. De exemplu o procedură de calcul al radicalului de ordinul 2 trebuie să calculeze acest lucru din orice număr real pozitiv iar pentru cele negative să semnaleze eroare. Procedurile trebuie deci parametrizate cu anumite variabile numite parametri formali. Valorile de la apel ale parametrilor formali se numesc parametri efectivi. Programarea procedurală are la bază deci utilizarea procedurilor, iar acestea realizează o abstractizare prin parametri. La apelare o procedură funcţionează după principiul cutiei negre (black box): se cunosc intrările şi ieşirile rezultate din acestea dar nu şi modul de transformare care nu e important în acest moment. În majoritatea limbajelor procedurale de programare se consideră 2 categorii de proceduri: - proceduri care definesc o valoare de revenire (denumite şi funcţii); - proceduri care nu definesc o valoare de revenire. În limbajele C şi C++ procedurile de ambele categorii se numesc funcţii.

4.5.1.3.

Programarea

modulară

Pe măsură ce complexitatea aplicaţiilor a crescut, a apărut ideea de a descompune problemele în subprobleme mai 50

simple care la rândul lor pot fi descompuse în altele mai simple şi aşa mai departe. În felul acesta se ajunge la o descompunere arborescentă a problemei date în subprobleme mai simple. Programarea subproblemelor devine o problemă mai simplă şi fiecare subproblemă are o anumită independenţă faţă de celelalte subprobleme. De asemenea, interfaţa ei cu celelalte subprobleme este limitată şi bine precizată prin procesul de descompunere a problemei iniţiale. De obicei, programarea unei subprobleme, componentă a descompunerii arborescente a problemei iniţiale, conduce la realizarea unui număr relativ mic de proceduri (funcţii). Aceste funcţii pot prelucra în comun anumite date. Unele dintre ele sunt independente de funcţiile realizate pentru alte subprobleme componente ale descompunerii arborescente. Altele realizează chiar interfaţa cu subproblemele învecinate. Despre funcţiile obţinute în urma programării unei subprobleme se obişnuieşte să se spună că sunt înrudite. De obicei, aceste funcţii, împreună cu datele pe care le prelucrează, se păstrează într-un fişier şi se compilează independent. O colecţie de funcţii înrudite, împreună cu datele pe care le prelucrează în comun formează un modul. În felul acesta, problema iniţială se realizează printr-un program alcătuit din module. Programarea modulară are la bază elaborarea programelor pe module. O parte din datele utilizate în comun de funcţiile modulului, sau chiar toate datele modulului, nu sunt necesare şi în alte module. Aceste date pot fi protejate sau cum se mai spune, ascunse în modul. Limbajul C şi C++, permite ascunderea datelor în modul folosind date care au clasa de memorie static. Mai mult, pot fi declarate şi funcţiile ca statice şi atunci ele vor fi ascunse în modul (nu pot fi apelate din afara modului). Ascunderea funcţiilor în modul se face pentru acele funcţii care nu se utilizează la realizarea interfeţei modulului cu celelalte module. Ascunderea datelor şi funcţiilor în module permite protejarea datelor şi preîntâmpină utilizarea eronată a funcţiilor.

4.5.1.4.

Programarea

structurată

Descompunerea unei probleme în subprobleme mai simple se poate face succesiv în mai multe etape, până când subproblemele sunt direct programabile sub forma unor proceduri sau module. Această descompunere succesivă se mai numeşte rafinare pas cu pas (stepwise refinement).. Evident că se obţine o descompunere arborescentă. Procedurile se pot organiza sau nu în module. În cadrul procedurilor se folosesc anumite structuri de control a execuţiei. Aceasta impune o anumită disciplină a programării. Structurile de control de sunt: 51

a) secvenţa; b) iteraţia (pretestată, posttestată, cu număr prestabilit de ciclări); c) alternativa (simplă, completă, generalizată). Instrucţiunea de bază (primitivă) în cadrul acestor structuri de control este instrucţiunea de atribuire. Această abordare a programării s-a născut din necesitatea eliminării instrucţiunii de control GO TO care face saltul necondiţionat la o instrucţiune precizată, alta decât instrucţiunea următoare ei. Profesorul Dijsktra de la Universitatea din Eindhoven spunea, prin anul 1965, “calitatea unui programator este invers proporţională cu numărul de instrucţiuni GO TO folosite” şi a impus D-structurile de control: a) secvenţa; b) iteraţia pretestată; c) alternativa simplă. D-structurile se regăsesc în toate limbajele procedurale. Corespondenţa ar fi: a) secvenţa este echivalentă cu execuţia instrucţiunilor în ordinea scrierii lor în programul sursă; b) iteraţia pretestată echivalentă cu WHILE ... DO; c) alternativa simplă echivalentă cu IF ... THEN. O ilustrare grafică a celor trei D-structuri se dă în continuare.

S1 da C S

C

da nu

S2

S

nu

.

Sn

S-a demonstrat ulterior (Bohm şi Jacopini) că orice algoritm se poate descrie doar cu D-structurile dar pentru o mai bună lizibilitate şi înţelegere a programelor sursă s-au adăugat şi iteraţia postestată (REPEAT ... UNTIL), iteraţia cu număr prestabilit de ciclări (FOR ... DO), alternativa completă (IF ... THEN ... ELSE) şi alternativa generalizată (CASE ... OF). În unele limbaje se folosesc şi alte structuri pe lângă cele de mai sus pentru o cât mai fidelă reflectare a algoritmului.

4.5.1.5. 52

Programarea

prin

abstractizarea

datelor

În toate aceste tehnologii anterioare se urmăreşte mai mult organizarea programului şi mai puţin rezolvarea cât mai naturală a problemei. Programarea prin abstractizarea datelor şi programarea orientată spre obiecte propun metodologii în care conceptele deduse din analiza problemei să poată fi reflectate cât mai fidel în program şi să se poată manevra cu instanţieri ale acestor concepte cât mai natural. Se realizează o mai mare fidelitate a programului faţă de problemă. De exemplu dacă într-o problemă în care se procesează numere complexe e nevoie să se lucreze într-o formă cât mai apropiată cu forma matematică se poate introduce tipul COMPLEX (tip care nu există în limbajele de programare) şi apoi se pot declara variabile de acest tip. Mai mult ar trebui să se poată face toate operaţiile matematice asupra datelor de tip COMPLEX. În general un TAD (Tip Abstract de Date) are două componente fundamentale: datele membru (reflectă reprezentarea tipului); funcţiile membru (reflectă comportamentul tipului).

4.5.1.6.

Programarea

orientată

spre

obiecte

Un neajuns al programării prin abstractizarea datelor este faptul că nu permite exprimarea legăturilor dintre diferite concepte (TAD-uri). Singura legătură dintre concepte care se poate exprima, este aceea că datele membru ale unei clase pot fi obiecte ale unei alte clase. Acest lucru nu este suficient în cazul în care conceptele sunt strâns dependente între ele formând structuri ierarhice. Exprimarea ierarhiilor conduce la atribute suplimentare cum sunt cele de moştenire. Aceste atribute conduc la un nou model de programare pe care îl numim programare orientată obiect. În vârful unei ierarhii se află fenomenul sau forma de existenţă care are trăsături comune pentru toate celelalte componente ale ierarhiei respective. Pe nivelul următor al ierarhiei se află componentele care pe lângă trăsăturile comune de pe nivelul superior, mai au şi trăsături suplimentare, specifice. O ierarhie, de obicei, are mai multe nivele, iar situarea unui element pe un nivel sau altul al ierarhiei este uneori o problemă deosebit de complexă. Dăm în exemplul următor o ierarhie arborescentă pentru conceptele de paralelogram, dreptunghi, romb şi pătrat. Paral elogram

Romb

Dreptunghi

P 53

ătrat

Dacă paralelogramul se află în vârful ierarhiei atunci pe nivelul imediat inferior se aşează dreptunghiul (paralelogramul cu un unghi drept) dar şi rombul (paralelgramul cu 2 laturi alăturate congruente). Apoi pătratul se poate defini fie ca un dreptunghi cu laturile congruente fie ca un romb cu un unghi drept. Conceptul de pe fiecare nivel se observă că moşteneşte proprietăţile conceptului imediat superior din care este derivat. La ora actuală, toate ramurile cunoaşterii ştiinţfice sunt pline de ierarhii rezultate în urma clasificării cunoştinţelor acumulate în perioada lungă de observare a fenomenelor şi formelor de existenţă a lumii materiale şi spirituale. Clasificările ierarhice ale cunoştinţelor pot fi întâlnite atât în domeniile care pleacă de la cele mai concrete forme ale lumii materiale, cum sunt botanica, zoologia, biologia, etc cât şi în domenii care studiază concepte dintre cele mai abstracte, cum ar fi matematica sau filozofia. Aceste ierarhii sunt rezultatul definirii conceptelor după regula includerii “genul proxim şi diferenţa specifică”. Limbajul C dispune de un set bogat de instrucţiuni care permit scrierea de: - programe structurate, - programe flexibile, - programe compacte. Totodată limbajul C permite aplicarea metodelor de programare procedurală, programare modulară şi programare structurată. Pe lângă aceste metodologii limbajul C++ permite şi programarea prin abstractizarea datelor şi programarea orientată spre obiecte. Vom descrie în continuare instrucţiunile limbajului C. Ca o caracteristică sintactică toate instrucţiunile limbajului se termină prin caracterul “;”, excepţie făcând instrucţiunile care se termină cu acolada închisă.

4.5.2.

INSTRUCŢIUNEA VIDĂ

Instrucţiunea vidă se reduce la caracterul “;”. Ea nu are nici un efect. Adesea este nevoie de ea la construcţii în care se cere prezenţa unei instrucţiuni, dar nu este necesar să se execute nimic în punctul respectiv.

4.5.3.

INSTRUCŢIUNEA

EXPRESIE

Instrucţiunea expresie se obţine scriind punct şi virgulă după o expresie, deci: 54

expresie; Există cazuri particulare ale instrucţiunii expresie: 1) expresia de atribuire, care de altfel este cel mai important caz particular al instrucţiunii expresie: expresie; 2) apelul unei funcţii: nume_funcţie (par1, par2, . . . parn); 3) incrementările şi decrementările pre şi post fixate: variabilă++; ++variabilă; variabilă- -; - - variabilă; Exemplu: void main (void) { int i; float f; double d; i=10; // instructiune de atribuire i++; // i se mareste cu 1 f=i; // instructiune de atribuire (valoarea lui i se converteste in float) d=++f; // incrementare lui f si atribuirea valorii lui d putchar(‘a’); // instructiune de apel }

4.5.4.

INSTRUCŢIUNEA

COMPUSĂ

Instrucţiunea compusă este o succesiune de declaraţii urmate de instrucţiuni, succesiune inclusă între acolade: { declaraţii instrucţiuni } Pot lipsi declaraţiile sau instrucţiunle dar nu în acelaşi timp. Dacă delaraţiile sunt prezente, atunci ele definesc variabile care sunt valabile numai în instrucţiunea compusă respectivă. Exemplu: . . . { int i=100; // variabila i este definita in aceasta instructiune compusa i++; // i are valabilitate doar intre acolade; dupa acolada inchisa i isi printf (“i=%d\n”,i); // pierde valabilitatea } Observaţii: 1o. După acolada inchisă a unei instrucţiuni compuse nu se pune ”;”. 2o. Corpul unei funcţii are aceeaşi structură ca şi instrucţiunea compusă, deci o funcţie are formatul: 55

antetul funcţiei instrucţiune compusă

4.5.5.

INSTRUCŢIUNEA

if

Instrucţiunea if permite să realizăm o ramificare a execuţiei în funcţie de valoarea unei expresii. Ea are două formate ce permit aplicarea structurii de alternativă simplă şi compusă. Formatul 1: if (expresie) instructiune; Efectul: 1) se evaluează expresia din paranteze; 2) dacă valoarea expresiei este diferită de zero (deci conform convenţiei are valoarea adevărat), atunci se execută instructiune, altfel se trece la instrucţiunea următoare. Formatul 2:

if (expresie) else

instructiune_1; instructiune_2;

Efectul: 1) se evaluează expresia din paranteze; 2) dacă valoarea expresiei este diferită de zero (deci conform convenţiei are valoarea adevărat), atunci se execută instructiune_1, altfel se execută instructiune_2; apoi în ambele cazuri se trece la instrucţiunea următoare. Observaţii: 1o. Se pot folosi instrucţiuni if imbricate, nivelul de imbricare fiind oarecare (deci nu există o limitare a numărului de imbricări). 2o. Pentru mai multe imbricări se foloseşte regula asocierii if-lui cu else astfel: un else se pune în corespondenţă cu primul if care se află înaintea lui în textul sursă şi nu este inclus în instrucţiunea care îl precede pe el şi nici nu îi corespunde deja un else. Exemple void main (void) { float x,y,a; x=-5; y=10; if (x<0) if (y<0) else else a=0; 56

// ultimul else se asociaza cu primul if iar a=1; // penultimul else se asociaza cu cel de-al doilea if a=2;

} void main (void) { float x,y,a; x=-5; y=10; if (x<0) { if (y<0) a=1; } compusa care else a=0; }

// ultimul else se asociaza cu primul if deoarece cel de-al // de-al doilea if este inclus in instructiunea // il precede pe if

void main (void) // citeste trei intregi si scrie minimul dintre ei {int i,j,k,min; scanf (“\ndati i=%d”, &i); scanf (“\ndati j=%d”, &j); scanf (“\ndati k=%d”, &k); if (i>j) min=j; else min=i; if (k<min) min=k; printf (“min(%d,%d,%d)= %d\n”,i,j,k,,min); }

4.5.6. Instrucţiunea while

INSTRUCŢIUNEA

while

are următorul format:

while (expresie) instructiune; Cu ajutorul instrucţiunii while se realizează structura repetitivă pretestată (condiţionată anterior). Efectul: 1) se evaluează valoarea expresiei din paranteze; 2) dacă expresia are valoarea diferită de zero, atunci se execută instructiune şi se reia punctul 1), altfel se trece la instrucţiunea următoare instrucţiunii while. Deci instructiune se execută repetat atâta timp cât expresia din paranteză este diferită de zero. Se observă că dacă expresia are valoarea zero de la început, atunci instructiune nu se execută niciodată. Antetul ciclului while este construcţia while (expresie) iar instructiune formează corpul ciclului. În cazul în care este necesar să se execute repetat mai multe instrucţiuni, se utilizează o instrucţiune compusă formată din instrucţiunile respective. Exemplu: Vom crea un program care citeşte un întreg n şi scrie n!. Algoritmul în pseudocod este următorul: Citeste n f=1 i=2 CâtTimp i<=n execută 57

f=f*i; i=i+1 SfârşitCâtTimp Scrie n,f Programul în C este: #include<stdio.h> void main (void) { int n,i; double f; f=1.0; i=2; printf(“\n dati n= “); scanf(“%d”,&n); while (i<=n) { f=f*i; i++; } printf(“\nn=%d, iar n!=%g\n”,n,f); }

Corpul ciclului while se poate scrie mai compact astfel: while (i<=n) f*=i++;

4.5.7. INSTRUCŢIUNEA for Instrucţiunea for, ca şi instrucţiunea while, se utilizează pentru a realiza o structură repetitivă pretestată. Formatul instrucţiunii este: for(exp1; exp2; exp3) instructiune; Antetul ciclului este definit de for(exp1; exp2; exp3) iar instructiune formează corpul ciclului. Prima expresie exp1 constituie partea de iniţializare a ciclului, iar exp3 este partea de reiniţializare a ciclului. Condiţia de continuare a ciclului este exp 2. De obicei exp1 şi exp3 reprezintă atribuiri. Efectul: 1) se execută secvenţa de iniţializare definită de expresia exp1; 2) se evaluează exp2; dacă exp2 are valoarea zero, atunci se iese din ciclu, adică se trece la instrucţiunea următoare instrucţiunii for, altfel se execută instrucţiunea din corpul ciclului; 3) se execută apoi secvenţa de reiniţializare definită de exp3, apoi se reia secvenţa de la punctul 2). Observaţii: 1o. Ca şi în cazul instrucţiunii while, instrucţiunea din corpul ciclului for poate să nu se execute niciodată dacă exp2 are valoarea zero chiar la prima evaluare. 58

2o. Expresiile din antetul instrucţiunii for pot fi şi vide; totuşi caracterele “;” vor fi întotdeauna prezente. 3o. Comparând instrucţiunile for şi while observăm că instrucţiunea for cu formatul anterior se poate realiza cu secvenţa următoare folosind while: exp1; while (exp2) { instructiune; exp3; } Invers, o instrucţiune while de forma: while (exp) instructiune este echivalentă cu următoarea instrucţiune for: for(; exp; ) instructiune. Autorii limbajului C propun ca instrucţiunea for să se folosească cu prioritate pentru ciclurile care au pas. Exemple: Vom da o secvenţă de instrucţiuni care însumează elementele unui tablou: s=0; for(i=0; i void main(void) { long n; for (n=0; getchar()!=EOF; n++); printf (“\nnumarul caracterelor citite =%ld\n”,n); } sau scrisă cu instrucţiunea while #include <stdio.h> void main(void) { long n=0; while (getchar()!=EOF) n++; printf (“\nnumarul caracterelor citite =%ld\n”,n); }

4.5.8. INSTRUCŢIUNEA do-while Această instrucţiune realizează structura repetitivă condiţionată posterior (posttestată) dar modificată faţă de REPEAT .. UNTIL. Această instrucţiune s-a introdus pentru o mai mare flexibilitate în scrierea programelor. Formatul ei este: do instructiune; 59

while (exp); Efectul: 1) se execută instrucţiunea instructiune; 2) se evaluează expresia exp din paranteze; 3) dacă valoarea expresiei este zero se trece la instrucţiunea următoare instrucţiunii do-while; altfel se revine şi se execută din nou instructiune. Observaţii: 1o. Structura realizată de instrucţiunea do-while poate fi realizată printr-o secvenţă în care se foloseşte instrucţiunea while astfel: instructiune; while (exp) instructiune; o 2 . Se observă că în cazul instrucţiunii do-while, corpul ciclului se execută cel puţin odată, spre deosebire de ciclurile while şi for unde corpul ciclului poate să nu se execute niciodată. Exemplu: Vom da un program care calculează rădăcina pătrată dintr-un număr real a>=0. #include<stdio.h> #define EPS 1e-10 void main (void) { double x1,x2,y,a; clrscr(); printf(“\ndati un numar real pozitiv a=”); if (scanf(“%lf”,&a) !=1 || a<0) printf (“numarul citit nu este pozitiv\n”); else { x2 = 1.0; do { x1 = x2; x2 = 0.5 *(x1+a/x1); if ((y=x2-x1) < 0) y = -y; } while (y >= EPS); printf (“radacina patrata din:%g este: %.2lf\n”,a,x2); } //sfirsit else }

// sterge ecranul

// formula de iteratie

// 2 zecimale

4.5.9. INSTRUCTIUNEA switch Instrucţiunea switch permite realizarea structurii alternativa generalizată. Ea este echivalentă cu o imbricare de structuri de alternativă simple. Utilizarea instrucţiunii switch face în schimb programul mult mai clar. Formatul instrucţiunii switch este următorul: switch (exp) { case c1: case c2: ... case cn: 60

sir1 break; sir2 break; sirn break;

default:

sir

} unde:

c1,. . . cn sunt constante sau constante simbolice; sir1, . . . ,sirn, sir sunt şiruri de instrucţiuni.

Efectul: 1) se evaluează expresia din paranteză; 2) se compară pe rând valoarea expresiei cu valorile constantelor c1, . . . , cn; 3) dacă valoarea expresiei coincide cu valoarea lui ck, se execută secvenţa de instrucţiuni definită prin sirk; în cazul în care valoarea expresiei nu coincide cu nici una din constantele c1, . . . , cn, se execută secvenţa de instrucţiuni definită prin sir; 4) după execuţia secvenţei sirk sau sir se trece la instrucţiunea următoare instrucţiunii switch, adică la prima instrucţiune aflată după acolada închisă care termină instrucţiunea switch respectivă; evident, acest lucru are loc dacă şirul care se execută nu impune, el insuşi, un alt mod de continuare a execuţiei, de exemplu o revenire din funcţia respectivă, un salt la o anumită instrucţiune, etc. Observaţii: 1o. Ramura default nu este obligatorie. În lipsa ei, dacă valoarea expresiei nu coincide cu nici una din constantele c1,. . . , cn, instrucţiunea switch respectivă nu are nici un efect. 2o.Construcţia break reprezintă o instrucţiune. Ea termină fiecare ramură de instrucţiuni sir1, . . . , sirn, provocând saltul la instrucţiunea următoare instrucţiunii switch sau, cum se mai spune, realizează ieşirea din instrucţiunea switch. 3o. Instrucţiunea break nu este obligatorie. În cazul în care este absentă, se execută secvenţial următoarea ramură. De exemplu dacă avem secvenţa: switch (exp) { case c1: sir1 case c2: sir2 } ea se execută în felul următor: - dacă valoarea expresiei este egală cu c1 se execută sir1 şi apoi sir2; - dacă valoarea expresiei este egală cu c2 se execută sir2; - daca valoarea expresiei difera de valorile c1 şi c2 instrucţiunea switch de mai sus nu este efectivă, se trece la instrucţiunea următoare care urmează după switch. - secvenţa de mai sus se putea realiza şi astfel: if (exp = = c1) { sir1 sir2 }else if (exp = = c2) sir2 Exemplu: Vom citi din fişierul de intrare construcţii de forma: op1 operator op2, unde op1 şi op2 sunt numere întregi (operanzi întregi) iar operator este un operator aritmetic {“+”, “-“, “*”, “/”}. La ieşire se va scrie valoarea expresiei citite. De exemplu dacă se citeşte secvenţa 100/3 se va afişa rezultatul 33. Programul permite citirea şi evaluarea mai multor astfel de expresii, până la întâlnirea sfârşitului de fişier. #include <stdio.h>

61

void main (void) { int op1,op2,operator,rezultat,i; while (( i=scanf(“%d %c %d”, &op1,&operator, &op2)) != EOF) if (i = = 3 ) // ramura adevarat inseamna ca s-au citit 3 campuri corecte { switch (operator) { case ‘+’: rezultat = op1 + op2 ; // avem adunare break; case ‘-‘ : rezultat = op1 – op2; // avem scadere break; case ‘*’ : rezultat = op1 * op2; // avem inmultire break; case ‘/’ : // avem impartire intreaga if (op2 = = 0) { printf (“divizor nul\n”); rezultat = 0; } else rezultat = op1 / op2; break; default : printf (“operator eronat\n”); rezultat = 0; } // sfarsit switch printf (“%d %c %d %d\n”, op1, operator, op2, rezultat); } else printf (“expresie eronat\n”); // sfarsit if si while }

4.5.10. INSTRUCŢIUNEA break Formatul instrucţiunii este următorul: break; De obicei instrucţiunea break se foloseşte pentru a ieşi dintr-un ciclu. Dacă există mai multe cicluri imbricate instrucţiunea break va trece controlul la ciclul de nivel imediat superior (deci imbricarea rămâne, nu se iese din toate ciclurile). O altă utilizare este în instrucţiunea switch, după cum am observat în paragraful anterior. Un alt exemplu de utilizare frecventă este ieşirea dintr-un ciclu infinit de forma: for ( ; ; ) {. . . if (exp) break; ... }

4.5.11. INSTRUCŢIUNEA continue Formatul instrucţiunii este următorul: continue; Efectul: 1) în ciclurile while şi do-while ea realizează saltul la evaluarea expresiei care decide asupra continuării ciclului; 2) în ciclul for ea realizează saltul la pasul de reiniţializare. 62

Observaţie: 1o. Instrucţiunea continue se utilizează numai în corpul unui ciclu, permiţând, după caz, să se treacă la pasul următor al ciclului sau să se iasă din ciclu.

4.5.12. INSTRUCŢIUNEA goto Conform principiilor programării structurate instrucţiunea goto nu ar fi necesară. Dar ea a fost introdusă în limbaj, deoarece, în anumite cazuri, se dovedeşte a fi utilă, asigurând o flexibilitate mai mare în programare. De multe ori ieşirea dintr-un ciclu imbricat în alte cicluri se realizează mai simplu cu ajutorul instrucţiunii goto. În lipsa ei ar trebui să folosim mai mulţi indicatori şi teste asupra valorilor acestora pentru ieşirea din ciclu. Saltul făcut de goto se face la o instrucţiune care este prefixată de o etichetă. Prin etichetă vom înţelege un nume urmat de caracterul “:”. Etichetele sunt locale unei funcţii. Instrucţiunea goto are următorul format: goto eticheta; Efectul: 1) se realizează saltul la instrucţiunea prefixată de eticheta al cărei nume se află scris după cuvântul cheie goto.

4.5.13. APELUL ŞI REVENIREA DINTR-O FUNCŢIE 4.5.13.1. Apelul unei funcţii În limbajul C funcţiile sunt de două tipuri: - funcţii care returnează o valoare la revenirea din ele; - funcţii care nu returnează nici o valoare la revenirea din ele. O funcţie care nu returnează nici o valoare la revenirea din ea se apelează printr-o instrucţiune de apel. Ea are următorul format: nume (lista_parametrilor_efectivi); (*) unde: - nume este numele funcţiei; - lista_parametrilor_efectivi este fie vidă, fie se compune din una sau mai multe expresii separate prin virgulă. Instrucţiunea de apel este un caz particular al instrucţiunii expresie. Parametrii efectivi (de la apel) trebuie să corespundă cu cei formali (de la definirea funcţiei) prin ordine, tip şi număr. În cazul în care o funcţie returnează o valoare, ea poate fi apelată fie printr-o instrucţiune de apel, fie sub forma unui operand al unei expresii. Observaţii: 1o. Dacă nu dorim să utilizăm valoarea returnată de funcţia respectivă, apelul se face printr-o 63

instrucţiune de apel. 2o. Dacă dorim să utilizăm valoarea returnată de funcţie, vom folosi apelul funcţiei drept operand într-o expresie, operandul având formatul (*). Exemple de apeluri de funcţii folosite până acum sunt apelurile funcţiilor standard printf, scanf, getchar şi putchar. Funcţiile printf şi putchar au fost apelate prin instrucţiuni de apel, valorile returnate de ele nefiind utilizate. În schimb funcţiile scanf şi getchar au fost apelate în ambele moduri, atât prin instrucţiuni de apel, cât şi ca operanzi în diferite expresii.

4.5.13.2. Prototipul unei funcţii O funcţie poate fi apelată dacă ea este definită în fişierul sursă înainte de a fi apelată. După cum am prezentat în lecţia 1 nu întotdeauna este posibil acest lucru şi în astfel de cazuri apelul funcţiei trebuie să fie precedat de prototipul ei. Prototipul unei funcţii are ca scop să informeze compilatorul despre: - tipul valorii returnate de funcţie; - tipurile parametrilor. În felul acesta, la apelul unei funcţii, compilatorul poate face teste cu privire la tipul expresiilor care reprezintă parametrii efectivi, precum şi unele conversii necesare asupra valorii returnate de funcţie. Observaţii: 1o. Tipurile parametrilor pot să lipsească. În acest caz, compilatorul nu controlează tipurile parametrilor efectivi, singura informaţie conţinută de prototip fiind tipul valorii returnate de funcţia respectivă. 2o. Absenţa atât a prototipului unei funcţii, cât şi a definiţiei funcţiei înainte de a fi apelată este posibilă; în acest caz se presupune că funcţia returnează o valoare de tip int. 3o. În practică se recomandă utilizarea prototipurilor pentru toate funcţiile înainte de a fi apelate. În acest scop, ele vor fi scrise la începutul fişierelor sursă. Formatele posibile ale unui prototip sunt: formatul 1:tip nume (lista_declaratiilor_de_parametri); formatul 2:tip nume (lista_ tipurilor_parametrilor); formatul 3:tip nume (void); formatul 4:tip nume (); Formatul 2 este cel mai utilizat. Formatul 3 se poate folosi pentru orice funcţie care nu are parametri. Formatul 4 se poate folosi pentru orice funcţie la al cărei apel nu se doresc teste referitoare la tipul parametrilor efectivi. Funcţiile din biblioteca standard a limbajului C au prototipurile definite în fişierele de tip .h.

4.5.13.3. Apel prin valoare şi apel prin referinţă La apelul unei funcţii, fiecărui parametru formal i se atribuie valoarea parametrului efectiv care-i corespunde. Deci, la apelul unei funcţii se transferă valorile parametrilor efectivi. Din această cauză se spune că apelul este prin valoare (call by value). În anumite limbaje de programare, la apel nu se transferă valorile parametrilor efectivi ci adresele acestora. În acest caz se spune că apelul este prin referinţă (call by refference). Între cele două tipuri de apeluri există o diferenţă esenţială şi anume: în cazul apelului 64

prin valoare funcţia apelată nu poate modifica parametrii efectivi din funcţia apelantă, neavând acces la ei. În cazul apelului prin referinţă, funcţia apelată, dispunând de adresele parametrilor efectivi, îi poate modifica. În limbajul C apelul se realizează implicit prin valoare. În cazul că un parametru este numele unui tablou atunci transferul se realizează prin referinţă deoarece numele unui tablou este un pointer şi conţine adresa primului element al tabloului. Transferul prin referinţă se realizează cu ajutorul variabilelor de tip pointer şi cu ajutorul operatorului de adresă (&).

4.5.13.4. Revenirea dintr-o funcţie Revenirea dintr-o funcţie se poate face în două moduri: - la întâlnirea instrucţiunii return; - după execuţia ultimei sale instrucţiuni, adică a instrucţiunii care precede acolada închisă ce termină corpul funcţiei respective. Instrucţiunea return are două formate: return; sau

return expresie;

Primul format se utilizează când funcţia nu returnează o valoare, iar cel de-al doilea când funcţia returnează o valoare. În acest ultim caz, funcţia returnează valoarea expresiei specificate. Observaţie: 1o. Când revenirea se face după execuţia ultimei instrucţiuni a funcţiei nu se returnează o valoare; revenirea în acest caz, se face ca şi cum acolada închisă de la sfârşitul corpului funcţiei ar fi precedată de instrucţiunea return. Exemplu: vom da un exemplu de apel al funcţiei care determină rădacina pătratică dintr-un număr nenegativ. #include<stdio.h> double radacina_2 (double) void main (void) { double d; clrscr();

// prototipul functiei // functia principala care citeste d // si afiseaza radacina patrata din d // sterge ecranul

if (scanf (“%lf”,&d) != || d<0) printf (“numarul dat este eronat\n”); else printf (“d=%f, radacina patrata = %.10g\n”, d, radacina_2(d)); #define EPS 1e-10 double radacina_2 (double x) { double x1,x2,y; x2 = 1.0; do { x1 = x2; x2 = 0.5 *(x1+x/x1); // formula de iteratie if ((y=x2-x1) < 0) y = -y; } while (y >= EPS);

65

return x2; }

Observaţie: 1o. Limbajul C dispune de o bibliotecă matematică în care sunt incluse o serie de funcţii pentru calculul valorilor funcţiilor elementare. Există o funcţie numită sqrt (cu prototipul double sqrt (double);). Fişierul care conţine biblioteca matematică se numeşte math.h şi trebuie inclus în fişierul sursă de lucru dacă se doreşte utilizarea funcţiilor definite în el. Pentru algoritmul palindromului, scris în pseudocod, dăm şi varianta în limbajul C: #include<stdio.h> #include void main(void) { long n,m,x; int c; printf ("\ndati un numar natural:"); scanf ("%ld",&n); x=n; m=0; while (x > 0) { c = x % 10; m = m*10+c; x = x / 10; } if (n == m) printf ("numarul %ld este palindrom",n); else printf ("numarul %ld nu este palindrom",n); getch(); }

66