cuprins 1. baze Şi sisteme de...

CUPRINS 1. BAZE ŞI SISTEME DE NUMERAŢIE .......................................................................... 3

1.1 SISTEME ŞI BAZE DE NUMERAŢIE ................................................................................... 3

SUGESTII TEME DE LABORATOR ......................................................................................... 19

1.2 EFECTUAREA OPERAŢIILOR ÎN DIFERITE BAZE DE NUMERAŢIE ..................... 20


2. REPREZENTAREA DATELOR ÎN CALCULATOR ................................................... 28


3. ELEMENTE DE TEORIA CODURILOR .................................................................... 36


4. ALGORITMI ŞI SCHEME LOGICE ............................................................................ 47

EXEMPLE ...................................................................................................................................... 56


5. TIPURI DE DATE. CITIREA ŞI TIPĂRIREA DATELOR ........................................ 59

EXEMPLE ...................................................................................................................................... 63


6. INSTRUCŢIUNILE IF ŞI SWITCH ............................................................................. 70

EXEMPLE ...................................................................................................................................... 73


7. CICLUL FOR ŞI INSTRUCŢIUNILE REPETITIVE DE TIP WHILE ŞI DO-WHILE .................................................................................................................................... 79

EXEMPLE ...................................................................................................................................... 80


8. TABLOURI UNIDIMENSIONALE PROBLEME DE ORDONARE ......................... 83

EXEMPLE ...................................................................................................................................... 84


9. TABLOURI BIDIMENSIONALE ................................................................................. 89

EXEMPLE ...................................................................................................................................... 89


10. FUNCŢII DEFINITE DE UTILIZATOR ..................................................................... 93

EXEMPLE ...................................................................................................................................... 96

SUGESTII TEME DE LABORATOR ....................................................................................... 102

11. POINTERI .................................................................................................................... 103

EXEMPLE .................................................................................................................................... 106


1

12. ŞIRURI DE CARACTERE ........................................................................................... 111

EXEMPLE .................................................................................................................................... 116


13. STRUCTURI ................................................................................................................. 119

EXEMPLE .................................................................................................................................... 120


14. LISTE ............................................................................................................................ 124

EXEMPLE .................................................................................................................................... 125


15. RECURSIVITATE ........................................................................................................ 130

EXEMPLE .................................................................................................................................... 131


16. METODA DIVIDE ET IMPERA................................................................................. 135

EXEMPLE .................................................................................................................................... 136


17. METODA BACKTRACKING ...................................................................................... 140

EXEMPLE .................................................................................................................................... 141


18. GRAFURI ŞI ARBORI ................................................................................................. 144

18.1 GRAFURI NEORIENTATE ............................................................................................... 144

EXEMPLE .................................................................................................................................... 146

18.2 GRAFURI ORIENTATE ..................................................................................................... 159


19. MINICULEGERE DE PROBLEME ........................................................................... 165

2

1. BAZE ŞI SISTEME DE NUMERAŢIE

1.1 SISTEME ŞI BAZE DE NUMERAŢIE

Prezentare generală; definiţii Suntem atât de obişnuiţi cu sistemul de numeraţie zecimal, încât ni se pare că

utilizarea lui este cel puţin cea mai bună alegere, sau, uneori, suntem tentaţi să credem chiar că este singura posibilitate şi nici nu ne mai punem problema ce « se ascunde » în spatele acestei reprezentari, care este, de fapt, doar una dintre multiplele posibilităţi de reprezentare a numerelor şi de efectuare a calculelor.

Sa luăm, pentru exemplificare, numărul natural 209319. În mod evident, noi întelegem că este vorba de numărul « două sute nouă mii trei sute

nouăsprezece », adică : 2 × 100000 + 0 × 10000 + 9 × 1000 + 3 × 100 + 1 × 10 + 9,

ceea ce mai poate fi scris ca : 209319 = 2 × 105 + 0 × 104 + 9 × 103 + 3 × 102 + 1 × 101 + 9 × 100. Deci, orice număr natural poate fi scris ca o sumă de produse, fiecare termen al sumei fiind produsul dintre o cifră (de la 0 până la 9, aşa cu am învăţat în clasele primare …) şi o putere a lui 10. Puterile lui 10 descresc de la stânga spre dreapta, cea mai mare putere fiind determinată de mărimea numărului respectiv. Pentru un numar N oarecare vom avea, deci :

N = an×10n + an-1×10 n-1 + an-2×10n-2 + … + a2×102 + a1×101 + a0×100, (1) unde coeficienţii ai sunt cifre de la 0 până la 9. După cum am fost învăţaţi, noi nu mai scriem puterile lui 10, ci doar înşiruirea acestor coeficienţi (cifrele din care este alcătuit numărul). Puterile corespunzătoare ale lui 10 le subînţelegem, după poziţia pe care o ocupă cifrele respective în alcătuirea numărului. Un astfel de sistem de numeraţie se numeşte sistem de numeraţie poziţional. Avem deci la dispoziţie 10 simboluri (0, 1, 2, 3, 4, 5, 6, 7, 8, 9), cu ajutorul cărora vom putea reprezenta orice nuamăr, indiferent de mărimea sa. Aşa cum numărul 2 × 105 + 0 × 104 + 9 × 103 + 3 × 102 + 1 × 101 + 9 × 100 era reprezentat ca 209319 (renunţând la scrierea puterilor lui 10, care înmulţesc de fapt fiecare cifră), numărul N = an×10n + an-1×10 n-1 + an-2×10n-2 + … + a2×102 + a1×101 + a0×100

3

va fi scris ca

N = anan-1an-2 … a1a0 , (2) prin aceasta neîntelegând înmulţirea între coeficienţii ai ci, aşa cum am arătat, interpretarea din formula (1). Coeficienţii ai sunt cifrele din care este format numarul N. Alegerea a 10 simboluri (cifrele de la 0 până la 9) nu este însă nici singura posibilitate si nici cea mai bună în orice ocazie. Antropologii sunt unanimi în a considera că această alegere se datorează în exclusivitate faptului că avem 10 degete la mâini. Mai mult, ea nu afost nici totdeauna nici pretutindeni valabilă. Se ştie cu certitudine că au existat reprezentări folosind :

- 20 de simboluri – urmările se pot vedea în limba franceză, unde numărul 99 se citeşte quatre vingt dix neuf, adică, mot-a-mot de 4 ori douăzeci şi nouăsprezece

- 12 simboluri – se regăsşte în sistemul de unităţi anglo-saxon (cu divizarea unităţilor de măsură în 12 părţi egale), sau în termenul românesc duzină, care, în mod riguros înseamnă o cantitate de 12 obiecte

- 60 de simboluri – utilizat în Egiptul antic Să revenim la numărul nostru (209319). El poate fi la fel de bine reprezentat ca o sumă de puteri ale lui 7 (de exemplu) şi nu ale lui 10 ; mai mult, putem face în aşa fel încât coeficienţii acestor puteri să ia valori numai într-o mulţime cu 7 elemente {0, 1, 2, 3, 4, 5, 6} 209319 = 1×76 + 5×75 + 3×74 + 1×73 + 1×72 + 5×71 + 5×70 , ceea ce poate fi verificat imediat, prin efectuarea calculelor ( 1×76 + 5×75 + 3×74 + 1×73 + 1×72 + 5×71 + 5×70 = 1×117649 + 5×16807 + 3×2401 + 1×343 + 1×49 + 5×7 + 5×1 = 117649+84035+7203+343+49+35+5 = 209319 ). Pentru a putea deci să reprezentăm orice număr conform principiului enunţat, avem nevoie de două mulţimi :

- o mulţime A de denumiri (numele cifrelor, de exemplu « zero », « unu », etc.) - o mulţime B de simboluri (reprezentarea grafică a cifrelor din mulţimea A ; de

exemplu « 1 », « 2 », etc) Între cele două mulţimi există o corespondentă biunivocă. Numărul de elemente al mulţimii A (şi deci, în mod evident, şi al mulţimii B) poate fi oarecare, dar cel puţin 2. Astfel, în sistemul zecimal (sistemul cu care suntem astăzi obişnuiţi), acest număr este 10 (cifrele de la 0 până la 9). In exemplul anterior, acest număr este 7 (cifrele de la 0 până la 6). Putem utiliza şi un număr mai mare de simboluri (am văzut că vechii egipteni foloseau 60 …). Va trebui ca în afara celor cu care suntem familiarizaţi (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) să mai “inventăm” alte simboluri. În informatică s-a generalizat utilizarea literelor mari ale alfabetului latin. De exemplu, să presupunem că ne-am decis la utilizarea unui sistem de numeratie cu 18 de simboluri (cifre). Trebuie să adăugăm « cifrele » A, B, C, D, E, F, G, H.

4

Semnificaţiile acestor simboluri vor fi : 0 cifra (şi numărul natural) 0 1 cifra (şi numărul natural) 1 2 cifra (şi numărul natural) 2 3 cifra (şi numărul natural) 3 4 cifra (şi numărul natural) 4 5 cifra (şi numărul natural) 5 6 cifra (şi numărul natural) 6 7 cifra (şi numărul natural) 7 8 cifra (şi numărul natural) 8 9 cifra (şi numărul natural) 9 A cifra A, corespunzând numărului natural 10 din sistemul zecimal B cifra B, corespunzând numărului natural 11 din sistemul zecimal C cifra C, corespunzând numărului natural 12 din sistemul zecimal D cifra D, corespunzând numărului natural 13 din sistemul zecimal E cifra E, corespunzând numărului natural 14 din sistemul zecimal F cifra F, corespunzând numărului natural 15 din sistemul zecimal G cifra G, corespunzând numărului natural 16 din sistemul zecimal H cifra H, corespunzând numărului natural 17 din sistemul zecimal Având la dispoziţie aceste 18 simboluri, putem exprima numărul natural 209319 din sistemul zecimal ca o sumă de produse în care să apară puterile lui 18, iar coeficienţii să fie din mulţimea celor 18 simboluri de mai sus : N = 209319 = 1×184 + H×183 + G×182 + 0×181 + F×180 Pentru verificare, vom efectua calculele, ţinând seama de semnificaţia simbolurilor nou introduse : 1×184 + H×183 + G×182 + 0×181 + F×180 = 1×184 + 17×183 + 16×182 + 0×181 + 15×180 = =1×104976 + 17×5832 + 16×324 + 0×18 + 15×1 = 209319 În sistemul zecimal, scrisesem numărul 2×105 + 0×104 + 9×103 + 3×102 + 1×101 + 9×100 renunţând să mai scriem şi puterile lui 10, prin simpla înşiruire a coeficienţilor, care constituiau astfel cifrele constitutive ale numărului : 209319. Dacă vom face acelaşi lucru şi cu reprezentarea 1×184 + H×183 + G×182 + 0×181 + F×180, vom obţine N = 1HGOF. Suntem acum în măsură să generalizăm : Putem exprima orice număr natural dacă dispunem de doua mulţimi (A – a denumirilor cifrelor şi B – a simbolurilor grafice ale acestor cifre) între care s-a stabilit o corespondenţă biunivocă. Numărul de elemente ale mulţimii B se numeşte baza de numeraţie.

5

Orice număr natural se exprimă atunci ca o sumă de produse între nişte coeficienţi (cifre cuprinse între 0 şi b-1 , unde b este baza de numeraţie) şi puterile corespunzătoare ale bazei b :

N = an×bn + an-1×bn-1 + … + a2×b2 + a1+b1 + a0×b0 , (3) unde coeficienţii ai iau, în mod evident, valori între 0 şi b-1. Dacă un număr este la forma (3), spunem că este exprimat sub formă polinomială. Dacă nu există posibilitatea de confuzie (ştim care este baza de numeraţie în care am reprezentat numărul), putem rennţa la scrierea polinimială (deci la transcrierea puterilor bazei), scriind doar înşiruirea coeficienţilor ai :

N = anan-1an-2 … a1a0 (4), aşa cum procedam în cazul sistemului zecimal. Pentru a evita ambiguităţile, baza se scrie între paranteze în modul următor :

N = anan-1an-2 … a1a0 (b) (5) În cuprinsul acestui capitol, vom utiliza reprezentările numerelor sub formele din formulele (3) şi (5). Exemplele pe care le-am prezentat anterior se sintetizează atunci în modul următor : N = 209319(10) = 1531155(7) = 1HG0F(18) (este deci vorba de reprezentarea aceluiaşi număr în bazele de numeraţie 10, 7 şi 18). În studiul informaticii, importanţă practică prezintă următoarele baze de numeraţie :

a) b=10 (sistemul zecimal) este forma exterioara în care se prezintă datele ce urmează a fi prelucrate şi rezultatele acestor prelucrări ; este sistemul de numeraţie cu care suntem obişnuiţi, sistem care utilizează cele 10 simboluri cunoscute (cifrele 0,1, 2, 3, 4, 5, 6, 7, 8, 9 – cifre preluate de către europeni de la matematicienii arabi) b) b=2 (sistemul binar) este forma sub care se prezintă informaţiile în calculator ; aşa cum rezultă din definiţiile date până acum, utilizează doar două simboluri – cifrele 0 şi 1 – vom reveni pe larg asupra acestui sistem ;

c) b=8 (sistemul octal) utilizează 8 simboluri (cifrele de la 0 până la 7) – utilizarea sa este mai restânsă decât a sistemelor 2 si 16 ; d) b=16 (sistemul hexagesimal)

constituie (aşa cum vom vedea) mai degrabă o formă « condensată » de reprezentare a sistemului binar ; utilizează 16 simboluri (cifrele de la 0 până la 9, la care se adauga 6 simboluri noi, cu semnificaţiile :

6

A cifra A, corespunzând numărului natural 10 din sistemul zecimal B cifra B, corespunzând numărului natural 11 din sistemul zecimal C cifra C, corespunzând numărului natural 12 din sistemul zecimal D cifra D, corespunzând numărului natural 13 din sistemul zecimal E cifra E, corespunzând numărului natural 14 din sistemul zecimal F cifra F, corespunzând numărului natural 15 din sistemul zecimal) Este evident că prima problemă care se pune, pentru a putea utiliza numere scrise în alte sisteme de numeraţie decât cel zecimal, este de a dispune de algoritmi pentru trecerea acestor numere în baza dorita (şi în general dintr-o bază în alta).

Trecerea numerelor naturale din baza 10 intr-o baza b oarecare

Să pornim tot de la un exemplu concret : reluăm numărul 209319(10) . Dorim să trecem acest număr în baza 5. Fără a spune (pentru început) cum am rezolvat această problemă, vom da deja rezultatul :

N = 209319(10) = 23144234(5)

Chiar dacă nu ştim (deocamdată) cum am ajuns la acest rezultat, suntem deja în măsură să verificăm dacă este corect. Întra-adevăr, conform definiţiilor date şi a formulei (3), N = 23144234(5) = = 2×57 + 3×56 + 1×55 + 4×54 + 4×53 + 2×52 + 3×51 + 4×50 = = 2×78125 + 3×15625 + 1×3125 + 4×625 + 4×125 + 2×25 + 3×5 + 4×1 = = 156250+46875+3125+2500+500+50+15+4 = = 209319 unde toate calculele s-au efectuat în sistemul zecimal. Cum putem însă să ajungem la această reprezentare în baza 5 (corectă, dupa cum tocmai am demonstrat) ? Conform definiţiei, numărul căutat este de forma : a7×57 + a6×56 + a5×55 + a4×54 + a3×53 + a2×52 + a1×51 + a0×50, care este scrierea polinomială a numărului nostru în baza 5 şi unde trebuie să determinăm coeficienţii ai (să ajngem pe o cale oarecare la concluzia că a7=2, a6=3, a5=1, a4=4, a3=4, a2=2, a1=3, a0=4). Dacă împărţim numărul 209319 la 5 (baza în care vrem să trecem numărul), obţinem 209319 : 5 = 41863 rest 4 Dacă în scrierea polinomială a numărului în baza 5 (care este acelaşi număr 209319, altfel scris) scoatem factor comun pe 5, obţinem : N = 5(a7×56 + a6×55 + a5×54 + a4×53 + a3×52 + a2×51 + a1×50)+ a0, ceea ce înseamnă că împărţind la 5 obţinem cătul

7

C0 = a7×56 + a6×55 + a5×54 + a4×53 + a3×52 + a2×51 + a1×50

şi restul R0 = a0. Cum am împărţit la 5 acelaşi număr (doar exprimat altfel), rezultă că C0=41863, şi, ceea ce este mai important, a0=4. Am determinat deci coeficientul a0 din exprimarea numărului nostru în baza 5 ; el este chiar restul împărţirii lui 209319 la 5. Împărţind pe C0=41853 la 5 obţinem un nou cât şi un nou rest : C0 : 5 = 41853 : 5 = 8372 rest 3 Dar, C0 = a7×56 + a6×55 + a5×54 + a4×53 + a3×52 + a2×51 + a1×50 în care vom da din nou factor comun pe 5, obţinând : C0 = 5(a7×55 + a6×54 + a5×53 + a4×52 + a3×51 + a2×50)+ a1 şi, prin împărţire oţinem un cât şi un rest C0 : 5 = C1 rest R1, unde C1 = a7×55 + a6×54 + a5×53 + a4×52 + a3×51 + a2×50

şi R1=a1, de unde deducem că C1=8372 şi a1=3, adică am mai găsit o cifră din reprezentarea în baza 5 a numarului nostru : ea este restul împărţirii primului cât la 5 (baza în care dorim să trecem numărul. Continuând de aceeaşi manieră, obţinem succesiv : C1 : 5 = 8372 : 5 = 1674 şi rest 2, cu C1 = a7×55 + a6×54 + a5×53 + a4×52 + a3×51 + a2×50 = =5(a7×54 + a6×53 + a5×52 + a4×51 + a3×50)+ a2 = =5 × C2 + a2 ceea ce înseamnă că C2=1674 şi a2=2 C2 : 5 = 1674 : 5 = 334 şi rest 4 C2 = a7×54 + a6×53 + a5×52 + a4×51 + a3×50 = = 5(a7×53 + a6×52 + a5×51 + a4×50)+ a3 = = 5 × C3 + a3 ceea ce înseamnă ca C3=334 şi a3=4 C3 : 5 = 334 : 5 = 66 şi rest 4 C3 = a7×53 + a6×52 + a5×51 + a4×50 = = 5(a7×52 + a6×51 + a5×50)+ a4 = = 5 × C4 + a4 ceea ce înseamnă că C4=66 şi a4=4 C4 : 5 = 66 : 5 = 13 şi rest 1

8

C4 = a7×52 + a6×51 + a5×50 = = 5(a7×51 + a6×50)+ a5 = = 5 × C5 + a5 ceea ce înseamnă că C5=13 şi a5=1 C5 : 5 = 13 : 5 = 2 şi rest 3 C5 = a7×51 + a6×50 = = 5(a7×50) + a6 = = 5 × C6 + a6 ceea ce înseamnă că C6=2 şi a6=3 C6 : 5 = 2 : 5 = 0 şi rest 2 (ATENŢIE : Noul cât este zero !) C6 = a7×50 = = 5 × C7 + a7 ceea ce înseamnă că C7=0 (semnal de STOP) şi a7=2 Observăm cu uşurinţă că, împărţind rând pe rând numărul nostru din baza 10 şi apoi resturile succesive obţinute la 5 (noua bază în care dorim să exprimăm numărul dat), obţinem resturile a0, a1, a2, … ,a7, adică tocmai cifrele constitutive ale numărului nostru în baza 5 (în ordinea inversă în care apar ele în exprimarea polinomială).

N == 209319(10) = a7a6a5a4a3a2a1a0 (5) = 23144234(5) = = 2×57 + 3×56 + 1×55 + 4×54 + 4×53 + 2×52 + 3×51 + 4×50

Din mersul de calcul, este evident că acest lucru rămâne valabil oricare ar fi baza b în care dorim să exprimăm numărul nostru din baza 10, ceea ce poate fi demonstrat pornind de la formula (3) :

N = an×bn + an-1×bn-1 + … + a2×b2 + a1×b1 + a0×b0 =

= b(an×bn-1 + an-1×bn-2 + … + a2×b1 + a1×b0)+ a0

N: b = C0 rest R0 cu C0 = an×bn-1 + an-1×bn-2 + … + a2×b1 + a1×b0 = = b(an×bn-2 + an-1×bn-3 + … + a2×b0) + a1 R0=a0 C0 : b = C1 rest R1 cu C1 = an×bn-2 + an-1×bn-3 + … + a3×b1 + a2×b0 = = b(an×bn-3 + an-1×bn-4 + … + a3×b0) + a2 R1=a1 C1 : b = C2 rest R2 cu C1 = an×bn-3 + an-1×bn-4 + … + a4×b1 + a3×b0 = = b(an×bn-4 + an-1×bn-5 + … + a4×b0) + a3 R2=a2 ….

9

Procedeul se repetă până când se obţine câtul 0 (semnalul de STOP); ultimul rest obţinut va reprezenta prima cifră a numărului exprimat în baza b. Aceasta reprezintă chiar algoritmul de trecere a unui număr natural din baza 10 într-o bază b oarecare :

• se împarte succesiv numărul din baza 10 (şi câturile succesive obţinute pe parcurs) la valoarea b ( baza în care dorim să trecem numarul);

• se reţin resturile succesive obţinute pe parcurs; • procedeul se opreşte după ce s-a obţinut un cât egal cu zero (reţinându-se deci şi restul

respectiv) ; • resturile succesive obţinute constituie, în ordinea inversă, cifrele numărului exprimat

in noua bază. Trecerea numerelor naturale dintr-o baza b oarecare in baza 10

În toate exemplele pe care le-am analizat anterior (de trecere a unui număr din baza 10 intr-o bază b oarecare), am verificat corectitudinea rezultatelor obţinute prin aplicarea formulei polinomiale (3). Aceasta constituie chiar metoda de trecere a unui număr natural dintr-o bază b oarecare în baza 10 : aplicarea formulei polinomiale (3). Trecerea numerelor naturale dintr-o baza b1 (oarecare) intr-o alta baza b2 (oarecare)

Având la dispoziţie o metodă de trecere a unui număr natural dintr-o bază oarecare în baza 10 şi o metodă de trecere a unui număr natural din baza 10 într-o bază b oarecare, putem trece cu uşurinţă un număr dintr-o bază b1 într-o bază b2 , prin aplicarea combinată a celor două metode : se trece numărul din baza b1 în baza 10, apoi se trece rezultatul în baza b2 prin metodele deja menţionate. Trecerea reciproca a numerelor naturale dintr-o baza b1 intr-o baza b2=b1

k

În cazul particular în care cele două baze b1 şi b2 sunt legate între ele printr-o relaţie de forma b2 = b1

k, trecerea din baza b1 în baza b2 (şi reciproc) se poate face direct, fără a mai fi nevoie să mai trecem prin intermediul bazei 10.

Să exprimăm acelaşi număr N în bazele b2 şi b1; conform formulei polinomiale (3), vom avea :

N = αnb2

n + αn-1b2n-1 + αn-2b2

n-2 + … . + α2b22 + α1b2

1 + α0b20 = αnαn-1αn-

2…α2α1α0(b2) N = βnb1

n + βn-1b1n-1 + βn-1b1

n-2 + … . + β1b12 + β1b1

1 + β0b10 = βnβn-1βn-

2…β2β1β0(b1) unde : αi ≤ b2-1, i = 1 … n βj ≤ b1-1, j = 1 … m

10

şi, datorită faptului că b2 = b1

k, vom avea n ≤ m (acelaşi număr natural N are o reprezentare mai “lungă” în baza mai mică – b1 – decât în baza mai mare – b2 ). Putem să calculăm mai exact valoarea lui m (în raport cu n), raţionând în modul următor : Din exprimarea numărului N în baza b2 (unde am notat cu n cel mai mare exponent al bazei b2) rezultă că N < b2

n+1 (dacă n-ar fi aşa, în dezvoltarea polinomială ar trebui să apară şi puterea n+1). Ştiind că b2 = b1

k, putem deduce succesiv N < b2

n+1 = (b1k)n+1

Din exprimarea numărului N în baza b1 (unde am notat cu m cel mai mare exponent al bazei b1) şi, ţinând cont de rezultatul anterior, rezultă că m ≤ b1

kn+k-1 ceea ce înseamnă că reprezentarea numărului N în baza b1 va fi, de fapt : N = βkn+k-1bkn+n-1 + βkn+k-2bkn+n-2 + … + β2b2 + β1b1 + β0b0 = βkn+k-1βkn+k-

2…β2β1β0(b1)

Evident că, din acest punct de vedere, a trece numărul N din baza b2 în baza b1 revine la a determina coeficienţii βj (j ≤ kn+k-1) atunci când cunoaştem coeficienţii αi (i ≤ n). Să ne aducem aminte că dispunem deja de o metodă indirectă : aceea de a trece numărul din baza b2 în baza 10, apoi din baza 10 în baza b1, dar aşa cum anunţam anterior, în cazul particular în care ne găsim (b2 = b1

k), există şi o metodă directă, fără a mai fi necesară trecerea prin intermediul bazei 10.

Pentru aceasta să observăm că toţi coeficienţii αi sunt cifre (simboluri) în reprezentarea numărului în baza b2 (αi ≤ b2-1), dar exprimarea lor în baza b1 constituie numere (formate din una sau mai multe cifre), din simplul motiv că în baza b1 cifrele pot fi cel mult egale cu b1-1 ≤ b2-1.

Să exprimăm pe oricare dintre coeficienţii αi în baza b1; observăm, mai întâi, că αi ≤ b2-1 = b1

k-1 < b1k,

ceea ce înseamnă că în exprimarea polinomială a oricăruia dintre coeficienţii αi în baza b1 va apărea cel mult puterea k-1 a bazei b1; conform formulei polinomiale, vom avea : αi = ai,k-1b1

k-1 + ai,k-2b1k-2 + ai,k-3b1

k-3 + … + ai,2b12 + ai,1b1

1 + ai,0b10 =

= ai,k-1ai,k-2ai,k-3…ai,2ai,1ai,0 (b1),

(unde coeficienţii ai,j respectă condiţia ai,j ≤ b1-1). Înlocuind acum în dezvoltarea polinomială a numărului N în baza b2 valoarea coeficienţilor αi pe care tocmai am calculat-o şi ţinând cont de faptul că b2 = b1

k, obţinem : N = αnb2

n + αn-1b2n-1 + αn-2b2

n-2 + … . + α2b22 + α1b2

1 + α0b20 =

= (an,k-1b1k-1 + an,k-2b1

k-2 + an,k-3b1k-3 + … + an,2b1

2 + an,1b11 + an,0b1

0)b1kn +

= (an-1,k-1b1k-1 + an-1,k-2b1

k-2 + an-1,k-3b1k-3 + … + an-1,2b1

2 + an-1,1b11 + an-1,0b1

0)b1kn +

= (an-2,k-1b1k-1 + an-2,k-2b1

k-2 + an-2,k-3b1k-3 + … + an-2,2b1

2 + an-2,1b11 + an-2,0b1

0)b1kn +

… = (a2,k-1b1

k-1 + a2,k-2b1k-2 + a2,k-3b1

k-3 + … + a2,2b12 + a2,1b1

1 + a2,0b10)b1

kn +

11

= (a1,k-1b1k-1 + a1,k-2b1

k-2 + a1,k-3b1k-3 + … + a1,2b1

2 + a1,1b11 + a1,0b1

0)b1kn +

= (a0,k-1b1k-1 + a0,k-2b1

k-2 + a0,k-3b1k-3 + … + a0,2b1

2 + a0,1b11 + a0,0b1

0)b1kn

Observăm două lucruri :

- am obţinut o sumă de produse între nişte coeficienţi ai,j ≤ b1 şi puterile (strict descrescătoare) ale bazei b1;

- cea mai mare putere a bazei este kn+k-1 Acest lucru înseamnă că am obţinut tocmai reprezentarea căutată a numărului N în

baza b1 , adică am determinat coeficienţii βj (j ≤ kn+k-1) atunci când cunoaştem coeficienţii αi (i ≤ n).

Conform definiţiilor date, reprezentarea polinomială a numărului N în baza b1 va consta din simpla înşiruire a coeficienţilor ai,j rezultaţi din desfacerea parantezelor şi renunţarea la a mai scrie puterile bazei b1 :

N = an,k-1an,k-2an,k-3…an,2an,1an,0an-1,k-1an-1,k-2an-1,k-3…an-1,2an-1,1an-1,0an-2,k-1an-2,k-2an-2,k-3 …an-2,2an-2,1an-

2,0… a2,k-1a2,k-2a2,k-3…a2,2a2,1a2,0a1,k-1a1,k-2a1,k-3…a1,2a1,1a1,0a0,k-2a0,k-3…a0,2a0,1a0,0 Dar fiecare grupă de câte k cifre (coeficienţi) din această reprezentare constituie pur şi simplu reprezentarea în baza b1 a cifrelor αi ale numărului N în baza b2 (ne aducem aminte că am avut αi = ai,k-1b1

k-1 + ai,k-2b1k-2 + ai,k-3b1

k-3 + … + ai,2b12 + ai,1b1

1 + ai,0b10 =

= ai,k-1ai,k-2ai,k-3…ai,2ai,1ai,0 (b1) ). Mai exact spus : an,k-1an,k-2an,k-3…an,2an,1an,0 = αn an-1,k-1an-1,k-2an-1,k-3…an-1,2an-1,1an-1,0 = αn-1 an-2,k-1an-2,k-2an-2,k-3…an-2,2an-2,1an-2,0 = αn-2 … a2,k-1a2,k-2a2,k-3…a2,2a2,1a2,0 = α2 a1,k-1a1,k-2a1,k-3…a1,2a1,1a1,0 = α1 a0,k-1a0,k-2a0,k-3…a0,2a0,1a0,0 = α0 Acest rezultat ne sugerează metoda de trecere a numărului natural N din baza b2 în baza b1 în cazul b2=b1

k : Se exprimă toţi coeficienţii (cifrele) numărului N din baza b2 pe câte exact k cifre în baza b1; simpla înşiruire a acestor cifre (în ordinea în care au apărut) reprezintă numărul N în baza b1; eventualele zerouri care apar la stânga numărului se neglijează. Reciproc, pentru trecerea numărului N din baza b1 în baza b2=b1

k : Se despart coeficienţii (cifrele) numărului N din baza b1, începând de la dreapta spre stânga, în grupe de câte exact k cifre; se înlocuieşte fiecare astfel de grupe prin cifra corespunzătoare din baza b2; dacă în urma despărţirii ultima grupă din stânga are mai puţin de k cifre, se completează la stânga cu numărul necesar de zerouri; simpla înşiruire a acestor cifre (în ordinea în care au rezultat) reprezintă numărul N scris în baza b2.

12

EXEMPLE Exemplul 1 Să trecem numărul N = 209319(10) în baza 6. Se utilizează 6 simboluri (cifrele de la 0 până la 5). N : 6 = 209319 : 6 = 43886 rest 3 C0=43886 R0=a0=3 C0 : 6 = 43886 : 6 = 5814 rest 2 C1=5814 R1=a1=2 C1 : 6 = 5814 : 6 = 969 rest 0 C2=969 R2=a2=0 C2 : 6 = 969 : 6 = 161 rest 3 C3=161 R3=a3=3 C3 : 6 = 161 : 6 = 26 rest 5 C4=26 R4=a4=5 C4 6 = 26 : 6 =4 rest 2 C5=4 R5=a5=2 C5 : 6 = 4 : 6 = 0 rest 4 C6=0 R6=a6=4 Am obţinut restul 0, deci procedeul se opreşte aici. Rezultă că numărul N=209319(10) se exprimă în baza 6 pe 7 cifre : N = 209319(10) = a6a5a4a3a2a1a0 (6)= 4253023(6) Verificare : 4253023(6) = 4×66 + 2×65 + 5×64 + 3×63 + 0×62 + 2×61 + 3×60 = = 4×46656 + 2×7776 + 5×1296 + 3×216 + 0×36 + 2×6 + 3×1 = = 186624 + 155552 + 6480 + 0 + 12 + 3 = 209319 Exemplul 2 Să trecem numărul N = 209319(10) în baza 19. Se utilizează 19 simboluri (cifrele de la 0 până la 9 şi literele mari A=10, B=11, C=12, D=13, E=14, F=15, G=16, H=17, I=18). N : 19 = 209319 : 19 = 11016 rest 15 C0=11016 R0=a0=15=F C0 : 19 = 11016 : 19 = 579 rest 15 C1=579 R1=a1=15=F C1 : 19 = 579 : 19 = 30 rest 9 C2=30 R2=a2=9 C2 : 19 = 30 : 19 = 1 rest 11 C3=11 R3=a3=11=B C3 : 19 = 1 : 19 = 0 rest 1 C4=0 R4=a4=1 Am obţinut restul 0, deci procedeul se opreşte aici. Rezultă că numărul N=209319(10) se exprimă în baza 19 pe 5 cifre : N = 209319(10) = a4a3a2a1a0 (19) = 1B9FF(19)

13

Verificare : 1B9FF(19) = 1× 194 + B×193 + 9×192 + F×191 + F×190 = = 1× 194 + 11×193 + 9×192 + 15×191 + 15×190 = = 1×130321 + 11×6859 + 9×361 + 15×19 + 15×1 = = 130321 + 75449 + 3294 + 285 + 15 = 209319 Exemplul 3 Să trecem numărul N = 209319(10) în baza 2 (sistemul binar). Se utilizează 2 simboluri (cifrele 0 şi 1). N : 2 = 209319 : 2 = 104659 rest 1 C0=104659 R0=a0=1 C0 : 2 = 104659 : 2 = 52329 rest 1 C1=52329 R1=a1=1 C1 : 2 = 52329 : 2 = 26164 rest 1 C2=26164 R2=a2=1 C2 : 2 = 26164 : 2 = 13082 rest 0 C3=13082 R3=a3=0 C3 : 2 = 13082 : 2 = 6541 rest 0 C4=6541 R4=a4=0 C4 2 = 6541 : 2 =3270 rest 1 C5=3270 R5=a5=1 C5 : 2 = 3270 : 2 = 1635 rest 0 C6=1635 R6=a6=0 C6 : 2 = 1635 : 2 = 817 rest 1 C7=817 R7=a6=1 C7 : 2 = 817 : 2 = 408 rest 1 C8=408 R8=a7=1 C8 : 2 = 408 : 2 = 204 rest 0 C9=204 R9=a8=0 C9 : 2 = 204 : 2 = 102 rest 0 C10=102 R10=a9=0 C10 : 2 = 102 : 2 = 51 rest 1 C11=51 R11=a10=1 C11 : 2 = 51 : 2 = 25 rest 1 C12=25 R12=a11=1 C12 : 2 = 25 : 2 = 12 rest 1 C13=12 R13=a12=1 C13 : 2 = 12 : 2 = 6 rest 0 C14=6 R14=a13=0 C14 : 2 = 6 : 2 = 3 rest 0 C15=3 R15=a15=0 C15 : 2 = 3 : 2 = 1 rest 1 C16=1 R16=a16=1 C16 : 2 = 1 : 2 = 0 rest 1 C17=0 R17=a17=1 Am obţinut restul 0, deci procedeul se opreşte aici. Rezultă că numărul N=209319(10) se exprimă în baza 2 pe 18 cifre : N = 209319(10) = a17a16a15a14a13a12a11a10a9a8a7a6a5a4a3a2a1a0 (2) = = 110011100110100111(2) Verificare : 110011100110100111(2) = 1×216 + 1×215 + 0×214 + 0×213 + 1×212 + 1×211 + 1×210 + 0×29 + 0×28 + 1×27 + 1×26 + 0×25 + 1×24 + 0×23 + 0×22 + 1×21 + 1×20 = = 1×131072 + 1×65536 + 0×32768 + 0×16384 + 1×8192 + 1×4096 + 0×2048 + 0×1024 + 0×512 + 1×256 + 1×128 + 0×64 + 1×32 + 0×16 + 0×8 + 1×4 + 1×2 + 1×1 = 131072 + 65536 + 8192 + 4096 + 256 +128 +32 +4 + 2 + 1 = 209319

14

Exemplul 4 Să trecem numărul N = 209319(10) în baza 8 (sistemul octal). Se utilizează 8 simboluri (cifrele de la 0 până la 7). N : 8 = 209319 : 8 = 26164 rest 7 C0=26164 R0=a0=7 C0 : 8 = 26164 : 8 = 3270 rest 4 C1=3270 R1=a1=4 C1 : 8 = 3270 : 8 = 408 rest 6 C2=408 R2=a2=6 C2 : 8 = 408 : 8 = 51 rest 0 C3=51 R3=a3=0 C3 : 8 = 51 : 8 = 6 rest 3 C4=6 R4=a4=3 C4 8 = 6 : 8 =0 rest 6 C5=0 R5=a5=6 Am obţinut restul 0, deci procedeul se opreşte aici. Rezultă că numărul N=209319(10) se exprimă în baza 8 pe 6 cifre : N = 209319(10) = a5a4a3a2a1a0 (8)= 630647(8) Verificare : 630647(6) = 6×85 + 3×84 + 0×83 + 6×82 + 4×81 + 7×80 = = 6×32768 + 3×4096 + 0×512 + 6×64 + 4×8 + 7×1 = = 196608 + 12288 + 384 + 32 + 7 = 209319 Exemplul 5 Să trecem numărul N = 209319(10) în baza 16 (sistemul hexagesimal). Se utilizează 16 simboluri (cifrele de la 0 până la 9 şi literele mari A=10, B=11, C=12, D=13, E=14, F=15). N : 16 = 209319 : 16 = 13082 rest 7 C0=13082 R0=a0=7 C0 : 16 = 13082 : 16 = 817 rest 10 C1=817 R1=a1=10=A C1 : 16 = 817 : 16 = 51 rest 1 C2=51 R2=a2=1 C2 : 16 = 51 : 16 = 3 rest 3 C3=3 R3=a3=3 C3 : 16 = 3 : 16 = 0 rest 3 C4=0 R4=a4=3 Am obţinut restul 0, deci procedeul se opreşte aici. Rezultă că numărul N=209319(10) se exprimă în baza 16 pe 5 cifre : N = 209319(10) = a4a3a2a1a0 (16) = 331A7(16) Verificare : 331A7(19) = 3× 164 + 3×163 + 1×162 + A×161 + 7×160 = = 3×194 + 3×193 + 1×192 + 10×191 + 7×190 = = 3×65536 + 3×4096 + 1×256 + 10×16 + 7×1 = = 196608 + 12288 + 256 + 160 + 7 = 209319 Aplicând acelaşi procedeu, poate fi trecut numărul dat în orice bază (b≥2).

15

Pentru un control al celor învăţate, vom da reprezentarea aceluiaşi număr (209319) în toate bazele de numeraţie de la baza b=2 (sistemul binar, şi totodată cea mai mică bază posibilă) până la baza b=20 : N = 209319(10) = = 110011000110100111(2) = = 101122010120(3) = = 303012213(4) = = 23144234(5) = = 4253023(6) = = 1531155(7) = = 630647(8) = = 348116(9) = = 209319(10) = = 1332A0(11) = = A1173(12) = = 74C376(13) = = 563D5(14) = = 42049(15) = = 331A7(16) = = 28A47(17) = = 1HG0F(18) = = 1B9FF(19) = = 1635J(20) Exemplul 6 : trecerea reciprocă dintre bazele 2 şi 4 b1 = 2; b2 = 4 = 22; rezultă k = 2 (vom lucra deci pe câte 2 cifre în binar) N = 209319(10) = 110011000110100111(2)

Despărţim reprezentarea binară în grupe de câte 2 cifre (de la dreapta la stânga) : 11 00 11 00 01 10 10 01 11 şi reprezentăm fiecare grupă pe câte o singură cifră în baza 4 (pentru că am făcut un tabel de corespondenţe, putem să citim asta direct din tabel) ; obţinem succesiunea de cifre 303012213 Se observă cu uşurinţă că am obţinut chiar reprezentarea numărului N în baza 4. Procedeul poate fi aplicat şi invers : În reprezentarea numărului N în baza 4 N = 209319(10) = 303012213(4) înlocuim fircare cifră din baza 4 prin reprezentarea ei prin grupe de două cifre în baza 2 (binar) şi obţinem direct reprezentarea întregului număr N în baza 2 (binar). Exemplul 7 : trecerea reciprocă dintre bazele 2 şi 8 b1 = 2; b2 = 8 = 23; rezultă k = 3 (vom lucra deci pe câte 3 cifre în binar) N = 209319(10) = 110011000110100111(2)

16

Despărţim reprezentarea binară în grupe de câte 3 cifre (de la dreapta la stânga):

110 011 000 110 100 111 şi reprezentăm fiecare grupă pe câte o singură cifră în baza 8 (pentru că am făcut un tabel de corespondenţe, putem să citim asta direct din tabel) ; obţinem succesiunea de cifre 630647 Se observă cu uşurinţă că am obţinut chiar reprezentarea numărului N în baza 8. Procedeul poate fi aplicat şi invers : În reprezentarea numărului N în baza 4 N = 209319(10) = 630647(8) înlocuim fircare cifră din baza 8 prin reprezentarea ei prin grupe de trei cifre în baza 2 (binar) şi obţinem direct reprezentarea întregului număr N în baza 2 (binar). Exemplul 8 : trecerea reciprocă dintre bazele 2 şi 16 b1 = 2; b2 = 16 = 24; rezultă k = 4 (vom lucra deci pe câte 4 cifre în binar) N = 209319(10) = 110011000110100111(2)

Despărţim reprezentarea binară în grupe de câte 2 cifre (de la dreapta la stânga): 11 0011 0001 1010 0111 Datorită faptului că în prima grupă din stânga am obţinut doar două cifre, completăm prima grupă cu două cifre de zero la stânga (ceea ce, evident, nu modifică valoarea) 0011 0011 0001 1010 0111 şi reprezentăm fiecare grupă pe câte o singură cifră în baza 8 (pentru că am făcut un tabel de corespondenţe, putem să citim asta direct din tabel) ; obţinem succesiunea de cifre 331A7 Se observă cu uşurinţă că am obţinut chiar reprezentarea numărului N în baza 16. Procedeul poate fi aplicat şi invers : În reprezentarea numărului N în baza 16 N = 209319(10) = 331A7(16) înlocuim fircare cifră din baza 16 prin reprezentarea ei prin grupe de patru cifre în baza 2 (binar) şi obţinem direct reprezentarea întregului număr N în baza 2 (binar). Exemplul 9 : trecerea reciprocă dintre bazele 4 şi 16 b1 = 4; b2 = 16 = 42; rezultă k = 2 (vom lucra deci pe câte 2 cifre în baza 4) N = 209319(10) = 303012213(4)

Despărţim reprezentarea în baza 4 în grupe de câte 2 cifre (de la dreapta la stânga) : 3 03 01 22 13 Datorită faptului că în prima grupă din stânga am obţinut doar o cifră, completăm prima grupă cu o cifră de zero la stânga (ceea ce, evident, nu modifică valoarea) şi reprezentăm fiecare grupă pe câte o singură cifră în baza 16 (pentru că am făcut un tabel de corespondenţe, putem să citim asta direct din tabel) ; obţinem succesiunea de cifre 331A7 Se observă cu uşurinţă că am obţinut chiar reprezentarea numărului N în baza 16. Procedeul poate fi aplicat şi invers : În reprezentarea numărului N în baza 16

17

N = 209319(10) = 331A7(16) înlocuim fircare cifră din baza 16 prin reprezentarea ei prin grupe de două cifre în baza 4 (binar) şi obţinem direct reprezentarea întregului număr N în baza 4. Exemplul 10 : trecerea reciprocă dintre bazele 3 şi 9 Pentru ultima pereche de baze dintre cele pe care ni le-am propus, vom scrie mai întâi corespondenţa dintre bazele 10, 3 şi 9 (cu alte cuvinte, vom număra în aceste baze) : Baza 10 3 9 0 00 0 1 01 1 2 02 2 3 10 3 4 11 4 5 12 5 6 20 6 7 21 7 8 22 8 b1 = 3; b2 = 9 = 32; rezultă k = 2 (vom lucra deci pe câte 2 cifre în baza 3) N = 209319(10) = 101122010120(3)

Despărţim reprezentarea binară în grupe de câte 2 cifre (de la dreapta la stânga) : 10 11 22 01 01 20 şi reprezentăm fiecare grupă pe câte o singură cifră în baza 9 (pentru că am făcut un tabel de corespondenţe, putem să citim asta direct din tabel) ; obţinem succesiunea de cifre 348116 Se observă cu uşurinţă că am obţinut chiar reprezentarea numărului N în baza 9. Procedeul poate fi aplicat şi invers : În reprezentarea numărului N în baza 9 N = 209319(10) = 348116(9) înlocuim fircare cifră din baza 9 prin reprezentarea ei prin grupe de două cifre în baza 3 şi obţinem direct reprezentarea întregului număr N în baza 3.

18

SUGESTII TEME DE LABORATOR

A. Scrieţi pe o foaie de hârtie data naşterii, în formatul aaaallzi, fǎrǎ pauze sau caractere separatoare. Veţi folosi ca punct de plecare numǎrul de opt cifre astfel obţinut. (de exemplu, pentru o persoanǎ nǎscutǎ la data de 17 decembrie 1976, vom obţine numǎrul 19761217, iar pentru o persoanǎ nǎscutǎ la data de 9 mai 1980 vom obţine numǎrul 19800508). Treceţi numǎrul astfel obţinut (considerat cǎ este scris în baza 10) în toate bazele de la 2 pânǎ la 16, utilizând algoritmul cu împǎrţiri successive.

B. Verificaţi corectitudinea rezultatelor prin douǎ metode:

- utilizând aplicaţia Bazenum de pe Desktopul calculatorului - Efectuând trecerea numerelor obţinute la punctul A în baza 10, utilizând formula

polinomialǎ

C. Efectuaţi urmǎtoarele schimbǎri de bazǎ:

- 3333(8) în bazele 4, 12 şi 5 - ABC(16) în bazele 6, 7 şi 11

D. Pornind de la reprezentarea în baza 2 pe care a-ţi obţinut-o la punctual A., treceţi numǎrul direct în bazele 4, 8 şi 16, fǎrǎ a vǎ folosi de de baza 10

19

1.2 EFECTUAREA OPERAŢIILOR ÎN DIFERITE BAZE DE NUMERAŢIE Reprezentare numerelor fracţionare intr-o baza b (oarecare)

Să pornim tot de la un exemplu concret: Q = 209319,6875

ceea ce înseamnă, evident,

Q = 2 × 105 + 0 × 104 + 9 × 103 + 3 × 102 + 1 × 101 + 9 × 100 + + 6 × 10-1 + 8 × 10-2 + 7 × 10-3 + 5 × 10-4 în care apar şi puterile negative ale lui 10. Este uşor de generalizat acest lucru pentru reprezentarea unui număr fracţionar Q într-

o bază b oarecare :

Q = an×bn + an-1×bn-1 + … + a2×b2 + a1+b1 + a0×b0 + + a-1×b-1 + a-2×b-2 + a-3×b-3 + … + a-m+b-m = anan-1an-2…a2a1a0 , a-1a-2a-3…a-m (b) în care virgula (sau punctul, în sistemul anglo-saxon) desparte partea întreagă de partea fracţionară. Putem, evident, descompune numărul fracţionar Q în cele două componente ale sale – componenta întreagă şi componenta fracţionară Q = Q1 + Q2 unde Q1 = an×bn + an-1×bn-1 + … + a2×b2 + a1+b1 + a0×b0

= anan-1an-2…a2a1a0 (b) Q2 = a-1×b-1 + a-2×b-2 + a-3×b-3 + … + a-m+b-m = 0, a-1a-2a-3…a-m (b) Având în vedere că pentru partea înteagă dispunem deja de metode de trecere dintr-o bază în alta, rezultă că pentru a trece numărul Q dintr-o bază în alta mai avem nevoie doar de metode prin care să trecem un număr fracţionar fără parte întreagă în baza dorită. Pentru a trece un astfel de număr dintr-o bază b oarecare în baza 10, e sufficient să aplicăm formula polinomială. Exemplu Fie Q = 0,312(4)

20

Conform formulei, vom avea Q = 3 × 4-1 + 1 × 4-2 + 2 × 4-3 = 3 × 0,25 + 1 × 0,625 + 2 × 0,05625 = = 0,75 + 0,625 + 0,03125 = 0,84375(4) Pentru a trece numărul Qf din baza 10 într-o bază b oarecare, observăm următoarele : Qf × b = (a-1×b-1 + a-2×b-2 + a-3×b-3 + … + a-m+b-m = 0, a-1a-2a-3…a-m) × b = = a-1 + a-2×b-1 + a-3×b-2 + … + a-m+b-m+1 = a-1 + Qf1 adică, prin înmulţirea numărului de la care am pornit cu baza b, se obţine “trecerea” în faţa virgulei a coeficientului a-1 (prima cifră din reprezentarea în baza b a numărului strict fracţionar Qf. Neglijând acum această cifră şi repetând înmulţirea cu b, pentru numărul Qf1 obţinut la pasul anterior, vom obţine cea de-a doua cifră din reprezenterea numărului iniţial Qf – cifra a-2, şi aşa mai departe. Procedeul se opreşte când partea fracţionară devine zero, sau atunci când considerăm că am obţinut numărul cu precizia dorită. Să aplicăm regula obţinută pe un exemplu: să trecem numărul fracţionar Qf = 0,6875(10) în baza 2. 0,6875 × 2 = 1,375 a-1 = 1 0,375 × 2 = 0,75 a-2 = 0 0,75 × 2 = 1,5 a-3 = 1 0,5 × 2 = 1 a-4 = 1 şi, deoarece partea fracţionară a devenit egala cu zero, procedeul s-a încheiat ; am obţinut, deci : Qf = 0,6875(10) = 0,1011(2) Verificare :

0,1011(2) = 1× 2-1 + 0 × 2-2 + 1 × 2-3 + 1 × 2-4 =

= 1 × 0,5 + 0 × 0,25 + 1 × 0,125 + 1 × 0,0625 =

= 0,6875(10)

Vom obţine atunci :

Q = 209319,6875(10) = 110011000110100111,1011(2)

21

Observaţie importantă 1 : Dacă un număr fracţionar se poate reprezenta cu ajutorul unui număr finit de cifre (matematic exprimat : fără perioadă) într-o bază b1, aceasta nu înseamnă că el se va putea reprezenta tot cu ajutorul unui număr finit de cifre în orice altă bază b2. Deci, proprietatea de periodicitate a unui număr depinde de baza în care este exprimat. Exemplul 1 : Fie numărul 0,12(3). După cum se vede, el se reprezintă cu ajutorul a doar două cifre după virgulă, în baza 3. Să-l trecem în baza 10. Conform formulei polinomiale : 0,12(3) = 1 × 3-1 + 2 × 3-2 = 1 × 1/3 +2 × 1/9 = 5/9 = 0,55555... = 0,(5)(10) deci am obţinut un număr periodic în baza 10. Exemplul 2 : Fie numărul 0,7(10). După cum se vede, el se reprezintă cu ajutorul unei singure cifre după virgulă, în baza 10. Să-l trecem în baza 2. Conform metodei pe care o cunoaştem, aceasta se face prin înmulţirea succesivă cu 2. pasul 1 0,7 × 2 = 1,4 a-1 = 1 păstrăm 0,4 pasul 2 0,4 × 2 = 0,8 a-2 = 0 păstrăm 0,8 pasul 3 0,8 × 2 = 1,6 a-3 = 1 păstrăm 0,6 pasul 4 0,6 × 2 = 1,2 a-4 = 1 păstrăm 0,2 pasul 5 0,2 × 2 = 0,4 a-5 = 0 păstrăm 0,4 pasul 6 0,4 × 2 = 1,8 a-6 = 1 păstrăm 0,8 şi este uşor de observat că de aici înainte se vor repeta la nesfârşit paşii 2, 3, 4, 5 şi 6, procesul neterminându-se niciodată. Vom avea deci : 0,7(10) = 0,101100011000110001100... = 0,1(01100)(2) , adică un număr periodic în baza 2. Observaţie importantă 2 : Metodele de trecere reciprocă între două baze b1 şi b2 legate între ele printr-o relaţie de tipul b2 = b1

k vor rămâne valabile, având grijă doar să despărţim în grupe de câte k cifre de la virgulă spre stânga, pentru partea întreagă, respectiv spre dreapta, pentru partea fracţionară. Dacă, pentru partea întreagă, ultima grupă de cifre pe care le-am despărţit (cea mai din stânga) este formată din mai puţin de k cifre, se completează la stânga cu numărul necesar de zerouri. Dacă, pentru partea fracţionară, ultima grupă de cifre pe care le-am despărţit (cea mai din dreapta) este formată din mai puţin de k cifre, se completează la dreapta cu numărul necesar de zerouri.

22

Exemplu : Să trecem numărul 209319,6875(10) în baza 16, ţinând cont că avem deja reprezentarea sa în baza 2. deoarece 16 = 24, înseamnă că k = 4, deci trebuie să despărţim cifrele din reprezentarea în bază 2 în grupe de câte 4. 209319,6875(10) = 110011000110100111,1011(2) =

= 11 0011 0001 1010 0111 , 1011 = = 0011 0011 0001 1010 0111 , 1011 = = 331A7,B(16)

unde am completat grupa din stânga cu două zerouri (la stânga), ceea ce, evident, nu modifică valoarea numărului.

Efectuarea operaţiilor matematice într-o bază B oarecare

Adunarea numerelor în diferite baze de numeraţie

În orice bazǎ de numeraţie, adunarea se face dupǎ aceleaşi reguli ca şi în zecimal, cu observaţia cǎ cifra cea mai mare dintr-o bazǎ “b” va fi b − 1, adicǎ 9 în zecimal, 7 în octal, 1 în binar şi F în hexazecimal. Dacǎ prin adunarea a douǎ cifre de rang “i” se va obţine un rezultat mai mare decît b − 1, va apare un “transport” spre cifra de rang urmǎtor (i +1) iar pe poziţia de rang “i” va rǎmîne restul împǎrţirii rezultatului adunǎrii cifrelor de rang i + 1 la bazǎ. Transportul spre cifra de rang i + 1 va deveni o nouǎ unitate la suma cifrelor de rang i + 1.

În tabelul 1 este prezentat un exemplu de adunare a numerelor în binar, octal şi hexazecimal. Tabelul 1. Adunarea numerelelor în diferite baze de numeraţie.

Binar Octal Hexazecimal 11101+ 11010 --------- 110111

1702+ 2131 ------ 4033

1C6F + 1411 ------- 3080

Scǎderea numerelor în diferite baze de numeraţie

Ca şi în cazul adunǎrii, pentru scǎderea numerelor în binar, octal şi hexazecimal (ca de altfel în orice bazǎ) se aplicǎ regulile de la scǎderea în zecimal: dacǎ nu se pot scǎdea douǎ cifre de rang “i”(adicǎ cifra descǎzutului este mai micǎ decât a scǎzǎtorului) se

23

face “împrumut” o unitate din cifra de rang urmǎtor i + 1. În cazul în care cifra din care se face “împrumutul” este 0, se face împrumutul mai departe, din cifra de rang urmǎtor. în tabelul 2 este prezentat un exemplu de scǎdere a numerelor în binar, octal şi hexazecimal. Tabelul 2. Scǎderea numerelelor în diferite baze de numeraţie

Binar Octal Hexazecimal 10101 − 110 ------- 1111

322 − 131 ---- 171

AF9 − 13F ------ 9BA

Înmulţirea şi împǎrţirea numerelor în binar

Înmulţirea şi împǎrţirea numerelor în sistemul de numeraţie binar se efectueazǎ ca şi în cazul numerelor din sistemul zecimal.

În cazul înmulţirii în binar (ca şi în zecimal) 1 × 1 = 1, 0 × 0 = 0 iar 0 × 1 = 0.

Împǎrţirea numerelor în sistemul de numeraţie binar are acelaşi rezultat ca şi în zecimal, adicǎ un cât şi un rest.

În tabelul 3 este prezentat cîte un exemplu de înmulţire şi împǎrţire a numerelor în binar Tabelul 3. înmulţirea şi împǎrţirea numerelor în binar

înmulţire împǎrţire 1011× 1101 ------------- 1011 0000 1011 1011 10001111

11101|101 101 |101 ---- 0100 000 ------ 1001 101 ------- 100

Notǎ: Dacǎ în urma împǎrţirii a douǎ numere în binar rezultǎ un rest diferit de zero şi mai

mic decî împarţitorul, pentru obţinerea pǎrţii fracţionare se poate continua împǎrţirea astfel: se adauga cifra 0 la rest si virgula la cât si se continuǎ prin împǎrţirea restului la împarţitor, rezultatele fiind adǎugate la cât dupǎ virgulǎ

24

Reprezentarea binarǎ a numerelor negative

Pentru reprezentarea numerelor negative în binar, bitul din stânga reprezentǎrii numǎrului este folosit ca bit de semn. Astfel avem bitul de semn: 0 - pentru numere pozitive (+) 1 - pentru numere negative (-) Restul de N − 1 biţi sunt folosiţi pentru reprezentarea valorii Codul direct Numerele întregi se reprezintǎ prin valoare absolutǎ şi semn. în cazul codului direct, pentru numerele negative bitul de semn este 1 iar ceilalţi n − 1 biţi servesc pentru reprezentarea valorii absolute a numǎrului.

De exemplu, numǎrul N = −5 se poate reprezenta pe 8 biţi astfel: 10000101(2), unde valoarea absolutǎ este 0000101(2) iar primul bit este bitul de semn. Domeniul de reprezentare în cazul codului direct va fi: • 2n−1 valori pozitive de la 0 la 2n−1 − 1 • 2n−1 valori negative de la −(2n−1 − 1) la 0

Se poate observa cǎ existǎ douǎ reprezentǎri ale lui zero, respectiv 00000000 şi 10000000, iar numǎrul maxim şi numǎrul minim dintr-un domeniu au aceeaşi valoare absolutǎ, respectiv 01111111 şi 11111111 Codul invers

Pentru numerele negative reprezentate în codul invers (complement faţǎ de 1) bitul de semn este 1 iar ceilalţi n − 1 biţi servesc la reprezentarea valorii absolute negate a numǎrului de reprezentat. Negarea se realizeazǎ la nivel de bit: biţii “0” devin “1” iar biţii “1” devin “0”.

De exemplu, numǎrul N = −5 se va reprezenta în codul invers astfel:

11111010(2), unde 1111010(2) reprezintǎ valoarea absolutǎ negatǎ a numǎrului 0000101(2). Matematic, complementul faţǎ de 1 al unui numǎr negativ N care se reprezintǎ pe n biţi se defineşte astfel

C1(N ) = 2n − 1 − V

25

unde n - numǎrul de biţi al reprezentǎrii V - valoarea absolutǎ a numǎrului de reprezentat Codul complementar

Pentru reprezentarea numerelor negative în codul complementar (complement faţǎ de 2) se aplicǎ urmǎtoarea regulǎ de complementare: se reprezintǎ numǎrul în valoare absolutǎ, apoi se inverseazǎ bit cu bit(inclusiv bitul de semn care devine 1); la rezultatul obţinut se adunǎ “1”. Deci, complementul faţǎ de 2 se obţine din complementul faţǎ de 1 la care se adunǎ “1”. De exemplu, numǎrul N = −5 în codul complementar va avea valoarea (inversare) 11111010 + 1 11111011 Din punct de vedere matematic, complementul faţǎ de 2 al unui numǎr negativ N este

C2(N ) = 2n − V unde: n - numǎrul de biţi al reprezentǎrii V - valoarea absolutǎ a numǎrului de reprezentat

În cazul codului complementar bitul din stânga rǎmâne tot timpul bit de semn. Avantajul reprezentǎrii în complement faţǎ de 2 este cǎ, adunînd un numǎr cu complementul sǎu faţǎ de 2, rezultatul este 0 (ignorând depǎşirea) ceea ce nu este valabil în cazul celorlalte reprezentǎri. Codul complementar este cel mai utilizat în reprezentarea numerelor algebrice în calculator

26

SUGESTII TEME DE LABORATOR 1) Sǎ se efectueze urmǎtoarele operaţii: a) 1101001(2) + 1010111(2) b) 1000100(2) + 1001111(2) c) 1733(8) + 234(8) d) 1022(8) + 7721(8) e) AC 97(16) + 33ED(16) f) 922A(16) + 4522(16) g) 10110(2) − 1101(2) h) 11101011(2) − 11101(2) i) 7100(8) − 324(8) j) 1021(8) − 261(8) k) AA31(16) − 2F C(16) l) F D124(16) − AF 3C(16) 2) Sǎ se efectueze urmǎtoarele operaţii:: a) 110100110(2) × 11001(2) b) 100101101(2) × 10011(2) c) 111010001(2) × 1110(2) d) 110111101(2) × 101(2) e) 10111(2) : 110(2) f ) 10101(2) : 100(2) g) 110011(2) : 1101(2) h) 100010(2) : 101(2) 3) Sǎ se reprezinte urmǎtoarele numere în sistemul binar, utilizînd codul direct, invers şi complementar:

a) -314 b) -666 c) -2111 d) -34 e) -255 f) -256 g) -100 h) -1

27

2. REPREZENTAREA DATELOR ÎN CALCULATOR

Reprezentarea numerelor în virgulă mobilă

În cazul reprezentării în forma cu virgulă fixă, poziţia virgulei, stabilită prin proiectare, nu mai poate fi schimbată, cu toate că virgula nu mai este reprezentată fizic în calculator. Dacă virgula este amplasată după cifra de semn, se lucrează cu numere fracţionare subunitare. Deoarece nu toate numerele sunt subunitare, pentru a le aduce la această formă trebuie executate o serie de operaţii de scalare (multiplicare cu un anumit factor de scală) sau deplasare, ataşând numerelor factori de scală. Evidenţa acestora trebuie realizată prin program, motiv pentru care acestea se complică.

Această dificultate se poate rezolva utilizând reprezentarea în virgulă mobilă

(virgulă flotantă). În acest caz, factorul de scală devine o parte a cuvântului din calculator, poziţia virgulei variind pentru fiecare număr în mod automat, ceea ce conduce la simplificarea programelor.

Un număr reprezentat în virgulă mobilă (VM) are două componente. Prima

componentă este mantisa, care indică valoarea exactă a numărului într-un anumit domeniu, fiind reprezentată de obicei ca un număr fracţionar cu semn. A doua componentă este exponentul, care indică ordinul de mărime al numărului. Considerând un număr N, reprezentarea acestuia în VM poate avea forma următoare:

N = ± M⋅B ±E (3.1)

unde M este mantisa, B este baza sistemului de numeraţie, iar E este exponentul.

Această reprezentare poate fi memorată într-un cuvânt binar cu trei câmpuri: semnul, mantisa şi exponentul. De exemplu, presupunând un cuvânt de 32 de biţi, o asignare posibilă a biţilor la fiecare câmp poate fi următoarea:

Aceasta este o reprezentare în mărime şi semn, deoarece semnul are un câmp separat faţă de restul numărului. Câmpul de semn constă dintr-un bit care indică semnul numărului: 0 pentru un nu- măr pozitiv şi 1 pentru un număr negativ. Nu există un câmp rezervat pentru baza B, deoarece această bază este implicită şi ea nu trebuie memorată, fiind aceeaşi pentru toate numerele.

28

De obicei, în locul exponentului se reprezintă o valoare numită caracteristică, care se obţine prin adunarea unui deplasament la exponent, astfel încât să rezulte întotdeauna o valoare pozitivă. Deci, nu se rezervă un câmp separat pentru semnul exponentului. Caracteristica C este deci exponentul deplasat:

C = E + deplasament (3.2)

Valoarea reală a exponentului se poate afla prin scăderea deplasamentului din

caracteristica numărului. De exemplu, dacă pentru caracteristică se rezervă un câmp de 8 biţi, valorile caracteristicii pot fi cuprinse între 0 şi 255. Cu un deplasament de 128 (80h), exponentul poate lua valori între –128 şi +127, fiind negativ dacă C < 128, pozitiv dacă C > 128, şi 0 dacă C = 128. Exponentul este deci reprezentat în exces 128.

Reprezentarea cu ajutorul caracteristicii va fi următoarea:

În acest caz, semnul mantisei este acelaşi cu semnul numărului.

Unul din avantajele utilizării exponentului deplasat constă în simplificarea operaţiilor executate cu exponentul, datorită lipsei exponenţilor negativi. Al doilea avantaj se referă la modul de reprezentare al numărului zero.

Mantisa numărului zero are cifre de 0 în toate poziţiile. Exponentul numărului

zero poate avea, teoretic, orice valoare, rezultatul fiind tot zero. În unele calculatoare, dacă un rezultat are mantisa zero, exponentul este lăsat la valoarea pe care o are în momentul respectiv, rezultând un “zero impur”.

La majoritatea calculatoarelor, se recomandă ca numărul zero să aibă cel mai mic

exponent posibil, rezultând astfel un “zero pur”. În cazul exponenţilor nedeplasaţi, exponentul cu cea mai mică valoare este cel mai mic număr negativ pe care îl poate avea exponentul, iar în cazul exponenţilor de- plasaţi, această valoare este 0.

Deci, prin utilizarea caracteristicii, reprezentarea în VM a numărului zero este

aceeaşi cu reprezentarea în VF, adică toate poziţiile sunt 0. Aceasta înseamnă că se pot utiliza aceleaşi circuite pentru testarea valorii zero.

În reprezentarea anterioară, mantisa constă din 23 de biţi. Deşi virgula binară nu

este repre- zentată, se presupune că ea este aşezată înaintea bitului c.m.s. al mantisei. De exemplu, dacă B = 2, numărul 1,75 poate fi reprezentat sub mai multe forme:

29

Pentru simplificarea operaţiilor cu numere în VM şi pentru creşterea preciziei

acestora, se utili- zează reprezentarea sub forma normalizată. Un număr în VM este normalizat dacă bitul c.m.s. al mantisei este 1. Din cele două reprezentări ale numărului 1,75 ilustrate anterior, prima este cea normalizată.

Deoarece bitul c.m.s. al unui număr normalizat în VM este întotdeauna 1, acest bit

nu este de obicei memorat, fiind un bit ascuns la dreapta virgulei binare. Aceasta permite ca mantisa să aibă un bit semnificativ în plus. Astfel, câmpul de 23 de biţi este utilizat pentru memorarea unei mantise de 24 de biţi cu valori între 0,5 şi 1,0.

Cu această reprezentare, Figura 2.1 indică gama numerelor care pot fi reprezentate

într-un cu- vânt de 32 de biţi. Dacă se utilizează reprezentarea în C2, se pot reprezenta toate numerele întregi între –231 şi 231–1, cu un total de 232 numere diferite. Pentru formatul prezentat, se pot reprezenta numere în urmă- toarele domenii (Figura 3.1):

• Numere negative între –(1–2 -24) ⋅ 2127 şi –0,5 ⋅ 2-128

• Numere pozitive între 0,5 ⋅ 2-128 şi (1–2-24) ⋅ 2127

Figura 3.1. Numere reprezentabile în formate tipice de 32 de biţi.

Există cinci regiuni care nu sunt cuprinse în aceste domenii:

• Numere negative mai mici decât – (1–2-24) ⋅ 2127, apariţia acestora determinând

o depăşire su- perioară negativă

30

• Numere negative mai mari decât –0,5 ⋅ 2-128, care determină o depăşire inferioară negativă

• Zero

• Numere pozitive mai mici decât 0,5 ⋅ 2-128, care determină o depăşire inferioară pozitivă

• Numere pozitive mai mari decât (1–2-24) ⋅ 2127, care determină o depăşire superioară pozitivă

În unele cazuri, bitul ascuns se presupune poziţionat la stânga virgulei binare.

Astfel, mantisa memorată M va reprezenta de fapt valoarea 1,M. În acest caz, numărul normalizat 1,75 va avea urmă- toarea formă:

Presupunând că bitul ascuns este poziţionat la stânga virgulei binare în formatul

prezentat, un număr normalizat diferit de zero reprezintă următoarea valoare:

(–1)S∗ (1,M) ∗ 2E–128 (3.3)

unde S indică bitul de semn.

În acest format se pot reprezenta numere în următoarele domenii:

• Numere negative între –[1 + (1 – 2–23)] ∗ 2127 şi – 1,0 ∗ 2–128

• Numere pozitive între 1,0 ∗ 2–128 şi [1 + (1 – 2–23)] ∗ 2127

Problema care apare în cazul formatului prezentat este că nu există o reprezentare pentru valoarea zero. Aceasta deoarece valoarea zero nu poate fi normalizată. Totuşi, reprezentările în VM cuprind de obicei o combinaţie specială de biţi pentru reprezentarea valorii zero.

Depăşirea superioară apare atunci când exponentul depăşeşte valoarea maximă, de

exemplu peste 127 în cazul formatului prezentat. Depăşirea inferioară apare atunci când exponentul are o valoare negativă prea mică, de exemplu sub –128. În cazul depăşirii inferioare, rezultatul se poate apro- xima cu 0. Coprocesoarele matematice au anumite mecanisme pentru detectarea, semnalarea şi tratarea depăşirii superioare şi a celei inferioare.

Pentru alegerea unui format în VM trebuie realizat un compromis între dimensiunea

mantisei şi cea a exponentului. Creşterea dimensiunii mantisei va conduce la creşterea preciziei numerelor, iar creşterea dimensiunii exponentului va conduce la creşterea domeniului numerelor care pot fi reprezentate. Singura cale de a creşte atât precizia,

31

cât şi domeniul numerelor, este de a utiliza un număr mai mare de biţi pentru reprezentare. Cele mai multe calculatoare utilizează cel puţin două formate, în simplă precizie (de exemplu pe 32 de biţi), şi dublă precizie (de exemplu pe 64 de biţi).

Reprezentarea numerelor în formatul IEEE 754

IEEE (Institute of Electrical and Electronics Engineers) a dezvoltat un standard pentru reprezentarea numerelor în VM şi operaţiile aritmetice în această reprezentare. Scopul era facilitarea portabilităţii programelor între diferite calculatoare. Standardul IEEE 754 a fost publicat în 1985. Cele mai multe coprocesoare aritmetice, printre care şi cele Intel pentru familia de microprocesoare 80x86, se conformează acestui standard.

Standardul defineşte trei formate:

• Formatul scurt (precizie simplă): 4 octeţi • Formatul lung (precizie dublă): 8 octeţi • Formatul temporar (precizie extinsă): 10 octeţi

Baza implicită este 2. Formatul scurt şi cel lung sunt prezentate în continuare.

S indică semnul numărului. C reprezintă exponentul deplasat, deci caracteristica,

pentru care se rezervă 8 biţi în formatul scurt şi 11 biţi în formatul lung. Pentru formatul scurt, deplasamentul este 127 (7Fh), iar pentru formatul lung deplasamentul este 1023 (3FFh). Valorile minime (0) şi cele maxime (255, respectiv 2047) ale caracteristicii nu sunt utilizate pentru numerele normalizate, ele având utilizări speciale.

Bitul ascuns este utilizat şi la standardul IEEE 754, dar mantisa este reprezentată

într-un mod diferit. Ea constă dintr-un bit implicit cu valoarea 1 (partea întreagă), virgula binară implicită, şi apoi cei 23, respectiv 52 de biţi ai fracţiei. Dacă toţi biţii fracţiei sunt 0, mantisa este 1,0; dacă toţi biţii fracţiei sunt 1, mantisa este cu puţin mai mică decât 2,0. Deci:

1,0 <= M < 2,0

Mantisa are valoarea: M = 1,Fracţie

iar valoarea numărului în precizie simplă (NS), respectiv în precizie dublă (ND) este:

NS = (–1)s ⋅ M ⋅ 2C-127 (3.4)

ND = (–1)s ⋅ M ⋅ 2C-1023 (3.5)

32

Gama numerelor care pot fi reprezentate în precizie simplă este cuprinsă între aproximativ 2,2×10-38 şi 3,4×1038, iar cea a numerelor reprezentate în precizie dublă este cuprinsă între 2,2×10-308 şi 1,7×10308.

Formatul temporar este utilizat pentru reprezentarea numerelor în cadrul coprocesoarelor aritmetice, în scopul reducerii erorilor datorate rotunjirilor. Acest format este următorul:

Bitul 63 reprezintă partea întreagă a mantisei, care nu este implicită. Numerele în formatul temporar nu sunt întotdeauna normalizate, de aceea nu încep în mod obligatoriu cu un bit de 1. De aceea acest bit este reprezentat explicit, fiind notat cu I în cadrul formatului. Deplasamentul exponentului este 16.383, iar valoarea numărului (NE) este:

NE = (–1)s * M * 2C-16383 (3.6)

Una din problemele care apare la calculele cu numere în VM se referă la modul de tratare al depăşirilor inferioare şi superioare, şi la reprezentarea valorilor nedefinite. În acest scop, pe lângă numerele normalizate, standardul mai permite şi reprezentări ale unor valori speciale, pentru care sunt rezervate valorile 0 şi 255 ale exponentului. Unele din aceste valori speciale sunt prezentate în continuare.

În cazul obţinerii unui rezultat cu o valoare mai mică decât numărul normalizat cel mai mic posibil, în mod obişnuit rezultatul este setat la zero şi operaţiile se continuă, sau se semnalează o eroare de depăşire inferioară. Nici una din aceste soluţii nu este satisfăcătoare, astfel încât standardul permite utilizarea numerelor nenormalizate (denormalizate), care au caracteristica 0, iar fracţia diferită de 0.

Pentru valoarea zero, atât caracteristica, cât şi fracţia, sunt egale cu 0. Există două

reprezentări pentru valoarea 0, în funcţie de bitul de semn: +0, respectiv -0. Bitul de la stânga punctului binar este implicit 0 în loc de 1.

Pentru cazul în care apare o depăşire superioară, există o reprezentare specială

33

pentru infinit, constând din caracteristica formată din biţi de 1 (255 pentru formatul scurt), şi o fracţie egală cu 0. Valoarea infinit se poate utiliza ca operand, de exemplu:

∞ + n = ∞ n / ∞ = 0 n / 0 = ∞

Astfel, utilizatorul poate decide dacă va trata depăşirea superioară ca o condiţie de eroare, sau va continua calculele cu valoarea infinit.

Pentru indicarea diferitelor condiţii de excepţie, ca în cazul nedefinirilor de forma ∞/∞, ∞ * 0,

0/∞, s-a prevăzut un format special NaN (Not a Number). Caracteristica este formată din biţi de 1, iar fracţia este diferită de 0.

Exemple

1) Care este reprezentarea binară a numărului –0,75 în simplă precizie?

Numărul –0,75 poate fi scris ca – 3/4 sau – 0,11 în binar. Notaţia ştiinţifică a numărului este

-0,11×20, iar forma normalizată a acestei notaţii este – 1,1×2–1. Caracteristica va fi –1 + 127 = 126 (7Eh). Reprezentarea numărului în precizie simplă este deci:

2) Care este numărul zecimal reprezentat de următorul cuvânt?

Bitul de semn este 1, câmpul rezervat caracteristicii conţine 81h = 129, iar câmpul fracţiei conţine 1 × 2–2 = 0,25. Valoarea numărului este:

(– 1)1 × 1,25 × 2(129–127) = – 1,25 × 22 = – 1,25 × 4 = – 5,0

34


A. Reprezentaţi în formatul IEEE 754 cu precizie simplă următoarele numere zecimale:

a) 1; b) –1; c) 5; d) –5; e) 35,4; f) –35,4; g) 2,6; h) -192

Scrieţi rezultatele în hexazecimal. B. Reprezentaţi în formatul IEEE 754 cu precizie dublă următoarele numere zecimale:

a) 1; b) 1,5; c) 2,5; d) 5; e) 35,4; f) –35,4

C. Scrieţi numerele zecimale corespunzătoare următoarelor reprezentări în formatul IEEE 754 cu precizie simplă:

a) 41 8A 1E 94; b) 41 36 66 6A; c) BE CC CC CB; d) BD AB 40 C0

35

3. ELEMENTE DE TEORIA CODURILOR

6.1 Coduri binar-zecimale

Aceste coduri se utilizează pentru codificarea cifrelor zecimale. Pentru codificarea fiecăreia din cele 10 cifre sunt necesari 4 biţi; din cele 16 valori posibile, 6 vor fi neutilizate. Prin stabilirea unor corespondenţe între mulţimea cifrelor zecimale şi mulţimea celor 16 cuvinte de 4 biţise obţin numeroase posibilităţi de codificare ( A10 ).

Dintre numeroasele coduri posibile se utilizează practic doar o mică parte.

Codurile utilizate se împart în coduri ponderate şi neponderate.

În cazul codurilor ponderate, o cifră zecimală este exprimată printr-o combinaţie de 4 cifre binare, în care fiecărei cifre i se asociază o anumită pondere. Ponderile pot fi pozitive sau negative. Valoarea cifrei zecimale se obţine prin suma biţilor din cod, fiecare bit fiind multiplicat cu valoarea ponderii asociate.

Considerând un cod format din biţii b0, b1, b2, b3, ponderile asociate acestora fiind

p0, p1, p2, respectiv p3, valoarea cifrei zecimale codificate este:

N = p0b0 + p1b1 + p2b2 + p3b3

Ponderile fiecărui bit reprezintă valoarea corespunzătoare din denumirea codului. Pentru ponderile de sus, codul are denumirea p3p2p1p0. În Tabelul 1 se prezintă exemple de coduri ponderate de 4 biţi mai des utilizate.

Nr. zecimal

8421

2421

6423

8421 0 0000 0000 0000 0000 1 0001 0001 0101 0111 2 0010 0010 0010 0110 3 0011 0011 1001 0101 4 0100 0100 0100 0100 5 0101 1011 1011 1011 6 0110 1100 0110 1010 7 0111 1101 1101 1001 8 1000 1110 1010 1000 9 1001 1111 1111 1111

Tabelul 1. Coduri binar-zecimale ponderate de 4 biţi

36

Exemple

01018421 = 8⋅0 + 4⋅1 + 2⋅0 + 1⋅1 = 5 1010 = 8⋅1 + 4⋅0 + (-2)⋅1 + (-1)⋅0 = 8–2 = 6

8421

În cazul codului 8421, deoarece fiecare bit are ponderea numărării în binar (20, 21, 22, 23), iar cuvintele de cod reprezintă numerele succesive în sistemul binar natural, codul se mai numeşte cod binar-zecimal natural (NBCD – Natural Binary Coded Decimal). În mod obişnuit, acest cod se numeşte, impropriu, cod BCD.

În cazul codului 2421, numit şi cod Aiken (după numele prof. Howard Aiken,

care a realizat calculatorul MARK I), primele 5 cifre zecimale (0 – 4) au aceeaşi exprimare ca şi în codul 8421. Cifra zecimală 5 poate fi exprimată fie prin 0101, fie prin 1011. Deci, reprezentarea unor cifre zecimale nu este unică, această proprietate fiind valabilă şi pentru alte coduri. Pentru codificare s-a ales reprezentarea 1011, deoarece codul pentru cifra 5 se poate obţine atunci prin complementarea codului pentru cifra 4. Aceeaşi regulă se poate aplica pentru obţinerea codului cifrei 6 din codul cifrei 3, a codului cifrei 7 din codul cifrei 2 etc.

Codurile care au această proprietate se numesc coduri autocomplementare. Un cod este autocomplementar dacă cuvântul de cod al complementului faţă de 9 al cifrei N (deci 9 – N) se poate obţine din codul cifrei N, prin complementarea fiecăruia din cei 4 biţi. De exemplu, codul 8421 nu este autocomplementar, iar codurile 2421 , 6423 , 8421 sunt autocomplementare.

ondiţia necesară pentru ca un cod ponderat să fie autocomplementar este ca suma ponderilor să fie egală cu 9. Autocomplementaritatea constituie un avantaj în construcţia unui dispozitiv aritmetic care lucrează cu numere zecimale reprezentate în codul respectiv.

Observaţie. În forma internă, numerele sunt reprezentate şi prelucrate fie sub formă binară, fie codificate printr-un cod binar-zecimal. Trebuie sesizată diferenţa dintre conversia unui număr zecimal în echivalentul său binar şi codificarea binar-zecimală a numărului zecimal. De exemplu:

1210 = 11002 (4 biţi) 1210 = (0001 0010)BCD (8 biţi)

Codurile neponderate pot avea un număr mai mare de 4 biţi. Codurile cele mai

uzuale sunt prezentate în Tabelul 2.

Nr. zecimal Exces 3 2 din 5 Gray 0 0011 00011 0000 1 0100 00101 0001 2 0101 00110 0011 3 0110 01001 0010 4 0111 01010 0110 5 1000 01100 0111 6 1001 10001 0101 7 1010 10010 0100 8 1011 10100 1100 9 1100 11000 1101

37

Codul Exces 3 este autocomplementar, şi derivă din codul 8421 (BCD) prin adăugarea la fiecare cifră a valorii 3. Utilizând acest cod, se poate face distincţie între lipsa unei informaţii înscrise într-un registru sau locaţie de memorie şi înscrierea valorii zero (0000 reprezintă lipsa unei informaţii, iar zero este codificat prin 0011).

Codul 2 din 5 se utilizează pentru reprezentarea numerelor zecimale printr-un grup

de 5 biţi. Denumirea derivă din faptul că fiecare cifră zecimală codificată în binar conţine doi biţi de 1 din cei 5 biţi.

Codul Gray are proprietatea de adiacenţă, adică trecerea de la o cifră zecimală la

următoarea sau precedenta necesită modificarea unui singur bit din cuvântul de cod. Este util pentru mărimile care cresc sau descresc succesiv.

6.2 Coduri detectoare de erori

Transmiterea informaţiilor prin medii influenţate de zgomote poate fi însoţită de introducerea unor erori. Verificarea transmiterii corecte a informaţiilor se poate realiza cu ajutorul unor coduri speciale numite coduri detectoare de erori.

Una din metodele de detectare a unei erori o constituie detectarea combinaţiilor interzise. În cazul codurilor binar-zecimale, deoarece se utilizează 10 din cele 16 combinaţii posibile de 4 biţi, celelalte combinaţii nu trebuie să apară. Aceste combinaţii interzise se pot utiliza pentru detectarea erorii. Dacă, de exemplu, în codul BCD 1000 apare o singură eroare, codul poate fi transformat în 0000, 1100, 1010 sau 1001. Dintre aceste combinaţii, a doua şi a treia constituie combinaţii interzise, astfel încât în aceste cazuri eroarea poate fi detectată. Celelalte combinaţii nu sunt interzise, deci în cazurile respective eroarea nu poate fi detectată.

O modalitate de creştere a probabilităţii de detectare a erorilor constă în folosirea

mai multor combinaţii interzise, care pot fi disponibile dacă codurile au mai mult de 4 biţi. De exemplu, în codul 2 din 5 apare o eroare ori de câte ori o cifră codificată are mai mult sau mai puţin de doi biţi de 1. Astfel, se pot detecta erori multiple.

O altă metodă pentru detectarea erorilor constă în folosirea unor biţi suplimentari

de verificare. De exemplu, un cod de n biţi poate fi format din m biţi de date şi r biţi redundanţi de verificare (n = m + r). Fiind date două cuvinte de cod, de exemplu 1000 1001 şi 1011 0001, se poate determina numărul biţilor care diferă. În acest caz, există 3 biţi care diferă. Pentru determinarea numărului de biţi care diferă, se efectuează suma modulo 2 între cele două cuvinte de cod, şi se calculează numărul biţilor de 1 ai rezultatului. Numărul poziţiilor în care două cuvinte de cod diferă reprezintă distanţa Hamming. Dacă între două cuvinte de cod se află o distanţă Hamming d, sunt necesare d erori de câte un singur bit pentru trecerea de la un cod la al doilea cod.

Proprietăţile de detectare a erorilor ale unui cod depind de distanţa sa Hamming.

Pentru detectarea a d erori de câte un singur bit, este necesar un cod cu distanţa d+1, deoarece cu un asemenea cod nu există posibilitatea ca d erori de un singur bit să modifice un cuvânt de cod valid într-un alt cuvânt de cod valid.

38

Un exemplu simplu de cod detector de erori este un cod care conţine un bit suplimentar numit bit de paritate. Acest bit se poate alege astfel încât numărul total al biţilor având valoarea 1 în exprimarea numărului să fie par, respectiv impar. Dacă se utilizează paritatea pară, notând cu x3x2x1x0 biţii cifrei zecimale şi cu p bitul de paritate, valoarea bitului de paritate determină ca suma modulo 2 a valorii tuturor biţilor să fie 0:

x3 ⊕ x2 ⊕ x1 ⊕ x0 ⊕ p = 0 de unde rezultă p = x3 ⊕ x2 ⊕ x1 ⊕ x0 Dacă se alege paritatea impară, trebuie ca:

x3 ⊕ x2 ⊕ x1 ⊕ x0 ⊕ p = 1 p = x3 ⊕ x2 ⊕ x1 ⊕ x0 ⊕ 1

Tabelul 2 Codul 8421 cu paritate pară

Nr. zecimal Cod 0 0 0000 1 1 0001 2 1 0010 3 0 0011 4 1 0100 5 0 0101 6 0 0110 7 1 0111 8 1 1000 9 1 1001

Un asemenea cod are distanţa 2, deoarece o eroare de un singur bit produce un cuvânt de cod cu paritatea eronată. La transmisia datelor se adaugă bitul de paritate pară sau impară, iar la recepţie se determină dacă paritatea este aceeaşi cu cea de la transmisie.

Codurile 8421 cu paritate pară ale cifrelor zecimale sunt indicate în Tabelul 2.

6.3 Coduri corectoare de erori

Verificarea parităţii nu poate detecta apariţia erorilor duble, deoarece aceste erori nu modifică suma modulo 2 a biţilor. Există coduri mai complexe, numite coduri corectoare de erori, care permit şi corectarea unui bit eronat sau a mai multor biţi eronaţi. Aceste coduri sunt utile atunci când retransmisia informaţiei nu este posibilă, sau necesită un timp care nu ar fi acceptabil.

Presupunem un cod cu m biţi de date şi r biţi de verificare, cod care permite

corectarea tuturor erorilor de un singur bit. Fiecăruia din cele 2m cuvinte de cod valide îi corespund n cuvinte de cod ilegale cu distanţa 1. Acestea se formează prin inversarea

39

sistematică a fiecăruia din cei n biţi. Fiecare din cele 2m cuvinte valide necesită n+1 combinaţii de biţi dedicate pentru cuvântul respectiv. Deoarece numărul total al combinaţiilor de biţi este 2n, trebuie ca (n+1)2m ≤ 2n. Utilizând relaţia n = m + r, această cerinţă devine (m + r + 1) ≤ 2r. Fiind dat m, aceasta impune o limită inferioară asupra numărului biţilor de verificare necesari pentru corectarea erorilor de un singur bit. De exemplu, pentru un cuvânt de m = 4 biţi, numărul minim al biţilor de verificare este r = 3, iar pentru un cuvânt de m = 8 biţi, numărul minim al biţilor de verificare este r = 4.

Aceste limite teoretice pot fi atinse utilizând o metodă datorată lui Richard

Hamming. Metoda poate fi utilizată pentru construirea codurilor corectoare de erori pentru cuvinte de cod de orice dimensiune. Într-un cod Hamming, se adaugă r biţi de paritate la un cuvânt de m biţi, rezultând un nou cuvânt cu lungimea de m + r biţi. Biţii sunt numerotaţi începând cu 1 (şi nu cu 0), bitul 1 fiind bitul c.m.s. Toţi biţii ai căror număr este o putere a lui 2 sunt biţi de paritate, restul biţilor fiind utilizaţi pentru date. De exemplu, în cazul unui cuvânt de 4 biţi, biţii 1, 2 şi 4 sunt biţi de paritate. În total, cuvântul de cod va conţine 7 biţi (4 de date şi 3 de paritate). În exemplul prezentat se va utiliza în mod arbitrar paritatea pară.

Fiecare bit de paritate verifică anumite poziţii de biţi. Aceste poziţii sunt ilustrate

în Figura 1, unde prin pătrate s-a indicat poziţia biţilor de paritate, iar prin cercuri s-a indicat poziţia biţilor de informaţie.

Figura 2. Construcţia codului Hamming pentru valoarea binară 0101 prin adăugarea a trei biţi de paritate.

Poziţiile de biţi verificate de biţii de paritate sunt următoarele: Bitul 1 de paritate verifică biţii 1, 3, 5, 7. Bitul 2 de paritate verifică biţii 2, 3, 6, 7. Bitul 4 de paritate verifică biţii 4, 5, 6, 7.

În general, bitul b este verificat de acei biţi b1, b2, …, bj astfel încât b1 + b2 + …

+ bj = b. De exemplu, bitul 5 este verificat de biţii 1 şi 4 deoarece 1 + 4 = 5. Bitul 6 este verificat de biţii 2 şi 4 deoarece 2 + 4 = 6.

Se consideră exprimarea în cod 8421 a cifrei zecimale 5 (0101). Bitul 1 de paritate va trebui să

determine un număr par de cifre de 1 pentru poziţiile 1, 3, 5 şi 7, deci va avea valoarea 0. Similar se determină valoarea bitului 2 de paritate, care va avea valoarea 1, şi a bitului 4 de paritate, care va avea valoarea 0.

Dacă transmiterea cifrei zecimale se realizează corect, toţi biţii de paritate verifică

în mod corect paritatea. Dacă apare o eroare de transmisie, fie la un bit de paritate, fie la un

40

bit de informaţie, acest cod poate corecta o singură eroare. De exemplu, presupunem că a apărut o eroare la transmiterea bitului de informaţie din poziţia 6. Codul recepţionat va fi 0100111 în loc de 0100101. Se verifică biţii de paritate, cu următoarele rezultate:

Bitul 1 de paritate este corect (biţii 1, 3, 5, 7 conţin doi biţi de 1) Bitul 2 de paritate este incorect (biţii 2, 3, 6, 7 conţin trei biţi de 1) Bitul 4 de paritate este incorect (biţii 4, 5, 6, 7 conţin trei biţi de 1)

Bitul incorect trebuie să fie unul din biţii testaţi de bitul 2 de paritate (2, 3, 6 sau 7).

Deoarece bitul 4 de paritate este incorect, unul din biţii 4, 5, 6 sau 7 este incorect. Bitul eronat este unul din cei care se află în ambele liste, deci poate fi bitul 6 sau 7. Bitul 1 de paritate fiind corect, rezultă că şi bitul 7 este corect. Bitul eronat este deci bitul 6, şi valoarea acestui bit trebuie inversată. În acest fel, eroarea poate fi corectată.

O metodă simplă pentru determinarea bitului eronat este următoarea. Se calculează

biţii de paritate, şi dacă toţi biţii sunt corecţi, înseamnă că nu există eroare (sau există mai mult de o eroare). Se atribuie apoi biţilor de paritate ponderile 1, 2, respectiv 4, şi se adună ponderile biţilor de paritate eronaţi. Suma rezultată reprezintă poziţia bitului eronat. De exemplu, dacă biţii de paritate 2 şi 4 sunt eronaţi, bitul eronat este bitul 6.

6.4 Coduri alfanumerice

Datele alfanumerice conţin cifre, litere şi semne speciale, numite, în general, caractere. Codurile care pot reprezenta asemenea caractere se numesc coduri alfanumerice.

Codul ASCII

Un cod alfanumeric foarte des utilizat este codul ASCII (American Standard Code for Information Interchange), care codifică literele mari şi mici ale alfabetului englez, cifrele zecimale, semnele de punctuaţie şi alte caractere speciale. Codul ASCII utilizează 7 biţi pentru a codifica 128 de caractere. Din cele 128 de caractere, 94 sunt caractere care pot fi tipărite, iar 34 sunt caractere utilizate pentru diferite funcţii de control.

În Tabelul 3. se prezintă codurile ASCII. Cei 7 biţi ai codului sunt notaţi cu b0

până la b7, b7 fiind bitul c.m.s. De notat că cei trei biţi mai semnificativi ai codului determină coloana din tabelă, iar cei patru biţi mai puţin semnificativi determină linia din tabelă. De exemplu, litera A este reprezentată în ASCII prin codul binar 100 0001 (coloana 100, linia 0001).

41

Tabelul 3 Codurile ASCII

b3b2b1b0

b6b5b4 000 001 010 011 100 101 110 111

0000 NULL DLE 0 @ P ` p 0001 SOH DC1 ! 1 A Q a q 0010 STX DC2 " 2 B R b r 0011 ETX DC3 # 3 C S c s 0100 EOT DC4 $ 4 D T d t 0101 ENQ NAK % 5 E U e u 0110 ACK SYN & 6 F V f v 0111 BEL ETB ' 7 G W g w 1000 BS CAN ( 8 H X h x

b3b2b1b0

b6b5b4 000 001 010 011 100 101 110 111

1001 HT EM ) 9 I Y i y 1010 LF SUB * : J Z j z 1011 VT ESC + ; K [ k { 1100 FF FS , < L \ l | 1101 CR GS - = M ] m } 1110 SO RS . > N ^ n ~ 1111 SI US / ? O _ o DEL

Cele 34 de caractere de control sunt desemnate în tabelul caracterelor ASCII prin nume abreviate. Caracterele de control se utilizează pentru transmisia datelor şi pentru aranjarea textului într-un anumit format. Există trei tipuri de caractere de control: de formatare, de separare a informaţiei şi de control al comunicaţiei. Dintre caracterele de formatare a textului menţionăm cele pentru deplasare înapoi BS (Backspace), retur de car CR (Carriage Return) şi tabulare orizontală HT (Horizontal Tabulation). Separatorii de informaţii se utilizează pentru separarea datelor în secţiuni, de exemplu în paragrafe şi pagini. Acestea cuprind caractere cum sunt separatorul de înregistrare RS (Record Separator) şi separatorul de fişier FS (File Separator). Caracterele de control al comunicaţiei se utilizează la transmisia textului. Exemple de asemenea caractere sunt STX (Start of Text) şi ETX (End of Text), care se pot utiliza pentru încadrarea unui mesaj transmis pe liniile de comunicaţie.

Unicode şi ISO/IEC 10646

Unicode este un set de caractere specificat de un consorţiu de producători importanţi de calculatoare din SUA, definit cu scopul de a elimina dificultăţile datorate utilizării seturilor de caractere codificate diferit în programele elaborate pentru mai multe limbi. Începând cu versiunea 1.1, Unicode este compatibil cu standardul 10646, a cărui primă versiune a fost elaborată în 1993 de organizaţiile ISO (International Standards Organization) şi IEC International Electrotechnical Commission). Numele standardului este “Universal Multiple-Octet Coded Character Set”, întâlnit şi sub forma acronimului

42

UCS (Universal Character Set). Versiunea curentă a standardului 10646 este 3.0. UCS a fost primul set de caractere standardizat elaborat cu scopul de a include în final toate caracterele utilizate în toate limbile scrise din lume, ca şi alte simboluri, cum sunt cele matematice. UCS este utilizat atât pentru reprezentarea internă a datelor în sistemele de calcul, cât şi pentru comunicaţiile de date.

În versiunile uzuale ale UCS, codul unui caracter este reprezentat prin patru cifre hexazecimale; aceasta corespunde formei pe doi octeţi, denumită UCS-2. A fost definită de asemenea şi o formă pe 4 octeţi, UCS-4, pentru a garanta faptul că spaţiul de codificare va fi suficient şi în viitor. În forma pe 2 octeţi a UCS, cele 65536 coduri sunt împărţite în 256 de linii de câte 256 de celule fiecare. Primul octet al codului unui caracter indică numărul liniei, iar al doilea numărul celulei. Primele 128 de caractere din linia 0 reprezintă caracterele ASCII. Întreaga linie 0 conţine aceleaşi caractere ca şi cele definite de standardul ISO/IEC 8859-1. Octetul reprezentând codul unui caracter ASCII sau ISO/IEC 8859-1 poate fi transformat simplu în reprezentarea sa UCS prin adăugarea cifrelor 00 în faţa acestuia. UCS cuprinde aceleaşi caractere de control ca şi cele din setul ASCII.

În forma pe 4 octeţi, pot fi reprezentate peste 2 miliarde de caractere diferite. Primul bit al primului octet trebuie să fie 0, astfel încât se utilizează numai 31 de biţi din cei 32. Acest spaţiu de codificare este împărţit în 128 de grupe, fiecare conţinând 256 de planuri. Primul octet de cod indică numărul grupei, iar al doilea numărul planului. Al treilea şi al patrulea octet indică numărul liniei, respectiv al celulei. Caracterele care pot fi reprezentate în forma UCS-2 aparţin planului 0 din grupa 0, care este numit plan multilingv de bază sau BMP (Basic Multilingual Plane). Încă nu au fost alocate caractere poziţiilor în afara planului BMP, iar în practică se utilizează numai forma pe doi octeţi.

În forma UCS-2, caracterele cu coduri cuprinse între 00A0h şi 00FFh formează

setul Latin-1. Aceste coduri conţin litere suplimentare utilizate în principalele limbi din Europa de Vest, ca şi semne matematice şi de punctuaţie. Codurile din setul Latin-1 se bazează pe standardul ISO/IEC 8859-1. Tabelul 4. prezintă setul Latin-1. În acest tabel, primele trei cifre hexazecimale ale codului sunt cele care desemnează coloana, iar ultima cifră a codului este cea care desemnează linia.

00A 00B 00C 00D 00E 00F 0 ° À Ð à ð 1 ¡ ± Á Ñ á ñ 2 ¢ ² Â Ò â ò 3 £ ³ Ã Ó ã ó 4 ¤ ´ Ä Ô ä ô 5 ¥ µ Å Õ å õ 6 ¦ ¶ Æ Ö æ ö 7 § · Ç × ç ÷ 8 ¨ ¸ È Ø è ø 9 © ¹ É Ù é ù A ª º Ê Ú ê ú B « » Ë Û ë û C ¬ ¼ Ì Ü ì ü D - ½ Í Ý í ý E ® ¾ Î Þ î þ F ¯ ¿ Ï ß ï ÿ

Tabelul 4 Setul de caractere Latin 1

43

Există patru zone principale pentru asignarea codurilor UCS-2. Zona A conţine caractere alfabetice şi simboluri, având primele două cifre hexazecimale ale codului cuprinse între 00h şi 4Dh. De exemplu, această zonă cuprinde seturile Basic Latin, Latin-1, Latin Extended-A, Latin Extended-B; alfabetele grec, chirilic, armean, ebraic, arab, bengali, tamil, georgian; diferite simboluri, săgeţi, operatori matematici, forme geometrice etc. Literele ă, Ă, ş, Ş, ţ, Ţ din limba română fac parte din setul Latin Extended-A, în timp ce literele â, Â, î, Î fac parte din setul Latin-1. De menţionat că toate aceste caractere fac parte din setul de caractere ISO/IEC 8859-2, care cuprinde caracterele speciale necesare pentru limbile ţărilor din Europa Centrală şi de Est. În Tabelul 5. se prezintă codurile ISO/IEC 10646 ale caracterelor speciale utilizate în limba română.

Tabelul 5. Codurile ISO/IEC 10646 ale caracterelor speciale din limba română

Caracter Cod hexa Caracter Cod hexa Ă 01 02 ă 01 03 Â 00 C2 â 00 E2 Î 00 CE î 00 EE Ş 01 5E ş 01 5F Ţ 01 62 ţ 01 63

Zona I conţine caractere ideografice, având primele două cifre hexazecimale ale codului cuprinse între 4Eh şi 9Fh. Un caracter ideografic reprezintă un cuvânt sau o unitate gramaticală inseparabilă. Există un mare număr de caractere ideografice în diferite limbi. Ca un principiu general de codificare, pentru ca un nou caracter să fie inclus în setul UCS, acest caracter trebuie să difere de toate caracterele deja incluse, atât în semnificaţie, cât şi ca formă. Formele grafice alternative ale caracterelor existente (variante de fonturi, hieroglife) nu au deci coduri distincte. În limbile chineză, japoneză şi coreeană există un mare număr de caractere ideografice care au aceeaşi origine istorică şi doar diferenţe minore ca formă în cele trei limbi. Acestor variante naţionale ale aceluiaşi caracter ideografic li s-a atribuit un cod UCS unificat, o soluţie cunoscută sub numele de unificare CJK. Zona I conţine asemenea caractere unificate.

Zona O, având primele două cifre hexazecimale ale codului cuprinse între A0h şi DFh, este rezervată pentru versiunile ulterioare ale standardului. Zona R este o zonă pentru utilizare restrânsă, codurile având primele două cifre hexazecimale cuprinse între E0h şi FFh . Această zonă este împărţită la rândul ei în zona de utilizare privată, zona de compatibilitate a caracterelor ideografice CJK şi zona caracterelor speciale. Zona de utilizare privată este disponibilă pentru utilizatorii care necesită caractere speciale pentru programele lor de aplicaţii. De exemple, icoanele utilizate în meniuri pot fi specificate prin coduri de caractere în această zonă. Există posibilitatea utilizării unui număr de 6400 de caractere private, cu coduri având primele două cifre hexazecimale cuprinse între E0h şi F8h. Această zonă nu va fi ocupată de versiunile viitoare ale standardului. Zona de compatibilitate conţine caracterele care sunt mapate la alte zone în spaţiul de codificare. Caracterele disponibile în această zonă specială au o utilizare largă, dar nu sunt direct compatibile cu modul de reprezentare a caracterelor UCS, astfel încât nu pot fi incluse direct în alte zone. Codurile FFFEh şi FFFFh nu reprezintă coduri de caractere, fiind excluse din UCS.

Există o problemă de ordonare a octeţilor din cadrul cuvintelor de 16 biţi

reprezentând coduri de caractere în Unicode. În general, dacă octetul 0 se află în dreapta

44

cuvântului (în partea mai puţin semnificativă), iar octetul 1 se află în stânga, ordonarea octeţilor este numită “little-endian”. Dacă octetul 0 se află în stânga cuvântului (în partea mai semnificativă), iar octetul 1 se află în dreapta, ordonarea octeţilor este numită “big-endian”. Presupunem că un şir de 2n octeţi reprezentând n caractere Unicode sunt transferate de la un calculator cu ordonarea “little-endian” la un calculator cu ordonarea “big-endian”. Ordinea octeţilor din cuvintele de 16 biţi va fi atunci schimbată. Dacă la începutul şirului original se include codul FEFFh, care este un cod pentru marcajul ordinii octeţilor (Byte Order Mark), atunci prin inversarea octeţilor acesta va apare sub forma FFFEh, care este un cod invalid. Acest cod invalid indică faptul că ordinea octeţilor din cadrul tuturor cuvintelor este incorectă, şi deci ordinea trebuie inversată înaintea interpretării cuvintelor ca şi caractere. Astfel, prin plasarea codului FEFFh la începutul unui şir de caractere, o aplicaţie poate determina dacă octeţii trebuie inversaţi înainte de interpretarea codurilor. O situaţie similară apare la transferul de la un calculator cu ordonarea “big-endian” la un calculator cu ordonarea “little-endian”.

45


A. Deduceţi algoritmii pentru adunarea şi scăderea a două cifre zecimale exprimate în codul 8421. Pentru deducerea algoritmului de adunare se va întocmi un tabel cu toate sumele posibile care se pot obţine prin adunarea a două cifre zecimale şi a unui eventual transport, indicând pentru fiecare din

acestea suma corectă. Similar se va proceda pentru scădere, ţinând cont şi de un eventual împrumut.

B. Deduceţi algoritmii pentru adunarea şi scăderea a două cifre zecimale exprimate în codul Exces 3.

C. Deduceţi algoritmii pentru conversia din binar în codul Gray şi din codul Gray în binar.

D. Construiţi codul Hamming pentru un cuvânt de 16 biţi, considerând paritatea

impară. Explicaţi modul în care funcţionează corecţia unei erori.

46

4. ALGORITMI ŞI SCHEME LOGICE

Algoritmul este conceptul fundamental al informaticii. este acela de algoritm.

Algoritmul este un set de paşi prin care poate fi dusă la îndeplinire o sarcină. Exemplu: Algoritmul lui Euclid pentru determinarea celui mai mare divizor comun a 2 numere naturale. Pasul 1. Se notează cu M cea mai mare, iar cu N cea mai mică dintre cele 2 valori. Pasul 2. Se împarte M la N şi se notează restul cu R. Pasul 3. Dacă R este diferit de zero, se atribuie lui M valoarea N şi lui N valoarea R, apoi se revine la pasul 2; în caz contrar cel mai mare divizor al celor 2 numere este valoarea notată cu N. Algoritmii sunt reprezentaţi prin programe. Aceste programe formează ceea ce se numeşte software. Pentru ca un calculator să poată rezolva o anumită problemă, trebuie ca mai întâi să se descopere şi să se reprezinte sub formă de program un algoritm de rezolvare a problemei respective. La început studiul algoritmilor a făcut parte din matematică. Cu mult înainte de apariţia calculatoarelor, căutarea unor algoritmi a fost una dintre activităţile importante ale matematicienilor. Principalul obiectiv al acestora era descoperirea unui set mic de instrucţiuni care să descrie modul de rezolvare al oricărei probleme dintr-o anumită categorie de probleme. Unul dintre cele mai cunoscute rezultate obţinute în acest domeniu este algoritmul lui Euclid, prezentat anterior, care permite determinarea celui mai mare divizor comun a 2 numere întregi pozitive. După descoperirea algoritmului, efectuarea sarcinii repetitive nu va mai necesita înţelegerea principiilor care stau la baza acestuia, ci doar urmarea instrucţiunilor. Datorită acestei posibilităţi de captare şi transmitere a informaţiei prin intermediul algoritmilor, oamenii au putut să construiască maşini cu comportament inteligent. Prin urmare nivelul de cunoaştere al unei maşini este limitat de nivelul de cunoştinţe care poate fi transmis prin intermediul algoritmilor. Astfel, putem construi o maşină care să realizeze o anumită sarcină, dacă şi numai dacă găsim un algoritm care să precizeze modul în care sarcina respectivă poate fi dusă la bun sfârşit. Prin urmare, dacă nu există un astfel de algoritm, efectuarea sarcinii respective nu stă în puterea unei maşini.

După descoperirea unui algoritm care rezolvă o anumită problemă, pasul următor este ca algoritmul respectiv să fie reprezentat într-o formă în are să poată fi comunicat unei maşini. Definiţie

Un algoritm reprezintă o succesiune finită de paşi, bine determinaţi, prin care din mulţimea datelor de intrare ale unei probleme ce aparţine unei clase de probleme se produc date de ieşire corecte.

47

Proprietăţile algoritmilor

1) Determinarea Un algoritm trebuie astfel conceput încât operaţiile sale şi succesiunea executării lor să fie descrise clar, precis, fără ambiguităţi sau neclarităţi.

2) Generalitatea

Algoritmul va fi conceput astfel încât să asigure rezolvarea unei clase de probleme şi nu a unei probleme particulare.

3) Finititudinea - executarea algoritmului trebuie să cuprindă un număr finit de

operaţii, chiar dacă numărul acestora este foarte mare. Obiectele cu care lucrează algoritmii • Constantele sunt date a căror valoare nu se modifică pe parcursul algoritmului.

Constantele pot fi: - numerice; - alfanumerice; - logice. • Variabile sunt date a căror valori se pot modifica pe parcursul execuţiei algoritmului.

Variabilele pot fi numere întregi, reale, logice sau şiruri de caractere. Ele se notează cu litere sau simboluri care să le sugereze semnificaţia. • Operaţiile - aritmetice: +, -, *, /

- logice: - NOT (negaţia logică) : ¬ - AND (SI logic) : ∧ - OR (SAU logic) : ∨ Operaţiile logice se aplică unor operanzi logici, care pot avea valorile adevărat şi fals. Tabelele de adevăr corespunzătoare acestor operaţii sunt prezentate în cele ce urmează. - relaţionale: <, ≤, >, ≥, =, ≠.

• Expresiile sunt formate din constante şi variabile legate între ele prin operaţii şi paranteze care să prezinte ordinea de evaluare a operaţiilor. Nu se vor folosi decât paranteze ( ). Expresiile pot fi: - aritmetice; - relaţionale; - logice.

x x x y x ∧ y x y x ∨ y a f f f f f f f f a a f f a f a f a f f a a a a a a a a

48

Operaţiile de bază realizate de către un algoritm

• citirea unei variabile; • scrierea unei variabile; • atribuirea v ← expresie, unde ← este operator de atribuire; • decizia - prin care se verifică o condiţie a cărei valoare de adevăr determină

ramificarea algoritmului. Reprezentarea (descrierea) algoritmilor 1. Schema logică - constituie un mijloc foarte sugestiv (intuitiv) de a descrie un algoritm prin intermediul unor figuri geometrice numite blocuri care au o semnificaţie bine precizată. Schemele logice sunt foarte uşor de urmărit pentru algoritmi simpli, dar mai greu de urmărit pentru algoritmi lungi. 2. Limbajul convenţional numit şi limbaj pseudocod - este limbaj cu reguli sintactice foarte simple care permit exprimarea neambiguă a ordinii de execuţie a paşilor algoritmilor. Descrierea algoritmilor prin scheme logice

Schema logică este o transcriere grafică a paşilor unui algoritm. Fiecărui pas i se ataşează un simbol numit bloc, sensul de parcurgere fiind indicat prin săgeţi. Blocurile folosite într-o schemă logică sunt următoarele: Bloc delimitator: - marchează începutul/sfârşitul algoritmului.

Blocul de citire/scriere:

Blocul de atribuire: Blocul de decizie:

Blocul de procedură:

Săgeată:

Conector de blocuri:

condiţie NU DA

adevărat fals

Nume procedură

49

Exemplu: Algoritmul pentru rezolvarea ecuaţiei de gradul I, ax + b = 0 : Principiile de bază ale programării structurate Programarea structurală iniţială de E.W. Dijkstra şi C.A.R. Hoare reprezintă o metodă de elaborare a algoritmilor care impune reguli extrem de severe de concepere a algoritmilor. Una dintre metodele curente de elaborare a algoritmilor este metoda programării structurate. Programarea structurată are la bază următoarele principii: 1) Proiectarea descendentă a algoritmilor care consideră că algoritmul are o structură complexă care se obţine prin descompuneri succesive, astfel la fiecare pas de descompunere un element de structură se descompune în conformitate cu una dintre schemele de descompunere fundamentale. 2) Utilizarea în algoritmi a doar 3 structuri de control: secvenţială, alternativă şi repetitivă. Algoritmii proiectaţi conform acestor principii se numesc algoritmi structuraţi. Programarea structurală are la bază teorema de structură a lui Bőhm şi Jacopini care precizează că un algoritm cu un singur punct de început şi un singur punct de sfârşit poate fi descris cu ajutorul celor 3 structuri de control, prezentate în figura 2.

a) Structura secvenţială: b) Structura alternativă:

a

b

condiţie adevărat fals

a b

START

a,b

a = 0 DA NU

x ← -b/a

Scrie x

b = 0 DA NU

Scrie “Ecuaţia nu are soluţie “

Scrie “Ecuaţia are o infinitate de soluţii “

STOP

Fig. 1. Algoritmul pentru rezolvarea ecuaţiei de gradul I.

50

c) Structura repetitivă:

Exemple

1. Un exemplu pentru structura alternativă îl constituie algoritmul pentru determinarea minimului a 3 valori a, b, c, a cărui reprezentare prin schemă logică este prezentată în figura 3.

2. Determinarea minimului unui şir de numere care se încheie cu valoarea 0, are

algoritmul prezentat în figura 4.

Observaţii: Deşi structura ciclică prezentată este suficientă pentru a descrie un algoritm ciclic,

totuşi în anumite situaţii se mai utilizează şi structura ciclică cu test final, prezentată în figura 5. Ciclul cu test final poate fi transformat în ciclul cu test iniţial, conform figurii 6.

condiţie NU

DA

a

Fig. 2. Structuri de control utilizate în programarea structurată.

51

cond DA NU

a

START

Citeşte a,b,c

a < b DA NU

min ← b

min > c DA NU

STOP

min ← a

min ← c

Scrie min

START

Citeşte a

a ≠ 0 NU

max ← a

a > max DA

STOP

max ← a

DA

Citeşte a

Scrie a

Fig. 3. Determinarea minimului a trei numere.

Fig. 4. Determinarea minimului unui şir de numere.

Fig. 5. Structura ciclică cu test final. Fig. 4.6. Structura ciclică cu test final.

cond

DA

NU

a

a

52

Descrierea algoritmilor în limbaj pseudocod

Există mai multe variante de limbaj pseudocod, care însă nu diferă esenţial. Un limbaj pseudocod nu este standardizat şi conţine, în general următoarele comenzi (comenzi care corespund structurilor de control utilizate în programarea structurată):

1) de atribuire:

variabilă ← expresie

2) de citire: citeşte lista de variabile

3) de scriere: scrie listă de expresii

4) de ramificare: dacă condiţie

atunci operaţie 1 ... operaţie n

n operaţie...

1operaţiealtfel

sfârşit dacă

5) de ciclare: cât timp condiţie execută

operaţie 1 ... operaţie n sfârşit cât timp repetă operaţie 1 ... operaţie n până când condiţie pentru contor ← val_initială, val_finală execută operaţie 1 ... operaţie n sfârşit pentru

6) de oprire: stop

a)

b

c)

53

Erorile în algoritmi Un algoritm devine eficient în măsura în care între resursele de calcul utilizate şi

precizia rezultatelor se stabileşte un raport acceptabil. Cu toată precizia oferită de calculatoarele electronice, calitatea rezultatelor este influenţată de mulţi alţi factori. Soluţia unei probleme depinde de datele iniţiale, acestea fiind obţinute în urma unor observaţii, măsurători sau pe baza altor calcule prealabile. Precizia instrumentelor cu care se fac observaţiile, condiţiile în care au loc acestea, precizia calculelor necesare determinării unor parametrii iniţiali generează erori în datele iniţiale. O parte din parametrii utilizaţi în formulele de calcul nu au o valoare exprimabilă printr-un număr finit de zecimale (ex. ,e,,3 π etc.). Erorile de aproximare a lor sunt cunoscute şi vor fi astfel alese încât să fie corelate cu precizia dorită pentru calculele în care intră aceşti parametri. O clasă importantă de erori o constituie erorile de rotunjire. Ele apar ca urmare a limitării numărului de zecimale cu care se poate reprezintă un număr în calculator. La rezolvarea, mai ales numerică a unei probleme se foloseşte o metodă matematică. De multe ori fenomenul analizat este supus unor condiţii simplificatoare, fapt ce poate genera erori de metodă. O altă categorie de erori sunt cele introduse în calculator de prezenţa unor funcţii cărora în analiza matematică le corespund serii infinite. Aceste erori se numesc erori reziduale. Exemplu: Calculul funcţiei trigonometrice sin(x) se face prin dezvoltare în serie

Taylor: ( ) ...!5

x!3

xxxsin53−+−=

Proiectarea algoritmilor Conceptele principale care s-au cristalizat în domeniul programării structurate sunt: proiectarea top-down, proiectarea modulară şi proiectarea structurală. Cele trei tipuri nu se exclud una pe cealaltă ci se intercorelează în obţinerea unor produse program. Proiectarea top-down (de sus în jos) presupune descompunerea de la general la particular a problemei date în subprobleme sau funcţii de prelucrat conducând la realizarea algoritmului în mai multe faze succesive, fiecare fază fiind o detaliere a fazei anterioare până când algoritmul este suficient de rafinat (detaliat) pentru a putea fi codificat. Proiectarea modularizată presupune descompunerea problemelor în părţi numite module, astfel încât fiecare din acestea să îndeplinească anumite funcţii bine definite. Descompunerea se poate face în mai multe faze (la mai multe niveluri) prin metoda top-down. Criteriile de descompunere depind în mare măsură de experienţa proiectanţilor (programatorilor). Proiectarea modularizată presupune pe lângă identificarea modulelor şi a relaţiilor dintre ele şi precizarea modului şi a ordinii în care sunt puse în lucru. Reprezentarea modularizată a programelor se realizează prin intermediul diagramelor (organigramelor) de tip arbore (figura 4.7.) .

54

Se disting modulele apelatoare: A, B, B1, C, C2 şi module apelate (B11, B12, B2,

C1, C3). În implementarea în programe modulele pot fi interne sau externe după modul de apel şi locul de plasare faţă de unitatea apelatoare. Modulele interne sunt integrate în programul din care sunt apelate şi au acces la toate datele acestuia. Modulele externe nu sunt integrate în programele de care sunt apelate. Atât modulele interne cât şi cele externe pot fi constituite în blocuri cu semnificaţie de subprograme. Modul de lucru cu module diferă semnificativ de la un limbaj de programare la altul. Proiectarea structurată a algoritmilor constă dintr-o mulţime de reguli şi restricţii care forţează proiectantul (programatorul) să urmeze o formă strânsă de reprezentare şi codificare. Verificarea corectitudinii algoritmilor În procesul de elaborare al algoritmilor se pot structura formulări imprecise sau eronate. Verificarea corectitudini ar însemna verificarea faptului că pentru oricare set de date algoritmul furnizează rezultate corecte, lucru imposibil de realizat în practică. În practică se recomandă următoarele verificări ale corectitudinii algoritmilor simpli: 1. Încheierea algoritmilor după un număr finit de paşi. 2. Modul în care au fost construite selecţiile. 3. Asigurarea valorilor pentru toate variabilele referite în operaţii. Dacă cele trei tipuri de verificări au condus la concluzia de corectitudine se procedează la un test care presupune parcurgerea atentă operaţie cu operaţie a algoritmului pentru seturi de date de obicei cazuri limită.

A

B

B1 B2

B11 B12 C21 C22

C1 C2 C3

C

Figura 7. Reprezentarea modularizată a programelor

55

Analiza algoritmilor

Această etapă constă în:

1. Determinarea necesarului de memorie; 2. Determinarea timpului necesar execuţiei algoritmului; 3. Determinarea optimalităţii algoritmului. EXEMPLE Rezolvarea ecuaţiei de gradul al doilea

Să se rezolve ecuaţia de gradul II 02 =++ cbxax , coeficienţii a, b şi c fiind citiţi de la tastatură.

Identificând toate situaţiile care pot să apară, obţiem organigrama

în care semnificaţia mesajelor este următoarea: m1 : Aceasta nici macar nu e o ecuatie! m2 : Imposibil! m3 : Este, de fapt, o ecuatie de gradul I m4 : Asta da! Este o ecuatie de gradul II m5 : Radacini reale distincte m6 : Radacini reale confundate m7 : Radacini complexe

56

Prin identificarea modului în care instrucţiunile IF-THEN, respectiv IF-THEN-ELSE se includ unele pe altele şi a instrucţiunilor simple şi compuse, se obţine organigrama mai explicită:

57


Pentru rezolvarea urmǎtoarelor probleme (pentru care algoritmii se dau parţial sau total), se cere detalierea algoritmilor, transpunerea lor în scheme logice (organigrame) şi scrierea programelor în pseudocod:

A. Se citesc de la tastatură valorile pentru variabilele a, b şi c. Se va afişa pe monitor valoarea maximului dintre a, b şi c.

B. Aceeaşi cerinţă, pentru patru valori a, b, c şi d.

C. Să se afişeze în ordine crescătoare valorile de la problema A.

D. Se citesc trei numere reale, în variabilele a, b, c. Dacă cele trei valori pot forma

unghiurile unui triunghi, să se verifice dacă toate unghiurile sunt ascuţite; în caz contrar, verificati dacă există un unghi obtuz sau un unghi drept. Scrieti un mesaj corespunzator pentru fiecare caz.

E. Se citesc valorile parametrilor a, b, c, d, e şi f pentru sistemul de douǎ ecuaţii liniare cu douǎ necunoscute

=+=+

feydxcbyax

Sǎ se gǎseascǎ valorile rǎdǎcinilor x şi y. Se vor lua în calcul diferitele situaţii care pot interveni.

F. Se citesc valorile pentru douǎ variabile, a şi b. Sǎ se gǎseascǎ cel mai mare divizor comun (cmmdc) şi cel mai mic multiplu comun (cmmmc) al celor douǎ numere, utilizând algoritmul lui Euclid cu scǎderi repetate. Se va ţine seama de diversele posibilitǎţi de introducere a valorilor pentru cele douǎ variabile de intrare, a şi b.

G. Se citeşte valoarea variabilei întregi n.

Sǎ se stabileascǎ dacǎ n este un numǎr prim, iar în caz contrar, sǎ se gǎseascǎ valoarea celui mai mic divizor propriu al lui n.

58

5. TIPURI DE DATE. CITIREA ŞI TIPĂRIREA DATELOR

În limbajul C++ sunt utilizate următoarele tipuri simple de date numerice:

Tipul de dată Lungime (octeţi) Domeniu de valori

Întreg

[signed] char 1 -128..127 (-27..27-1) unsigned char 1 0..255 (0..28-1) unsigned [int] 2 0..65535 [short] [int] 2 -32768..32767 unsigned long 4 0..232-1

Real

long [int] 4 -231..231-1 float 4 3.4*10-38..3.4*1038 double 8 1.7*10-308.. 1.7*10308 long double 10 3.4*10-4932.. 3.4*104932

Cel mai adesea, pentru citirea/scrierea datelor se utilizează cin>>/cout<<, dar formatarea este în acest caz în seama utilizatorului; ca alternativă, se pot utiliza funcţiile scanf/printf din limbajul C.

Funcţia getch( ) citeste fără ecou pe monitor un caracter de la tastatură Funcţia putch( ) tipăreşte un caracter pe ecran Funcţia getche( ) citeste cu ecou pe monitor un caracter de la tastatură Macro-ul getchar( ) citeşte un caracter tastat, după asarea tastei ENTER Macro-ul putchar( ) afişează un caracter pe monitor Macro-urile getchar si putchar(x) au prototipurile in header-ul <stdio.h> Funcţia gets( ) citeşte un şir de caractere Funcţia puts( ) afişează un şir de caractere FUNCŢIA scanf( ) Funcţia de citire cu format scanf( ) are sintaxa : scanf(“lista de formate” , adresa_var1 , adresa_var2,…..);

59

- citeşte din fişierul standard de intrare stdio o secvenţă de câmpuri de intrare,caracter cu caracter, până la terminarea introducerii câmpurilor şi apăsarea tastei < Enter > ; - formatează fiecare câmp conform formatului specificat în lista de formate.

Dincaracterele citite se calculează valori numerice sau literale, conform tipului fiecăreiv a r i a b i l e , d im en s i un i lo r d e f o r m at s p e c i f i ca te ş i a s e p ar a t o r i l o r d e c âmp ur ipredefiniţi (spaţiu, tab şi enter) sau impuşi explicit ; - v a l o r i l e a s t f e l c on s t r u i t e s un t s to c a t e l a ad r e s e l e v a r i a b i l e l o r s pe c i f i ca t e c a argumente; ordinea formatelor variabilelor trebuie să coincidă cu ordinea listei adreselor variabilelor în care se face citirea. Fiecare variabilă care se doreşte a fi citită trebuie corelată cu un format specific. Observaţie: indiferent de formatul folosit, la întâlnirea unui spaţiu în introducereadatelor, este terminată citirea variabilei. Pentru funcţia de citire scanf trebuie folosit operatorul adresă “&”

Pentruvariabilele citite cu această funcţie trebuie precizate adresele la care se stochează înmemoria calculatorului valorile variabilelor. Funcţia va introduce valorile citite direct laacele adrese. Singurul caz în care nu este obligatorie folosirea operatorul adresăpentru citirea valorii unei variabile cu funcţia scanf este citirea unui şir de caractere.

Observaţie: citirea cu ajutorul funcţiei scanf a şirurilor de caractere care conţin spaţii este imposibilă. În cazul în care formatul specificat este necorespunzător, rezultatul obţinut poate fi neprevăzut. Valoarea întoarsă de scanf în caz de succes, este numărul de variabile care au fost citite corect. Dacă nu a fost citită nici o variabilă (de exemplu s-a introdus un şir în loc de un număr) funcţia întoarce valoarea 0. Dacă apare o eroare înaintea oricărei citiri şi asignări, funcţia returnează EOF (constantă de sistem avândvaloarea întreagă –1). Specificatorii de format ai funcţiei scanf( ) : % c C i t e ş t e u n c a r a c t e r % d C i t e ş t e u n î n t r e g z e c i m a l % i C i t e ş t e u n î n t r e g z e c i m a l % e C i t e ş t e u n n u m ă r f l o a t % f C i t e ş t e u n n u m ă r f l o a t % g C i t e ş t e u n n u m ă r f l o a t % o C i t e ş t e u n n u m ă r o c t a l f ă r ă s e m n % s C i t e ş t e u n ş i r d e c a r a c t e r e % x C i t e ş t e u n n u m ă r h e x a z e c i m a l f ă r ă s e m n % p C i t e ş t e u n p o i n t e r % n A r gu m en tu l a so c i a t p r im e ş te o v a lo a r e î n t re gă e ga l ă c u nu mă r u lde

caractere deja citite % u C i t e ş t e u n n u m ă r î n t r e g f ă r ă s e m n

În specificatorul de format pot să apară şi modificatori de tip.

- Modificatorul h, care poate precede caracterele de conversie d, i , o , u , x sau X, precizează că valoareaconvertită trebuie memorată ca un „short int” sau „unsigned short int”.

60

- Modificatorul l, poate precede caracterele de conversie d, i, o, u, x, X, caz în care valoarea trebuie memorată ca un „ long int” s a u „ unsigned long int”, sau poate precede caracterele e , E , f , g , G , c a z î n c a re v a l o a r ea t r e bu i e m em o r a t ă c a u n „ double”.

- Modificatorul L poate precede numai caracterele e, E, f , g, G şi precizează că valoarea convertită trebuie memorată ca un „long double”

FUNCŢIA printf( ) Este perechea funcţiei scanf( ), semnificaţia caracterelor de control fiind asemănătoare. Sintaxa de utilizare este : int printf(“mesaje si lista de formate”, expr_1, expr_2, ….,expr_n); Funcţia printf realizează următoarele : - acceptă o serie de argumente de tip expresie pe care, după ce le evaluează, letransformă în şiruri de caractere conform formatului specificat - scrie şirurile în fişierul standard de ieşire (sunt acceptate secvenţele de evitare). Dacă numărul de argumente specificate în format nu corespunde cu numărulargumentelor din lista de expresii, atunci apar rezultate neaşteptate care pot aveaefecte dăunătoare. Rezultatul întors de funcţie, în caz de succes, este numărul deocteţi scrişi, iar în caz de eroare, valoarea întoarsă este EOF. Specificatorii deformat folosiţi pentru printf sunt % e , % E Număr real de forma iiii.zzzzzz , unde nr.zecimale z este dat de

precizie (6 implicit) % f Număr real de forma i.zzzzzz , unde nr. zecimale este dat deprecizie (6

implicit) şi pentru partea întreagă este folosită doar o cifră % g , % G N u m ă r r e a l c a r e s u p r i m ă c a r a c t e r e l e t e r m i n a l e

c a r e n u influenţează valoarea , adică cifrele 0 de la sfârşit şipunctul zecimal , dacă are partea fracţionară 0

% i Număr întreg în baza 8, 10, sau 16 în funcţie de primul sauprimele două caractere

% d Număr întreg în baza 10 % o Număr întreg în baza 8 ; nu este necesară scrierea cifrei 0la începutul

numărului % x Număr întreg în baza 16 ; nu este necesară scriereasecvenţei 0x la

începutul numărului % u Număr întreg fără semn % s Şir de caractere % c Un singur character

Expresiile afişate se pot alinia la stânga sau la dreapta şi se poate forţa

afişareasemnului astfel :

- semnul plus (+) afişează explicit semnul expresiei

61

- semnul minus (-) aliniază expresia afişată la stânga - absenţa oricărui semn semnifică alinierea expresiei afişate la dreaptă

Pentru numerele întregi şi pentru şirurile de caractere se poate specifica un număr care înseamnă spaţiul folosit pentru afişare. Dacă spaţiul necesar este mai mic sau egal cu numărul specificat, atunci se vor afişa suplimentar spaţii (sau zerouri,dacă numărul este precedat de cifra 0) până la completarea spaţiului de afişare.

Pentru numerele reale se pot specifica, opţional, semnul pentru aliniere şi două numere separate prin punct. Primul precizează dimensiunea totală de afişare, iar al doilea precizia, adică numărul de zecimale afişate.

În cazul şirurilor de caractere, specificarea a două numere separate prin punct indică

faptul că primul număr reprezintă numărul de caractere din şir care se vor afişa, iar al doilea reprezintă limita superioară de tipărire, completarea făcându-se cu spaţii la dreapta sau stânga, în funcţie de modul de aliniere.

Poate apare fenomenul de t runchiere a şirului afişat în cazul în care

dimensiunea acestuia depăşeşte limitainferioară. În cazul unui număr întreg, al doilea număr indică o completare la stânga cu zerouri

până se ajunge la dimensiunea de afişare specificată. În format se pot utiliza şi modificarii de tip h şi l , corespunzători lui „short”,

respectiv „long”. Dacă h este urmat de un d , i , o , u , x sau X, atunci aceasta este o

specificare de conversie relativ la „short int” s a u „ unsigned short int” Dacă l este urmat de d, i, o, u, x sau X, atunci specificarea de conversie se

aplică unui argument „long int” sau „unsigned long int”. Modificatorul L poate fi urmat de e , E , f , g sau G şi atunci specificarea de

conversie se plică unui argument „long double”

62

EXEMPLE

A. Funcţiile getch( ) şi putch( )

#include <conio.h> // Functia getch() citeste fara ecou un caracter // Caracterul tastat va aparea pe ecran doar datorita lui putch(x) void main(void) { clrscr(); putch(getch()); getch(); }

B. Funcţia getche( )

#include <conio.h> // Functia getche() face acelasi lucru ca getch(), dar cu ecou pe monitor // Caracterul tastat va aparea de 2 ori (odata datorita lui getche(), // odata datorita lui putch(x) ). void main(void) { clrscr(); putch(getche()); getch(); }

C. Macrourile getchar( ) şi putchar( )

#include <conio.h>

63

#include <stdio.h> // Si macro-ul getchar citeste un caracter tastat, dar, spre deosebire // de functiile getch() si getche(), doar dupa apasarea tastei ENTER // Macro-urile getchar si putchar(x) au prototipurile in header-ul stdio.h // (STanDard Input-Output) // conio.h este inclus pentru functia getch() void main(void) { clrscr(); putchar(getchar()); getch(); }

D. Secvenţele ESCAPE; funcţia puts( )

#include <conio.h> #include <stdio.h> // Functia puts(x) scrie pe monitor sirul x // Ghilimelele si apostroful, avand in mod normal semnificatii speciale, // se scriu precedate de un back-slash \ , daca vrem sa apara ca atare in text // Acum, deoarece se vede ca si back-slashul are o semnificatie speciala, // trebuie si el precedat de un back-slash, daca vrem sa apara in text void main(void) { puts("Ce frumoase ghilimele (\") avem !"); puts("Si apostroful (\') este frumos !"); puts("nu trebuie uitat nici back-slash-ul (\\) !"); getch(); }

64

E. Funcţia printf( ) pentru scrierea cu format

#include <stdio.h> #include <conio.h> // Cea mai complexa functie de tiparire - printf - are prototipul in stdio.h; // permite afisarea datelor sub comanda unor formate introduse cu simbolul % // Back-slashul isi pastreaza semnificatia de introducere a unor comenzi // De ex. \n - trecerea la un rand nou // \t - tabulare orizontala etc. // In tot programul, introducerea se face cu funtia deja studiata getch() void main(void) { clrscr(); int i=123; printf("\n\nDe aici incepe. Nu se va apasa niciodata tasta Enter !\n"); printf("Tasteaza un caracter. Caracterul va fi afisat\n"); printf("%c\n\n",getch()); printf("Tasteaza un caracter. Caracterul va fi aliniat la dreapta\n"); printf("*%4c*\n\n",getch()); printf("Tasteaza un caracter. Caracterul va fi aliniat la stanga\n"); printf("*%-4c*\n\n",getch()); printf("Apasa orice tasta. Va fi afisat sirul abc\n"); printf("%s\n\n","abc",getch()); printf("Apasa orice tasta. Sirul abc va fi afisat aliniat la dreapta\n"); printf("*%10s*\n\n","abc",getch()); printf("Apasa orice tasta. Sirul abc va fi afisat aliniat la stanga\n"); printf("*%-10s*\n\n","abc",getch()); printf("Apasa orice tasta. Va fi afisata valoarea variabilei i (i=123).\n"); printf("%d\n\n",i,getch()); printf("Apasa orice tasta. Valoarea lui i va fi afisata aliniata la dreapta\n"); printf("*%10d*\n\n",i,getch());

65

printf("Apasa orice tasta. Valoarea lui i va fi afisata aliniata la stanga\n"); printf("*%-10d*\n\n",i,getch()); printf("Apasa orice tasta. Valoarea lui i va fi afisata cu zerouri in fata\n"); printf("*%010d*\n\n",i,getch()); printf("Pentru terminare, apasati orice tasta"); getch(); }

F. Utilizarea funcţiilor printf( ) şi scanf ( )

#include <conio.h> #include <stdio.h> // Deosebirile intre introducerea datelor de tip sir cu functia gets(x) // si introducerea cu ajutorul functiei scanf(x) // Si tiparirea se va face cu doua functii diferite puts(x) si Printf(x) void main(void) { char sir[50]; clrscr(); printf("\nSiruri citite cu functia "); printf("gets()\n"); printf("\nIntroduceti un sir FORMAT DIN MAI MULTE CUVINTE\n"); gets(sir); printf("\nSirul tiparit cu functia puts() :\n"); puts(sir); printf("\nSirul tiparit cu functia printf(%%s) :\n"); printf("%s\n",sir); printf("\nPentru continuare, apasati o tasta !"); getch(); clrscr(); printf("\nSiruri citite cu functia "); printf("scanf(%%s)\n"); printf("\nIntroduceti un sir FORMAT DIN MAI MULTE CUVINTE\n");

66

scanf("%s",sir); printf("\nSirul tiparit cu functia puts() :\n"); puts(sir); printf("\nSirul tiparit cu functia printf(%%s) :\n"); printf("%s\n",sir); printf("\nPentru terminare, apasati o tasta !"); getch(); }

G. Exerciţii asupra tipurilor de date

#include <conio.h> #include <stdio.h> // Diferentele intre tipul intreg int (format de tiparire %d) // si tipul real double (format %lf) void main() { clrscr(); printf("Se afiseaza valoarea polinomului 3x^2-8x+7\n\ pentru o valoare intreaga a lui x, introdusa de la tastatura\n"); int x; printf("tastati valoarea lui x="); scanf("%d",&x); printf("x=%d\tp(x)=%d\n\n",x,3*x*x-8*x+7); printf("\nPentru a continua programul, apasati orice tasta\n\n"); getch(); printf("Se afiseaza valoarea polinomului 3.5y^3-9.8y+3.7\n\ pentru o valoare flotanta dubla precizie a lui y,\n\ valoare introdusa de la tastatura\n"); double y; printf("tastati valoarea lui y="); scanf("%lf",&y); printf("y=%lf\tp(z)=%lf\n\n",y,3.5*y*y*y-9.8*y+3.7); printf("\nPentru a continua programul, apasati orice tasta\n\n"); getch(); printf("\nPrecizia maxima intr-un calcul este de 19-20 cifre semnificative\n");

67

printf("\n2/3=%20.18Lf",2/3.0l); printf("\n\nPentru a incheia programul, apasati orice tasta\n"); getch(); }

H. Formatele zecimal, octal şi hexagesimal

#include <conio.h> #include <stdio.h> // Limbajul C poate tipari rezultatele in zecimal (formatul %d), // octal (formatul %o) sau hexagesimal (formatul %x) void main() { clrscr(); int x; printf("tastati valoarea lui x="); scanf("%d",&x); printf("Valoarea in zecimal este\n"); printf("x(10)=%d\n\n",x); printf("Valoarea in octal este\n"); printf("x(8)=%o\n\n",x); printf("Valoarea in hexagesimal este\n"); printf("x(16)=%X\n\n",x); getch(); }

68


A. Se citesc de la tastatură coordonatele (xa, ya) şi (xb, yb) (valori întregi) a două puncte A şi B din plan. Să si tipărească pe monitor lungimea segmentului AB.

B. Se citesc de la tastatură lungimile (valori reale) a, b şi c ale unui triunghi. Se va

calcula cu ajutorul formulei lui Heron aria tringhiului şi se va afişa pe monitor, ca în exemplul următor:

date de intrare: a=3, b=4, c=5; afişarea dorită: Aria triunghiului cu laturile de lungime 3, 4 şi 5 este 6;

C. Se citesc de la tastatură valorile întregi a şi b; se va tipari câtul şi restul împărţirii

întregi a lui a la b, ca în exemplul următor: date de intrare: a=14, b=3; afişarea dorită: a:b = 4 si rest 2

D. Se citesc de la tastatură valorile întregi a şi b; se va tipari câtul şi restul împărţirii

întregi a lui a la b, ca în exemplul următor: date de intrare: a=14, b=3; afişarea dorită: 14:3 = 4 si rest 2

E. Se citesc trei valori reale a, b, şi c. Se calculează şi se afişează pe monitor valoarea polinomului

P(x) = a*x2 + bx + c

pentru patru valori ale parametrului x, citite de la tastatură, ca în exemplul următor: Presupunând că s-au introdus pentru a, b şi c valorile 1, 2 şi 3 (respectiv), iar pentru cele patru valori ale parametrului x valorile succesive 0, 1, 2 şi 3, pe monitor trebuie să apară mesajele P(0) = 3 P(1) = 6 P(2) = 11 P(3) = 18

69

6. INSTRUCŢIUNILE IF ŞI SWITCH Instrucţiunile condiţionale determină programele să testeze diferite condiţii şi, în funcţie de acestea, să decidă execuţia anumitor comenzi. Avem la dispoziţie instrucţiunile condiţionale:

• if( ) - execută comenzile dorite atunci când o condiţie (scrisă între paranteze) este adevarată.

• if( ) ... else - execută anumite comenzi când o conditie (scrisă între paranteze) este adevarată şi alte comenzi când această condiţie este falsă.

• switch - selectează care comandă va fi executată. A. Instructiunea "if"

"if( )" (dacă) este cea mai simplă instrucţiune condiţională. Forma generală a acestei instrucţiuni este:

• if (condiţie) { // Codul care va fi executat dacă este Adevarată condiţia }

unde 'condiţie' poate fi orice expresie alcatuită cu operatori raţionali, de egalitate şi logici. Dacă rezultatul evaluării condiţiei este TRUE, se execută codul dintre acolade, în caz contrar, când condiţia returnează FALSE, se trece peste acest cod. B. Instrucţiunea "if ... else"

Folosind instrucţiunea "if() ... else" (dacă ... altfel), putem stabili comenzi care să fie executate şi când condiţia instrucţiunii "if( )" este FALSE.

Forma generala a instructiuni "if() ... else" este: if (condiţie) { // codul care va fi executat dacă este Adevarată condiţia } else { // codul ce va fi executat daca condiţia este falsă }

unde 'condiţie' poate fi orice expresie logică.

Dacă rezultatul condiţiei este TRUE, se execută codul dintre primele acolade, care aparţin de "if()", în caz contrar, când condiţia returnează FALSE, sunt executate comenzile din acoladele de la "else".

70

Formula "else if( )"

Cu "if() ... else" sunt posibile execuţiile a doar două opţiuni, cea de la "if( )" sau de la "else". Dar sunt situaţii în care avem mai multe opţiuni, caz în care se foloseşte formula "else if( )" (altfel dacă).

Cu aceasta se pot crea şi alte opţiuni (suplimentare) între cele două Sintaxa generală este: if (condiţie 1) { // codul care va fi executat dacă este Adevarată condiţia 1 } else if (condiţie 2) { // codul ce va fi executat daca prima condiţie este Falsă şi este Adevarată condiţia 2 } else if (condiţie 3) { // codul care va fi executat daca primele două condiţii sunt False şi este Adevarată condiţia 3 } // ... else { // codul executat dacă toate condiţiile sunt False }

Pot fi adaugate oricate optiuni "else if". B. Instrucţiunea switch

Această instrucţiune e folosită pentru a compara o valoare cu altele dintr-o listă şi, în funcţie de acea valoare, se execută codul asociat ei în lista "switch".

Sintaxa generala a instructiuni "switch" este:

switch (expresie) { case valoare1: cod executat dacă expresie = valoare1 break; case valoare2: cod executat dacă expresie = valoare2 break; case valoare3: cod executat pt. expresie = valoare3 break; default : cod executat dacă expresie e diferit de valoare1, valoare2 sau valoare3 }

71

Prima dată este evaluată expresia scrisă între paranteze rotunde, la "switch( )", apoi valoarea expresiei este comparată pe rând cu fiecare valoare determinată de "case".

Dacă se găseşte o identitate, se execută codul asociat acelui "case", apoi se iese din instrucţiunea "switch".

Dacă, parcurgand fiecare "case", nu se găseşte o egalitate, se execută codul de la "default".

Prin folosirea lui "break" se opreşte parcurgerea corpului instrucţiunii atunci când s-a găsit o valoare egală cu 'expresie' şi se iese din "switch". Instructiunea "switch" poate inlocui un şir de condiţii cu "else if". C. Operatori logici şi instrucţiunile condiţionale

Operatorii logici sunt "&&" si "||". Rolul lor este asemănător cu cel al operatorilor relaţionali şi de egalitate, în sensul că şi

aceştia compară valoarea a doi operanzi. Operatorii logici compară operatii, expresii de cod, iar rezultatul lor este unul din valorile

TRUE (Adevărat) sau FALSE (Fals). • exp1 && exp2 - Returnează True dacă şi "exp1" şi "exp2" sunt Adevărate; altfel,

returneaza False. • exp1 || exp2 - Returneaza True dacă oricare dintre "exp1" sau "exp2" e Adevarat;

altfel, dacă amândouă sunt false, returnează False. • exp1 && exp2 || exp3 - Returnează True dacă expresia (exp1 && exp2) sau "exp2"

e Adevarată; altfel, returnează False. Datorita rezultatului True sau False pe care-l dau aceşti operatori logici, ei sunt folosiţi în

instrucţiunile condiţionale, contribuind la efectuarea unor condiţii mai complexe în parantezele instructiunii "if()" si "else if()". D. Operatorul condiţional "? :"

O alta metodă de a executa un cod în funcţie de faptul dacă o expresie este Adevarată sau Falsă e operatorul "? :"

Acest operator condiţional, deşi la prima vedere arată diferit de ceilalţi, este o formă prescurtată a instrucţiunii "if( ) else". Sintaxa generală de folosire a lui este:

• expresie-condiţionala ? dacă -TRUE : dacă -FALSE; Operatorul condiţional evaluează expresia condiţională. Dacă expresia are valoarea

TRUE, operatorul condiţional returnează valoarea de la "daca-TRUE"; în caz contrar, returnează valoarea de la "daca-FALSE".

Pe lângă atribuirea unei valori în funcţie de rezultatul unei expresii, acest operator condiţional poate fi utilizat în aceeaşi forma şi la determinarea apelării unei anumite funcţii, după rezultatul unei expresii logice.

• (expresie-logică) ? dacăTrue( ) : dacăFalse( );

unde "dacăTrue( )" şi "dacăFalse( )" pot fi considerate doua funcţii.

72

EXEMPLE

A. Sistemul de două ecuaţii de gradul I

#include <conio.h> #include <stdio.h> void main(){ /* Rezolvarea sistemului liniar de doua ecuatii cu doua necunoscute ax+by=c dx+ey=f */ double a,b,c,d,e,f,x,y,det,det1,det2; printf("\n\nIntroduceti coeficientii a,b,c,d,e,f\n"); /* Coeficientii se introduc pe aceeasi linie, separati de blancuri */ if (scanf("%lf %lf %lf %lf %lf %lf",&a, &b, &c, &d, &e, &f) != 6) printf("Coeficienti eronati\n"); else if ((det=a*e-b*d) == 0) printf("Sistemul are determinantul nul\n"); else { det1=c*e-b*f; det2=a*f-c*d; x=det1/det; y=det2/det; printf("x=%g\ty=%g\n",x,y); } getch(); }

B. Ecuaţia de gradul II

Să se rezolve ecuaţia de gradul II 02 =++ cbxax , coeficienţii a, b şi c fiind citiţi de la tastatură.

Identificând toate situaţiile care pot să apară, obţiem organigrama

73

În care semnificaţia mesajelor este următoarea: m1 : Aceasta nici macar nu e o ecuatie! m2 : Imposibil! m3 : Este, de fapt, o ecuatie de gradul I m4 : Asta da! Este o ecuatie de gradul II m5 : Radacini reale distincte m6 : Radacini reale confundate m7 : Radacini complexe Prin identificarea modului în care instrucţiunile IF-THEN, respectiv IF-THEN-ELSE se include unele pe altele şi a instrucţiunilor simple şi compuse, se obţine organigrama mai explicită:

74

Codul corespunzător este:

#include <conio.h> #include <iostream.h> #include <math.h> void main(){ float a, b, c, d, x, x1, x2, re, im; clrscr(); cout<<"a=";cin>>a; cout<<"b=";cin>>b; cout<<"c=";cin>>c; if(a==0) if(b==0) if(c==0) cout<<"Aceasta nici macar nu e o ecuatie!"; else cout<<"Imposibil!"; else{ cout<<"Este, de fapt, o ecuatie de gradul I"<<endl; x=-c/b; cout<<"Radacina este x="<<x; } else{ cout<<"Asta da! Este o ecuatie de gradul II"<<endl; d=b*b-4*a*c; if(d>0) { cout<<"Radacini reale distincte"<<endl; x1=(-b-sqrt(d))/2/a; x2=(-b+sqrt(d))/2/a;

75

cout<<"x1="<<x1<<endl; cout<<"x2="<<x2; } else if(d==0){ cout<<"Radacini reale confundate"<<endl; x=-b/2/a; cout<<"x1=x2="<<x; } else{ cout<<"Radacini complexe"<<endl; re=-b/2/a; im=-sqrt(-d)/2/a; if(im<0)im=-im; cout<<"x1="<<re<<" - "<<im<<" i"<<endl; cout<<"x2="<<re<<" + "<<im<<" i"; } } getch(); }

C. Realizarea unui meniu

Să se realizeze “scheletul” unui meniu pentru lucrul ulterior cu listele înlănţuite;

programul va permite selectarea dintr-un meniu a unor acţiuni şi va afişa acţiunea viitoare, pe care programul o va efectua în momentul în care vor fi implementate funcţiile respective.

Meniul va oferi ca principale opţiuni crearea listei, listarea de la stanga la dreapta, listarea de la dreapta la stanga, inserarea unui nod in interiorul listei, inserarea unui nod pe prima poziţie, inserarea unui nod pe ultima poziţie, ştergerea unui nod din interiorul listei, ştergerea primului nod, ştergerea ultimului nod şi salvarea listei.

Codul corespunzător este:

#include <iostream.h> #include <conio.h> #include <stdlib.h> void main(){ int rasp; clrscr(); cout<<"OPERATII CU LISTE :"<<endl<<endl; cout<< " 1: creare"<<endl<< " 2: listare de la stanga la dreapta"<<endl<< " 3: listare de la dreapta la stanga"<<endl<< " 4: inserare nod in interiorul listei"<<endl<< " 5: inserare nod pe prima pozitie"<<endl<< " 6: inserare nod pe ultima pozitie"<<endl<<

76

" 7: stergerea unui nod din interiorul listei"<<endl<< " 8: stergerea primului nod"<<endl<< " 9: stergerea ultimului nod"<<endl<< "10: salvez lista"<<endl; cin>>rasp; switch (rasp){ case 1: cout<<"voi crea o lista";break; case 2: cout<<"voi lista de la stanga la dreapta";break; case 3: cout<<"voi lista de la dreapta la stanga";break; case 4: cout<<" voi insera un nod in interiorul listei";break; case 5: cout<<" voi insera un nod inaintea primului nod";break; case 6: cout<<" voi insera un nod dupa ultimul nod";break; case 7: cout<<" voi sterge un nod din interiorul listei";break; case 8: cout<<" voi sterge primul nod";break; case 9: cout<<" voi sterge ultimul nod";break; case 10: cout<<" voi salva lista";break; default: exit(1); } getch(); }

77


A. Să se verifice dacă un număr întreg n, citit de la tastatură, este par.

B. Valorile a şi b (citite de la tastatură) sunt capetele unui interval. Să se stabilească dacă valoarea x (citită de la tastatură) se găseşte în interiorul intervalului.

C. Să se calculeze valoarea expresiei

>++=

<−

=0100

01

)(2 xpentruxx

xpentru

xpentrux

xE

pentru patru valori ale parametrului x, citite de la tastatură

D. Se citesc de la tastatură valorile pentru variabilele întregi a, b şi c. Se va afişa pe monitor valoarea maximului dintre a, b şi c.

E. Aceeaşi cerinţă, pentru patru valori reale a, b, c şi d.

F. Să se afişeze în ordine crescătoare valorile de la problema A.

G. Se citesc trei numere reale, în variabilele a, b, c. Dacă cele trei valori pot forma unghiurile unui triunghi, să se verifice dacă toate unghiurile sunt ascuţite; în caz contrar, verificati dacă există un unghi obtuz sau un unghi drept. Scrieti un mesaj corespunzator pentru fiecare caz.

H. Să se rezolve sistemul liniar de trei ecuaţii liniare cu trei necunoscute reale.

I. Se citeşte de la tastatură un număr întreg n, de exact patru cifre.

a. Să se calculeze suma dintre cifra sutelor şi cifra zecilor b. Să se afişeze numărul n inversat c. Să se verifice dacă numărul n este palindrom

78

7. CICLUL FOR ŞI INSTRUCŢIUNILE REPETITIVE DE TIP WHILE ŞI DO-WHILE

3.3.1 Instrucţiunea for este o structură ciclică cu test iniţial şi implementează structura ciclică cu număr cunoscut de paşi Sintaxa: for (expresie1; expresie2; expresie3) instructiune; Funcţionarea: evaluare expresie1 ATÂTA TIMP CÂT expresie2 este TRUE REPETĂ begin instrucţiune evaluare expresie3 end Nu este obligatorie prezenţa expresiilor, ci doar a instrucţiunilor vide. 3.3.2 Instrucţiunea while este o structura ciclică cu test iniţial Sintaxa: while(<expresie>) instr1; La întâlnirea acestei instrucţiuni, se evaluează expresie. Dacă aceasta are valoarea TRUE (diferită de ZERO), se execută instrucţiunea instr1. Se reevaluează valoarea expresie-i. Dacă ea este tot 1, se repetă instrucţiune, etc. Astfel, instrucţiunea (corpul ciclului) se repetă atât timp cât expresie are valoarea de adevăr TRUE.

În momentul în care <expresie> are valoarea de adevăr FALSE (egală cu ZERO), se iese din ciclu şi se trece la următoarea instrucţiune din afara buclei while. În cazul în care la prima evaluare a expresiei, aceasta are valoarea de adevăr FALSE, corpul instrucţiunii while nu va fi executat niciodată. instr1 din corpul ciclului while poate fi compusă (un bloc).

79

Instrucţiunea/instrucţiunile din corpul ciclului while trebuie să modifice valoarea expresiei, altfel va fi un „ciclu infinit”. 3.3.3 Instrucţiunea do while Sintaxa: do instr1; while(<expresie>)

Funcţionarea: Se execută instrucţiunea instr1 sau blocul de instrucţiuni. Se evaluează apoi <expresie>. Dacă aceasta are valoarea TRUE, se execută din nou instr1, altfel se iese din buclă. Se testează din nou valoarea expresiei. Se repetă execuţia instrucţiunii instr1 atâta cât timp valoarea expresiei este TRUE. În cazul instrucţiunii do while, corpul ciclului se execută cel puţin o dată. Instrucţiunea break

forţează ieşirea din interiorul unei bucle, fără a se mai ţine seama de condiţia de menţinere în buclă. Instrucţiunile situate în corpul buclei după instrucţiunea break nu vor mai fi executate. Intrucţiunea continue duce la ignorarea instrucţiunilor din buclă, situate după aceasta, şi testarea din nou a expresiei de menţinere în buclă. În cazul buclelor for, se realizează şi evaluarea celei de a treia expresii , responsabilă cu incrementarea contorilor.

EXEMPLE

A. Determinarea faptului dacă un număr este sau nu prim

#include <conio.h> #include <iostream.h> #include <math.h> void main() { clrscr(); unsigned long n, d; int prim=1; cout<<"n=?";cin>>n; for(d=2;d<=sqrt(n);d++) if(n%d==0) prim=0; if(prim) cout<<n<<" este prim";

80

else cout<<n<<" nu este prim"; getch(); }

B. Calculul cmmdc al două numere, utilizând algoritmul lui Euclid

#include<iostream.h> #include<conio.h> void main(){ clrscr(); int a, b, p=0; cout<<"a=";cin>>a; cout<<"b=";cin>>b; if(a==b)cout<<"cmmdc="<<a; else while(a!=b){if(a>b)a=a-b;else b=b-a;p++;} cout<<"cmmdc="<<a<<" in "<<p<<" pasi"; getch(); } #include<iostream.h> #include<conio.h> void main(){ clrscr(); int a, b, r, p; cout<<"a=";cin>>a; cout<<"b=";cin>>b; while(b){ r=a%b; a=b; b=r; p++; } cout<<"cmmdc="<<a<<" in "<<p<<" pasi"; getch(); }

81


A. Se citeşte de la tastatură o valoare naturală n. Să se afişeze numărul divizorilor numarului citit.

B. Scrieţi un program care afişează numerele divizibile cu 3 din intervalul [a,b]. Valorile

a şi b se citesc de la tastatură.

C. Se citeşte un număr natural n. Să se afişeze suma cifrelor lui n.

D. Scrieti un program care afişează numerele prime până la n. Valoarea lui n se citeşte de la tastatură.

E. De câte ori apare o cifră dată c, în numarul n?

F. Să se determine dacă un număr n este palindrom

G. Să se calculeze suma cifrelor unui număr întreg

H. Se citeşte un număr întreg n şi n valori pentru parametrul real x. Să se afişeze

maximul şi minimul valorilor introduse.

I. Scrieţi un program care determină perimetrul şi aria unui triunghi. Există 4 situaţii posibile. Un triunghi poate fi: 1. isoscel 2. echilateral 3. dreptunghic 4. oarecare. În funcţie de cifra introdusă de la tastatură (1, 2, 3 sau 4) se va cere utilizatorului numărul minim de informaţii care trebuie să se citească pentru fiecare tip de triunghi datele necesare, astfel încât să se poată calcula perimetrul şi aria triunghiului.

82

8. TABLOURI UNIDIMENSIONALE PROBLEME DE ORDONARE

Tablourile sunt colecţii de date de acelaşi tip reunite sub un singur nume, care ne

permit să programăm mai uşor operaţii asupra grupurilor de valori de acelaşi tip. Declararea tabloului este similară cu declaraţia unei variabile simple, cu o

singură excepţie: trebuie declarată şi dimensiunea tabloului. Numărul de componente se declară între [ ]. Declaraţia

float date[50];

creează un tablou cu 50 de elemente tip float.

Primul element are indicele 0, al doilea are indicele 1, …, iar ultimul are indicele 49. Un tablou unidimensional (numit de foarte multe ori vector) este deci o colecţie

structurată de elemente care pot fi accesate individual, specificând poziţia componentei printr-un indice (variabilă de tip întreg).

Sintaxa unei declaraţii de tablou unidimensional (vector): TipDată NumeTablou[ExpresieConstInt];

Elementele unui tablou pot avea aproape orice tip de dată. Expresia dintre parantezele drepte este o constantă întreagă, ce trebuie să fie strict

mai mare decât 0 şi determină numărul de componente ale tabloului. Dacă valoarea este n, domeniul indicilor va fi între 0 şi n-1, deci vectorul are n elemente.

Pentru a avea acces la componentele individuale ale unui vector, scriem numele vectorului urmat de o expresie indice între [ ]. Expresia specifică numărul componentei accesate şi poate fi o constantă întreagă, o variabilă întreagă, sau o expresie care este evaluată la o valoare întreagă. Oricare ar fi, însă, forma indicelui, acesta trebuie să fie o valoare întreagă.

Fiecare componentă a unui tablou poate fi tratată exact ca o variabilă simplă. Elementele unui tablou pot fi iniţializate în instrucţiunea de declarare prin

adăugarea unei liste de valori separate prin virgulă, plasate între acolade.

Exemplu

#include <iostream.h> #include <conio.h>

void main( ){ float x[5] = {11.2, 3.172, 12.1, -27.3, 12};

int i ; for(i = 0 ; i <5 ; i++) cout << "x[" << i << "]= " << x[i] << endl ;

}

83

Dacă se înscriu mai multe valori, compilatorul semnalează o eroare. Dacă sunt mai

puţine valori în listă, restul sunt iniţializate cu valoarea 0. Tablourile sunt transmise funcţiilor prin referinţă. În lista parametrilor formali, declararea unui tablou nu include şi dimensiunea sa

între [ ]. Dacă se include dimensiunea, compilatorul o ignoră, deoarece compilatorului îi este necesară doar informaţia referitoare la natura parametrului, adică faptul că este vorba despre un tablou, şi la tipul componentelor sale. Acesta este motivul pentru care trebuie adăugat un al doilea parametru al funcţiei prin care se precizează numărul de componente.

În prototipul unei funcţii care are parametri de tip tablou nu este necesară prezenţa numelor parametrilor formali.

EXEMPLE A. Aflarea valorilor maxime şi minime şi a poziţiilor pe care acestea le ocupă într-un vector

#include <conio.h> #include <iostream.h> void main() { clrscr(); int v[50], i, n, max, pozmax, min, pozmin; cout<<"n=?"; cin>>n; for(i=1;i<=n;i++){ cout<<"v["<<i<<"]=?"; cin>>v[i]; } max=v[1];pozmax=1; min=v[1];pozmin=1; for(i=2;i<=n;i++){ if(v[i]>max){ max=v[i];pozmax=i; } if(v[i]<min){ min=v[i];pozmin=i; } } cout<<"maximul este "<<max<<" si ocupa pozitia "<<pozmax<<endl; cout<<"minimul este "<<min<<" si ocupa pozitia "<<pozmin; getch(); }

84

B. Ordonarea crescătoare a elementelor unui vector

#include <conio.h> #include <iostream.h> void main() { clrscr(); int v[50], i, j, n, aux; cout<<"n=?"; cin>>n; for(i=1;i<=n;i++){ cout<<"v["<<i<<"]=?"; cin>>v[i]; } for(j=1;j<=n-1;j++){ for(i=1;i<=n-1;i++) if(v[i]>v[i+1]){ aux=v[i]; v[i]=v[i+1]; v[i+1]=aux; } } for(i=1;i<=n;i++) cout<<"v[i"<<"]="<<v[i]<<endl; getch(); }

C. ordonarea descrescătoare a elementelor unui vector

#include <conio.h> #include <iostream.h> void main() { clrscr(); int v[50], i, j, n, aux; cout<<"n=?"; cin>>n; for(i=1;i<=n;i++){ cout<<"v["<<i<<"]=?"; cin>>v[i]; } for(j=1;j<=n-1;j++){ for(i=1;i<=n-1;i++) if(v[i]<v[i+1]){ aux=v[i]; v[i]=v[i+1]; v[i+1]=aux; } }

85

for(i=1;i<=n;i++) cout<<"v[i"<<"]="<<v[i]<<endl; getch(); }

C. Numere Fibonacci

#include <conio.h> #include <iostream.h> void main(){ clrscr(); unsigned long n, a, b, f[50], j; int i, fv[50]; //afisarea numerelor fibonacci f[1]=1; f[2]=2; for(i=3; i<=46; i++) f[i]=f[i-2]+f[i-1]; for(i=1; i<=46; i++) cout<<i<<" "<<f[i]<<endl; //descompunerea unui numar n in suma de numere fibonacci getch(); cout<<"n=?"; cin>>n; for(i=1; i<=46; i++) fv[i]=0; for(i=46; i>=1;i--) if(f[i]<=n){ n=n-f[i]; cout<<f[i]<<" "; } cout<<endl; getch(); //vizualizarea numerelor de la a la b prin componentele fibonacci cout<<"a=";cin>>a; cout<<"b=";cin>>b; for(j=a; j<=b; j++){ n=j; for(i=1; i<=46; i++) fv[i]=0; for(i=46; i>=1;i--) if(f[i]<=n){ n=n-f[i]; fv[i]=1;

86

} for(i=46; i>=1;i--) cout<<fv[i]; cout<<endl; } getch(); }

87


A. Se introduce o valoare întregă n, un vector v cu n elemente întregi, o valoare întreagă k şi un caracter c. Să se rotească circular spre stânga sau spre dreapta (în funcţie de valoarea caracterului c) cu exact k poziţii.

B. Să se construiască vectorul w, având ca elemente numerele prime dintr-un vector v

dat.

C. Să se rearanjeze elementele unui vector v, astfel încât la început să fie numerele impare, în ordine crescătoare, apoi cele pare, în ordine descrescătoare.

D. Să se introducă între fiecare dintre elementele succesive ale unui vector media lor

aritmetică.

E. Să se descompună în factori primi un număr întreg n, afişându-se doi vectori: vectorul b al bazelor şi vectorul e al exponenţilor corespunzători.

88

9. TABLOURI BIDIMENSIONALE

Tablourile bidimensionale sunt denumite si matrici. La declararea unui tablou bidimensional, se specifică numărul de elemente al fiecărei dimensiuni, incluzând fiecare dintre aceste numere între paranteze drepte. Indexul inferior al fiecarei dimensiuni este 0.

Sintaxa pentru declararea unei matrice este urmatoarea:

tipul_datelor nume_matrice[nr_linii][nr_coloane];

Exemplu: o matrice de numere intregi , care are 5 linii a câte 4 componente pe linie :

int a[5][4];

Rămân valabile cele menţionate la capitolul referitor la tablorile unidimensionale.

EXEMPLE

A. Suma a două matrice

#include <stdio.h> #include <conio.h> void main() /* Suma a doua matrici cu m linii si n coloane */ { int a[10][10],b[10][10],c[10][10]; int n,m,i,j,k; printf("\nIntroduceti numarul de linii : "); scanf("%d",&m); printf("\nIntroduceti numarul de coloane : "); scanf("%d",&n); printf("\nIntroduceti elementele matricii A\n"); for (i=0;i<=m-1;i++) for (j=0;j<=n-1;j++) { printf("a[%d][%d]=",i,j); scanf("%d",&a[i][j]); }; printf("\nIntroduceti elementele matricii B\n"); for (i=0;i<=m-1;i++) for (j=0;j<=n-1;j++) { printf("b[%d][%d]=",i,j); scanf("%d",&b[i][j]); };

89

for (i=0;i<=m-1;i++) for (j=0;j<=n-1;j++) c[i][j]=a[i][j]+b[i][j]; printf("\nElementele matricei C sunt :\n"); for (i=0;i<=m-1;i++) for (j=0;j<=n-1;j++) printf("c[%d][%d]=%d\n",i,j,c[i][j]); getch(); }

B. Produsul a două matrice

#include <stdio.h> #include <conio.h> void main() /* Produsul a doua matrici cu A(mxn) si B(nxp) */ { int a[10][10],b[10][10],c[10][10]; int n,m,p,i,j,k,s; printf("\nIntroduceti numarul de linii al primei matrici : "); scanf("%d",&m); printf("Introduceti numarul de coloane al primei matrici : "); scanf("%d",&n); printf("Introduceti numarul de coloane al celei de a doua matrici : "); scanf("%d",&p); printf("\nIntroduceti elementele matricii A\n"); for (i=0;i<=m-1;i++) for (j=0;j<=n-1;j++) { printf("a[%d][%d]=",i,j); scanf("%d",&a[i][j]); }; printf("\nIntroduceti elementele matricii B\n"); for (i=0;i<=n-1;i++) for (j=0;j<=p-1;j++) { printf("b[%d][%d]=",i,j); scanf("%d",&b[i][j]); }; for (i=0;i<=m-1;i++) for (j=0;j<=p-1;j++) { c[i][j]=0; for (k=0;k<=n-1;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j]; } printf("\nElementele matricii C sunt :\n"); for (i=0;i<=m-1;i++) for (j=0;j<=n-1;j++)

90

printf("c[%d][%d]=%d\n",i,j,c[i][j]); getch(); C. Transpusa unei matrice

#include <stdio.h> #include <conio.h> void main() /* Transpusa unei matrici A(mxn) */ { int a[10][10],b[10][10]; int n,m,i,j; printf("\nIntroduceti numarul de linii : "); scanf("%d",&m); printf("Introduceti numarul de coloane : "); scanf("%d",&n); printf("\nIntroduceti elementele matricii A\n"); for (i=0;i<=m-1;i++) for (j=0;j<=n-1;j++) { printf("a[%d][%d]=",i,j); scanf("%d",&a[i][j]); }; for (i=0;i<=n-1;i++) for (j=0;j<=m-1;j++) b[i][j]=a[j][i]; printf("\nElementele matricii transpuse sunt :\n"); for (i=0;i<=n-1;i++) for (j=0;j<=m-1;j++) printf("b[%d][%d]=%d\n",i,j,b[i][j]); getch(); }

91


A. Să se afişeze elementele de pe bordura unei matrici

B. Să se afişeze elementele de sub diagonala principală a unei matrici pătrate

C. Să se afişeze elementele de deasupra diagonalei secundare a unei matrici pătrate

D. Să se interclaseze coloanele unei matrici, astfel încât elementele de pe linia k să fie ordonate crescător

E. Determinaţi elementele şa ale unei matrici (elementele minime pe linie şi maxime pe

coloane, sau invers)

92

10. FUNCŢII DEFINITE DE UTILIZATOR

Pentru utilizarea funcţiilor în C++, este necesară cunoaşterea următoarelor aspecte de bază:

a) Funcţiile grupează setul de operatori pentru îndeplinirea unei sarcini concrete. b) Programul principal apelează la funcţie, adresîndu-se la numele ei, după care

urmează paranteze rotunde. c) După terminarea prelucrării informaţiei, majoritatea funcţiilor întorc programului

principal valori de tipuri concrete, care pot fi olosite în calcule. d) Programul principal transmite funcţiilor parametrii (informaţia iniţială), inclusă în

paranteze rotunde, care urmează după numele funcţiei. e) Limbajul C++ foloseşte prototipuri de funcţie pentru determinarea tipului valorii

returnate de câtre funcţie, a cantităţii si tipurilor parametrilor transmişi funcţiei. În timpul creării programului, e necesar să se rezerve fiecare funcţie pentru rezolvarea

unei sarcini. Fiecare funcţie creată trebuie să primeascăun nume unic. Ca şi în cazul variabilelor, numele unei funcţii este un identificator şi e de dorit să

corespundă cu sensul logic al sarcinei pe care o îndeplineşte. Funcţiile din C++ se aseamănă structural cu funcţia principală main(). În faţa numelui funcţiei se indică tipul ei, iar după numele funcţiei urmează lista

de parametri descrişi înăuntrul parantezelor rotunde. Corpul funcţiei (compus din operatori) este amplasat după descrierea parametrilor,

între acolade. Sintaxa descrierii unei funcţii: tip_f nume_f (lista parametri) {declarare de variabile; operatori;}

unde tip_f - tipul funcţiei sau tipul valorii returnate de funcţie, nume_f - numele funcţiei.

Dacă funcţia nu întoarce valori, tipul ei este void.

1. Transmiterea parametrilor în funcţie.

Dacă funcţia foloseşte parametri, ei trebuie descrişi în cadrul descrierii funcţiei. În timpul descrierii parametrelor funcţiei se indică numeleşi tipul fiecărui parametru.

tip_parametru nume_parametru;

93

Dacă funcţia conţine mai mulţi parametri, ei vor fi descrişi împreună între parantezele rotunde după numele funcţiei, despărţiţi prin virgulă

tip_funcţie nume_funcţie (tip_parametru1 nume_parametru1, tip_parametru2 nume_parametru2 …. tip_parametruN nume_parametruN );

În unele surse de descriere a limbajului de programare C/C++, parametrii ce se

transmit din program în funcţie se numesc actuali, iar parametrii ce sunt declaraţi în antetul funcţiei şi cărora li se atribuie valorile parametrilor actuali, se numesc parametri formali.

În momentul folosirii parametrilor în funcţie, este necesară cunoaşterea următoarelor aspecte:

- Dacă funcţia foloseşte parametri, ea trebuie să indice numele unic şi tipul fiecărui parametru. - Când programul apelează funcţia, compilatorul atribuie valoarea parametrilor de la stânga la dreapta - Valorile transmise din program în funcţie, trebuie să coincidă ca număr, loc şi tip cu parametrii din funcţie. 2. Întoarcerea valorilor din funcţie.

Obiectivul oricărei funcţii este îndeplinirea unei sarcini concrete. În majoritatea cazurilor, funcţiile vor efectua calcule. După aceasta, funcţia va întoarce rezultatul fie funcţiei din care a fost apelată, fie funcţiei principale main. În momentul când funcţia întoarce o valoare, trebuie să fie cunoscut tipul ei. Tipul valorii returnate de funcţie se indică în momentul descrierii funcţiei, înainte de numele ei. Tipul valorii returnate se mai numeşte şi tipul funcţiei. Funcţiile folosesc operatorul return pentru a întoarce valori funcţiilor din care au fost apelate.

Când compilatorul întâlneşte operatorul return, el întoarce valoarea dată şi încheie executarea funcţiei curente, controlul executării programului fiind cedat funcţiei din care a fost chemată funcţia curentă. Dacă după operatorul return, în funcţie mai există şi alţi operatori, ei vor fi ignoraţi, funcţia terminîndu-se odată cu îndeplinirea operatorului return.

Valoarea întoarsă de funcţie poate fi folosită în orice loc al programului, unde e posibilă folosirea unei valori de tip identic cu valoarea returnată. Când funcţia întoarce o valoare, această valoare poate fi atribuită unei variabile de acelaşi tip, folosind operatorul de atribuire. Valoarea mai poate fi folosită în cadrul instrucţiunilor de afişare, în cadrul instrucţiunilor de decizie sau a instrucţiunulor de ciclare.

De asemenea, ea poate fi folosită ca parametru în cadrl apelului altei funcţii. 3. Prototipul funcţiei.

Înainte de apelul unei funcţii, compilatorul C++ trebuie să cunoască tipul valorii returnate, cantitatea şi tipul parametrilor folosiţi de funcţie.

Există însă situaţii cînd unele funcţii în program sînt apelate reciproc. În aceste cazuri, este posibilă situaţia cînd o funcţie va fi apelată înaintea descrierii sale.

94

În acest caz, se folosesc prototipuri ale funcţiilor. Prototipul unei funcţii este amplasat la începutul programului şi conţine informaţia despre tipul valorii returnate, cantitatea şi tipul parametrilor folosiţi de funcţie. Odată declarat prototipul unei funcţii, înainte de a fi început corpul programului, descrierea funcţiei poate fi făcută după acolada de închidere a programului principal. 4. Variabile localeşi domeniul de vizibilitate.

Apare adeseori necesitatea folosirii în funcţii a variabilelor proprii.Variabilele declarate în cadrul funcţiei e numesc variabile locale. Numele şi valoarea unei variabile locale sunt cunoscute numai funcţiei în care ea a fost declarată. Chiar faptul că variabila locală există este cunoscut numai de către funcţia în are ea a fostd eclarată. Declararea variabilelor are loc la începutul funcţiei, imediat după acolada care deschide corpul acesteia. Numele variabilei locale trebuie să fie unic în funcţia în care a fost declarată. O variabilăse numeşte locală, din cauză că este văzută numai din funcţia în care a fost descrisă.

Sintaxa de declarare a unei variabile locale:

tip_f numele_f (lista parametrilor) {tip_vl numele_vl;}

unde: tip_f - tipul funcţiei; nume_f - numele funcţiei; tip_vl - tipul variabilei; numele_vl - numele variabilei;

Principiile de declarare şi folosire a unei variabile locale oricărei funcţii sunt identice cu principiile de declarare şi utilizare a unei variabile declarate în corpul funcţiei principalemain( );

O variabilă declarată în corpul funcţiei main() este şi ea locală acestei funcţii. În general, tot ceea ce este valabil pentru a fost spus despre variabilele declarate în funcţia main( ) - tipurile, numele, principiile de utilizare ş.a.- rămâne valabil şi pentru o variabilă locală, din orice altă funcţie. 5. Variabile globale

Numim variabilă globală o variabilă pentru care numele şi valoarea sunt cunoscute pe parcursul întregului program, orice funcţie din acest program.

Pentru a crea o variabilă globală, se foloseşte declararea ei la începutul programului, în afara oricărei funcţii. Orice funcţie (inclusiv funcţia main), care va urma după această declarare, poate folosi această variabilă globală.

Declararea unei variabile globale:

# include<…> # include<…> … # include<…>

95

tip_vg nume_vg; eventuale declaraţii de funcţii void main (void){…}

unde tip_vg este tipul variabilei globale, iar nume_vg – numele variabilei globale.

Fiind declarată o variabilă globală, valoarea ei nu numai că e cunoscută oricărei funcţii din program, dar şi poate fi şi schimbată de către oricare dintre funcţiile prezente în program.

Cu toate că prezenţa variabilelor globale în program adaogă noi posibilităţi, este de dorit să nu se facă abuz de folosirea lor. Din cauză că orice funcţie din program poate schimba valoarea variabilei globale, este dificil de urmărit toate funcţiile care ar putea schimba această valoare, ceea ce conduce la un control dificil asupra execuţiei programului

6. Conflicte dintre variabile localeşi globale

În cazul în care un program trebuie să folosească o variabilă globală, poate apărea o situaţie de conflict între numele variabilei globale şi numele unei variabile locale. În aceste cazuri, limbajul C++ oferă prioritate variabilei locale.

Dacă există o variabilă globală cu acelaşi nume ca o variabila locală, compilatorul consideră, că orice apel al variabilei cu acest nume este un apel al variabilei locale.

Există situaţii, când apare necesitatea de a se adresa o variabilă globală care se află în conflict cu o variabilă locală. În acest caz, se poate folosi operatorul global de acces :: .

EXEMPLE

A. Transmiterea prin valoara şi prin referinţă #include <stdio.h> #include <conio.h> #include <math.h> float f1(int a,int b,int c) { a=a*a; b=b*b; c=c*c; return sqrt(a+b+c); }

96

float f2(int *a,int *b,int *c) { *a=*a**a; *b=*b**b; *c=*c**c; return sqrt(*a+*b+*c); } void main() { int x,y,z; printf("\nIntroduceti pe x : "); scanf("%d",&x); printf("Introduceti pe y : "); scanf("%d",&y); printf("Introduceti pe z : "); scanf("%d",&z); printf("Rezultatul aplicarii lui f1 : %g\n",f1(x,y,z)); printf("x=%d\n",x); printf("y=%d\n",y); printf("z=%d\n",z); printf("Rezultatul aplicarii lui f2 : %g\n",f2(&x,&y,&z)); printf("x=%d\n",x); printf("y=%d\n",y); printf("z=%d\n",z); getch(); }

B. Suma cifrelor unui număr

#include <fstream.h> #include <conio.h> void main(){ clrscr(); int x, y, z, rasp, gasit=0; char fis[20]; cout<<"numele fisierului de intrare : ";cin>>fis; ifstream f(fis); f>>x>>y; cout<<x<<" "<<y<<endl; while((!gasit)&&(x<=y)){ z=(x+y)/2; f>>rasp; if(rasp) gasit=1; else{ f>>rasp;

97

if(rasp)y=z-1; else x=z+1; } } if(gasit)cout<<z; else cout<<"0"; getch(); f.close; }

C. Factorialul primelor 170 de numere

double factorial(int); #include <stdio.h> #include <conio.h> void main() /* Afiseaza pe n! pentru m=0,1,2,...,170 */ { int m; for (m=0;m<171;m++) { printf("m=%d\tm!=%g\n",m,factorial(m)); if ((m+1)%23==0) { printf("Apasati o tasta pt.a continua\n"); getch(); } } getch(); } double factorial(int n) /* Calculeaza pe n! pentru n din intervalul [0,170]; pentru alte valori returneaza -1 */ { double f; int i; if (n<0||n>170) return -1.0; for (i=2,f=1.0;i<+n;i++) f*=i; return f; }

98

D. Aflarea unei rădăcini unice dintr-un interval dat

double f(double); double radac(double ls,double ld); #include <conio.h> #include <stdio.h> #include <math.h> void main() /* Calculeaza o radacina unica din intervalul [a,b] */ { double a,b,x,fx; printf("\n\nIntroduceti limita din stanga "); scanf("%lf",&a); printf("Introduceti limita din dreapta "); scanf("%lf",&b); if (fabs(f(a))<1e-30) printf("Radacina este chiar limita din stanga\n"); else if (fabs(f(b))<1e-30) printf("Radacina este chiar limita din dreapta\n"); else if (f(a)*f(b)>0) printf("Varianta nepermisa\n"); else printf("Radacina este x=%g\tf(x)=%g\n",radac(a,b),f(radac(a,b))); getch(); } double f(double x) { double val; val=x*x-3.0*x+2.0; return val; } double radac(double ls,double ld) /* Numarul de simboluri * arata de cate ori a fost apelata functia */ { double jum,val; jum=(ls+ld)/2; if (f(ls)*f(jum)<0) ld=jum; else ls=jum; if (fabs(f(jum))<1e-300) val=jum; else {val=radac(ls,ld);printf("*");} return val; }

99

E. Maxime din minime pe linii şi coloane #include <stdio.h> #include <conio.h> void maxmin(int a[10],int n,int& maxim,int& minim) { int i; maxim=a[1]; minim=a[1]; for (i=2;i<=n;i++) { if (maxim<a[i]) maxim=a[i]; if (minim>a[i]) minim=a[i]; }; }; void main() /* Maxime si minime in matrice */ { int a[10][10],ajut[10],mxln[10],mnln[10],mxcl[10],mncl[10]; int n,m,i,j,k,mxmxln,mxmnln,mnmxln,mnmnln,mxmxcl,mxmncl,mnmxcl,mnmncl; printf("\nIntroduceti numarul de linii : "); scanf("%d",&m); printf("\nIntroduceti numarul de coloane : "); scanf("%d",&n); printf("\nIntroduceti elementele matricii\n\n"); for (i=1;i<=m;i++) for (j=1;j<=n;j++) { printf("a[%d][%d]=",i,j); scanf("%d",&a[i][j]); }; printf("\n"); for (i=1;i<=m;i++) { for (j=1;j<=n;j++) ajut[j]=a[i][j]; maxmin(ajut,n,mxln[i],mnln[i]); printf("linia %d\t\tmax=%d\tmin=%d\n",i,mxln[i],mnln[i]); } maxmin(mxln,m,mxmxln,mnmxln); printf("\nMaximumul din maximele pe linii este %d",mxmxln); printf("\nMinimumul din maximele pe linii este %d",mnmxln); maxmin(mnln,m,mxmnln,mnmnln); printf("\nMaximumul din minimele pe linii este %d",mxmnln); printf("\nMinimumul din minimele pe linii este %d\n\n",mnmnln); getch(); for (j=1;j<=n;j++) {

100

for (i=1;i<=m;i++) ajut[i]=a[i][j]; maxmin(ajut,m,mxcl[j],mncl[j]); printf("coloana %d\tmax=%d\tmin=%d\n",j,mxcl[j],mncl[j]); } maxmin(mxcl,n,mxmxcl,mnmxcl); printf("\nMaximumul din maximele pe coloane este %d",mxmxcl); printf("\nMinimumul din maximele pe coloane este %d",mnmxcl); maxmin(mncl,n,mxmncl,mnmncl); printf("\nMaximumul din minimele pe coloane este %d",mxmncl); printf("\nMinimumul din minimele pe coloane este %d\n\n",mnmncl); getch(); }

101


A. Să se scrie funcţia citvect, care citeşte un vector de n elemente

B. Să se scrie funcţia scrvect, care afişează un vector de n elemente

C. Să se scrie funcţia citvmat, care citeşte o matrice cu nl linii şi nc coloane

D. Să se scrie funcţia scrvmat, care afişează o matrice cu nl linii şi nc coloane

E. Să se scrie funcţia perlin care permută liniile l1 şi l2 ale unei matrice

F. Să se scrie funcţia intercl care interclasează doi vectori ordonaţi crescător

G. Cunoscând vectorul de numere întregi v, să se creeze vectorul w, care conţine elementele prime din v, utilizând o funcţie care determină dacă un număr este prim

H. Să se scrie câte o funcţie care primeşte ca parametrii numerele întregi n şi b şi înscrie

într-un vector v cifrele numărului n scris în baza b

I. Să se scrie o funcţie pentru extragerea elementelor comune din doi vectori (neordona) într-un al treilea vector.

J. Să se scrie o funcţie care caculează aria intersecţiei a două dreptunghiuri, date prin

coordonatele colţurilor stânga-sus şi dreapta-jos. Coordonatele sunt numere întregi pozitive.

K. Să se scrie o funcţie care determină aria reuniunii a două dreptunghiuri date prin

coordonatele întregi ale colţurile stânga-sus şi dreapta-jos.

102

11. POINTERI

Pointerii au fost introdusi in limbajele de programare pentru a putea rezolva mai eficient anumite probleme.

Pointerul este o variabila ce contine adresa unui obiect. Obiectul a carei adresa este conţinută de pointer poate fi variabilă sau funcţie. Ex:

int a; int *b;

Variabila a este de tip întreg, iar variabila b este de tip pointer; ea conţine adresa unei

variabile de tip întreg (adresa la care se află o valoare de tip întreg). În cazul declarării variabilei, semnul * din stânga acesteia semnifică faptul ca acesta

conţine o adresă (variabila este de tip pointer) şi nu o valoare. În momentul utilizării variabilei semnul * din stânga acesteia are altă semnificaţie, acesta semnifică faptul că se preia valoarea variabilei de tip pointer.

Ex:

a=*b; variabila a preia valoarea de la adresa lui b (valoarea la care pointează b) Operatorul unar & este utilizat pentru obţinerea adresei. Ex:

b=&a; Alocarea dinamică a memoriei Utilizatorul poate solicita în timpul execuţiei programului alocarea unei zone de memorie. Această zonă de memorie poate fi eliberată, în momentul în care nu mai este necesară. Alocarea memoriei se poate realiza cu funcţiile din biblioteca având prototipul (declaraţiile) în <alloc.h> sau prin utilizarea operatorului new. void *malloc (unsigned n);

Funcţia alocă un bloc de memorie de n octeţi. Funcţia întoarce un pointer la începutul zonei de memorie alocată. În cazul în care nu este posibilă alocarea unei zone compacte de n octeţi funcţia returnează NULL(0x0000). Memoria alocată NU este iniţializată. La sfârţitul operaţiilor memoria trebuie eliberată. În cazul alocării cu funcţia malloc dealocarea memoriei se face cu funcţia:

103

void free(void *p); Funcţia eliberează o zonă de memorie indicată de p, alocată în prealabil prin malloc(). Funcţiile de alocare întorc pointeri generici (void*) la zone de memorie, în timp ce utilizatorul alocă memorie ce păstrează informaţii de un anumit tip. Pentru a putea accesa memoria alocată, indirect, prin intermediul pointerului, acesta va trebui să fie un pointer cu tip, ceea ce impune conversia explicită (prin cast) a pointerului întors de funcţia de alocare într-un pointer cu tip.

int *p; p=(int*)malloc(n*sizeof(int)) if(p==NULL) { printf(„Memorie insuficienta!”); ...... if(p) // identic cu if(p!=NULL) free(p);

sau

int *p; p=new int[n]; if(p==NULL) { printf(„Memorie insuficienta!”); ...... if(p) delete[] p;

Exemplu de alocare dinamică a unei matrici si de eliberare a zonei alocate.

#include <stdio.h> #include <conio.h> #include <alloc.h> //aloca dinamic o matrice cu m linii si n coloane double **aloca2double(int m,int n) {double **A; int k,i; A=(double**) malloc(m*sizeof(double*)); if(!A) return NULL; for(k=0;k<m;k++) {A[k]=(double*) malloc(n*sizeof(double)); if(!A) //alocare esuata, elibereaza mem. deja alocată { for(i=0;i<k;i++) free(A[i]); free(A); return NULL; }//endif }//endfor for(k=0;k<m;k++) for(i=0;i<n;i++) A[k][i]=0; return A; }

104

//----------------------------------------- //elibereaza zona de memorie alocata void elib2double(double**A, int m) {int k; for(k=0;k<m;k++) if(A[k]) free(A[k]); if(A) free(A); } //-------------------------------------- void main(void) { double **x; x=aloca2double(100,50); if(x==NULL) printf("Memorie insuficienta"); //..... operatii cu matricea x .... elib2double(x,100); }

ARITMETICA POINTERILOR Datorită faptului că adresele de memorie a elementelor dintr-un tablou sunt consecutive se pot efectua operaţii cu aceste adrese în cadrul tabloului. La incrementarea unei variabile pointer, C++ incrementează automat adresa cu o valoare adecvată (1 octet dacă tipul variabilei la care punctează este char, 2 octeţi pentru tipul de date short, patru octeţi pentru long sau float, etc.), astfel încât pointerul să indice următoarea valoare pe care o are tipul pointerului (tipul datei la care punctează). Pentru tipuri de date complexe (structuri, clase) se incrementează cu dimensiunea structurii sau clasei la care punctează. Ex:

#include <stdio.h> //biblioteca pentru functia printf -- afisare #include <conio.h> //biblioteca pentru functia getch – asteapta //apasarea unei taste –DOS void main(void) { int t[4]={0, 1, 2, 3}; int *p; p=&t[2]; p-=2;printf("%d\n", *p); /* afiseaza valoarea lui t[0] */ p+=1;printf("%d\n", *p); /* afiseaza valoarea lui t[1] */ p++;printf("%d\n", *p); /* afiseaza valoarea lui t[2] */ (*p)+=5;printf("%d\n", *p); /* afiseaza valoarea lui t[2]+5 */ getch(); }

105

Ex:

int a01,a02,*a1,b1[3][4] a3[10]; a1=b1[0];implica a1+2=b1[2]; b1[0]=&b1[0][0];implica b1[0]+5=&b1[1][0]; a3=&a3[0]; b1=&b1[0];b1=&b1[2]-2; b1[2][1]=*(&b1[2][1]); b1[2][1]=*(b1[2]+1); b1[2][1]=*(*(b1+2)+1); b1[2][3]=*(*(b1+2)+3) b1[2][3]=*(&b1[2]+3)

EXEMPLE

A. Pointeri şi adrese

#include <stdlib.h> #include <stdio.h> #include <conio.h> #include <iostream.h> void main(void){ int x, y, *adr; clrscr(); //variabila "x" (de tip int) ia o valoare cout<<"x=";cin>>x; //variabila "adr" (de tip pointer) ia ca valoare adresa variabilei x adr=&x; cout<<"valoarea lui x = "<<x<< " (valoare tiparita direct)"<<endl; cout<<"ceea ce e totuna cu "<<*adr<< " (valoare luata de la adresa lui x)"<<endl; cout<<"adresa lui x = "<<adr<< " (am tiparit valoarea variabilei adresa)"<<endl; cout<<"sau, altfel zis "<<&x<< " (am tiparit adresa variabilei a)"<<endl<<endl; //dar si variabila "adr" (de tip pointer) are o adresa cout<<"adresa variabilei x este tinuta la adresa "<<&adr; getch(); }

106

B. Aceeaşi funcţie utilizator, definită cu şi fără pointeri

#include <iostream.h> #include <conio.h> #include <stdio.h> #include <string.h> int cresc1(int &a,int k) {a+=k;return a;} int cresc2(int * a,int k) {*a+=k;return *a;} void main(void){ int x,y,d; clrscr(); cout<<"functie definita fara pointeri\n"; cout<<"pe cine cresc ?";cin>>x; cout<<"cu cat cresc ?";cin>>d; cout<<"obtin "<<cresc1(x,d)<<"\n\n"; cout<<"functie definita cu pointeri\n"; cout<<"pe cine cresc ?";cin>>y; cout<<"cu cat cresc ?";cin>>d; cout<<"obtin "<<cresc1(y,d)<<endl; getch(); }

C. Legătura dintre pointeri şi tablouri

#include <conio.h> #include <iostream.h> void main(){ int a, b, * pa, * pb, v[100], i, n; float x[100], * px; clrscr(); cout<<"a=?";cin>>a; cout<<"b=?";cin>>b; pa=&a; pb=&b; cout<<a<<" "<<pa<<" "<<*pa<<endl;

107

cout<<b<<" "<<pb<<" "<<*pb<<endl; getch(); /* cout<<"Cate elemente are vectorul v? ";cin>>n; for(i=0;i<n;i++){ cout<<"Introduceti pe v["<<i<<"] ";cin>>v[i]; } for(i=0;i<n;i++){ cout<<"v["<<i<<"]= "<<v[i]<<endl; } pa=v; cout<<*pa<<endl; pa=pa+3; cout<<*pa<<endl; */ cout<<"Cate elemente are vectorul x? ";cin>>n; for(i=0;i<n;i++){ cout<<"Introduceti pe x["<<i<<"] ";cin>>x[i]; } for(i=0;i<n;i++){ cout<<"x["<<i<<"]= "<<x[i]<<endl; } px=x; cout<<*px<<endl; px=px+3; cout<<*px<<endl; getch(); }

D. Aritmetica pointerilor

#include <stdio.h> #include <conio.h> void main() { int a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8}; unsigned long int adr0, adr1, adr2; int *p1, *p2; clrscr(); printf("a = %p\na + 1 = %p\na + 3 = %p\n\n", a, a + 1, a + 3); printf("sizeof(a) = %d\n", sizeof(a));

108

printf("sizeof(a + 1) = %d\n", sizeof(a + 1)); printf("sizeof(a + 3) = %d\n\n", sizeof(a + 3)); adr0 = (unsigned long int) a; adr1 = (unsigned long int) (a + 1); adr2 = (unsigned long int) a + 1; printf("adr0 = %lu\nadr1 = %lu\nadr2 = %lu\n\n", adr0, adr1, adr2); p1 = a + 4; p2 = &(a[4]); printf("p1 = %p \t *p1 = %d\n", p1, *p1); printf("p2 = %p \t *p2 = %d\n", p2, *p2); printf("a + 4 = %p \t a[4] = %d\n", a + 4, a[4]); *p1 = *p1 + 1; printf("\na[4] = %d\n", a[4]); getch(); }

109


A. Să se scrie un program care afişează ca întreg în baza 10 conţinutul primului octet al unei variabile de tip float

B. Să se scrie o funcţie pentru incrementarea unui moment de timp, dat ca oră, minut şi

secundă și perioada zilei (AM sau PM). Funcția va trebui să modifice 3 numere întregi şi un vector de caractere şi va primi 3 argumente pointer şi un argument vector.

C. Să se scrie o funcţie care calculează panta şi ordonata pentru o dreaptă dată prin 2

puncte. Ecuaţia dreptei dată prin pantă şi ordonată este y = m * x + n. Funcţia va avea antetul: void panta(int x1, int y1, int x2, int y2, float *m, float *n);

110

12. ŞIRURI DE CARACTERE

În limbajul C/C++, şirurile de caractere sunt vectori având tipul de bază char. Un şir de caractere se termina prin marcatorul \0, sau caracterul nul. De exemplu, şirul "x2A" este memorat pe 4 caractere, ultimul fiind \0, numărul de

elemente al şirului fiind, deci, 3, iar dimensiunea şirului 4. Un caracter dintr-un şir (vector) de caractere "a" poate fi accesat folosind indexul

şirului (a[i], de exemplu) sau folosind pointeri la caracter. Iniţializarea (citirea) unui şir de caractere se poate face în mai multe moduri:

a. Iniţializarea fiecărui element cu câte un character (ca la orice vector): a[0] = 'x'; a[1] = '2'; a[2] = 'A'; a[3] = '\0'; b. Folosind funcţia "scanf( )": scanf("%s", a); Formatul "%s" este folosit pentru citirea unui sir de caractere. Se efectuează trei pasi: - poziţionarea pe primul caracter al şirului; - citirea tuturor caracterelor diferite de <Enter> şi introducerea lor în vectorul "a"; - citirea se face până la întâlnirea EOF, după care se plasează '\0' la sfârşitul şirului. Deoarece numele unui şir (ca la orice vector) este un pointer la adresa de bază a şirului, expresia "a" este echivalentă cu "&a[0]". Dacă şirul citit are mai multe caractere decat cele rezervate, se va obţine o eroare. Este important de reţinut că 'b' şi "b" sunt două lucruri diferite, prima fiind o constantă caracter, în timp ce a doua este o constantă şir de caractere, care conţine pe prima poziţie constanta caracter 'b' şi pe a doua poziţie caracterul '\0' 3. Şirurile se pot iniţializa la fel ca şi caracterele char a[] = "x2A"; sau, echivalent char a[] = {'x', '2', 'c', '\0'}; 4. Putem folosi un pointer către un şir constant, dar interpretarea este diferită: char *p = "x2A";

111

Numele unui şir (ca la orice vector) poate fi tratat ca un pointer către adresa de bază a şirului din memorie. Constanta "x2A" este memorată de către compilator. În acelaşi timp, aceasta este "un nume de şir". Diferenţa dintre un şir iniţializat cu o constantă şir şi un pointer iniţializat tot cu o constantă şir este că şirul conţine caractere individuale urmate de caracterul "\0", în timp ce pointerul este asignat cu adresa şirului constant din memorie.

#include <stdio.h> #include <ctype.h> main() { char c, nume[200]; int i, sum = 0; printf("\nIntroduceti numele "); for (i = 0; (c = getchar()) != '\n'; ++i) { nume[i] = c; if (isalpha(c)) sum += c; } nume[i] = '\0'; printf("\n%s%s%s\n%s", "Buna ziua ",nume,".", "Numele tau scris invers este "); for (--i; i >= 0; --i) putchar(nume[i]); printf("\n%s%d%s\n\n%s\n", "si numele tau are ", sum," litere .", "La revedere. "); }

FUNCŢII PENTRU OPERAŢII CU ŞIRURI DE CARACTERE Funcţiile pentru operaţii cu şiruri de caractere se găsesc în header-ul <string.h>. A. Functia strlen int strlen(nume_şir); – returnează lungimea efectivă a unui şir (fără a număra terminatorul de şir). Exemplu: char s[20]=”Buna ziua!”; strlen(s) = 10

112

B. Funcţia strcpy strcpy(şir_destinaţie, şir_sursă); – copiază şirul şir_ sursa în şir_destinaţie (se simulează atribuirea şir_destinaţie = şir_sursă). Exemplu: char x[20]=”Ion”, y[30]=”Vasile”; strcpy(x,y); x = ”Vasile”; y= ”Vasile”; C. Funcţia strcat strcat(dest,sursa); – adauga şirului dest şirul sursa. Sirul sursa rămâne nemodificat. Operatia se numeste concatenare şi NU este comutativă. Exemplu: char *x=”Buna ”,*y=”ziua!”; strcat(x,y); x = ”Buna ziua! D. Funcţia strncat strncat(dest,sursa,nr); – adaugă la dest primele nr caractere din şirul sursa. Şirul sursa ramane nemodificat. Exemplu: char *x=”Buna ”,*y=”ziua!?”; strncat(x,y,2); a = ”Buna zi”; E. Funcţia strchr strchr(sir,c); – are rolul de a căuta caracterul c in şirul sir. Căutarea se face de la stânga la dreapta, iar funcţia întoarce adresa subşirului care începe cu prima apariţie a caracterului c. Dacă nu este găsit caracterul, funcţia returnează 0. Diferenţa dintre adresa şirului iniţial şi cea a subşirului returnat reprezintă chiar poziţia caracterului căutat în şirul dat. Exemplu: char *a=”acesta este un sir”,b=’t’,c=’x’,d; cout<<strchr(a,b); se tipăreşte ”ta este un sir”; cout<<strchr(a,c); nu se tipăreşte nimic (sau se tipăreşte 0, dacă se face o conversie la int a lui strchr(a,c) ; d= strchr(a,b); cout<<”Caracterul apare prima data la pozitia ”<<d-a;

113

F. Funcţia strrchr strrchr(sir,c); – are acelaşi rol cu strchr, cu deosebirea că returneaza adresa ultimei aparitii a caracterului (căutarea se face de la dreapta spre stânga; r = right) G. Funcţia strcmp int strcmp(sir1,sir2); – are rolul de a compara două şiruri de caractere. Valoarea returnată este

<0 (daca sir1<sir2) =0 (daca sir1=sir2) >0 (daca sir1>sir2).

Funcţia strcmp face distincţie între literele mari şi cele mici ale alfabetului. Funcţia strcmp returnează diferenţa dintre codurile ASCII ale primelor caractere care nu coincid. H. Functia stricmp int stricmp(sir1,sir2); – are acelaşi rol cu strcmp, cu deosebirea că nu face distincţie între literele mari şi cele mici ale alfabetului (i = ignore). I. Funcţia strstr strstr(sir1,sir2); – are rolul de a identifica dacă şirul sir2 este subşir al sirului sir1. Dacă este, funcţia returnează adresa de început a subşirului sir2 în şirul sir1, altfel returnează adresa 0. În cazul în care sir2 apare de mai multe ori în sir1, se returnează adresa de început a primei apariţii. Căutarea se face de la stânga la dreapta J. Functia strtok strtok(sir1,sir2); – are rolul de a separa şirul sir1 în mai multe şiruri (cuvinte) separate între ele prin unul sau mai multe caractere cu rol de separator. Şirul sir2 este alcătuit din unul sau mai multe caractere cu rol de separator. Funcţia strtok acţionează în felul următor: - Primul apel trebuie să fie de forma strtok(sir1,sir2); Funcţia întoarce adresa primului caracter al primei entităţi. După prima entitate, separatorul este înlocuit automat prin caracterul nul. - Urmatoarele apeluri sunt de forma strtok(NULL,sir2); De fiecare dată, funcţia întoarce adresa de început a următoarei entităţi, adăugând automat după ea caracterul nul. - Când şirul nu mai conţine entităţi, funcţia returnează adresa nula.

114

K. Functia strspn int strspn(sir1,sir2); – are rolul de a returna numărul de caractere ale şirului sir1 (caractere consecutive care încep obligatoriu cu primul caracter) care se găsesc în şirul sir2. L. Funcţia strcspn int strspn(sir1,sir2); – are rolul de a returna numărul de caractere ale şirului sir1 (caractere consecutive care încep obligatoriu cu primul caracter) care NU se găsesc în şirul sir2. M. Funcţia strlwr strlwr(sir); – are rolul de a converti toate literele mari din şir în litere mici. Restul caracterelor rămân neschimbate. N. Funcţia strupr strupr(sir); – are rolul de a converti toate literele mici din şir în litere mari. Restul caracterelor raman neschimbate O. Funcţia strbrk strpbrk(sir1,sir2); – acţioneaza în felul următor: - Caută primul caracter al şirului sir1 în sir2. Dacă este găsit, returnează adresa sa din cadrul şirului sir1 şi execuţia se termină. Altfel, se trece la pasul următor. - Caută al doilea caracter al şirului sir1 în sir2. Dacă este găsit, returnează adresa sa din cadrul şirului sir1 şi execuţia se termină. Altfel, se trece la pasul următor. - … - Dacă nici un caracter al şirului sir1 nu aparţine şirului sir2, funcţia returnează adresa nulă. P. Funcţia atof double atof(sir); – converteşte un şir către tipul double. Dacă această conversie eşuează (se întâlneşte un caracter nenumeric), valoarea întoarsă este 0. Această funcţie (ca şi cele similare) necesită includerea bibliotecii stdlib.h. Q. Funcţia _atold long double _atold(sir); – converteşte un şir către tipul long double. Dacă această conversie eşuează, valoarea întoarsa este 0. P. Funcţia atoi

115

int atoi(sir); – converteşte un şir către tipul int. Dacă această conversie eşuează (se întâlneşte un caracter nenumeric), valoarea întoarsă este 0. R. Funcţia atoll long atol(sir); – converteşte un şir către tipul long. Dacă această conversie eşuează, valoarea întoarsa este 0. S. Functia itoa itoa(int valoare,sir,int baza); – converteşte o valoare de tip int în şir, care este memorat în variabila sir. Baza reţine baza de numeraţie către care să se facă conversia. În cazul bazei 10, şirul reţine şi eventualul semn -. T. Funcţia ltoa ltoa(long valoare,sir,int baza); – converteşte o valoare de tip long int în şir, care este memorat în variabila sir. U. Funcţia ultoa ultoa(unsigned long valoare,sir,int baza); – converteşte o valoare de tip unsigned long în şir, care este memorat în variabila sir.

EXEMPLE

A. Afişarea tuturor poziţiilor unui caracter într-un şir

#include <iostream.h> #include <string.h> void main( ){ char a[100],*p,c; cin.get(a,100); cin>>c; p=strchr(a,c); while (p){ cout<<"Pozitia "<<p-a<<endl; p++; p=strchr(p,c); }

116

}

B. Separarea cuvintelor dintr-un text

#include <iostream.h> #include <conio.h> #include <string.h> void main(){ char text[100],cuv[10][10],*p,*r,separator[]=",. !?";int i=0,nr=0; clrscr(); cout<<"Dati sirul:";cin.get(text,100); strcpy(p,text); p=strtok(p,separator); while (p) {strcpy(cuv[++nr],p); p=strtok(NULL,separator);} cout<<"Sunt "<<nr<<" cuvinte:"<<endl; for (i=1;i<=nr;i++) cout<<cuv[i]<<endl; getch(); } C. Sirul este alcatuit exclusiv din caractere numerice?

#include <iostream.h> #include <conio.h> #include <string.h> void main(){ char text[100],cifre[]="0123456789"; clrscr(); cout<<"Dati sirul:";cin.get(text,100); if (strcspn(cifre,text)==strlen(text)) cout<<"exclusiv numeric"; else cout<<”nenumeric”; getch();}

117

SUGESTII TEME DE LABORATOR 1. Să se transforme un şir din litere mici în litere mari. 2. Să se transforme un şir din litere mari în litere mici. 3. Se citeşte un text dintr-un fişier şi un caracter c. Să se determine de câte ori se găseşte

caracterul în text. 4. Să se sorteze alfabetic un şir de cuvinte 5. Se citesc n cuvinte. Să se afişeseze grupurile de cuvinte care au ultimele 2 caractere

identice 6. Să se despartă un text în cuvinte şi să se afişeze cuvintele separate. Să se afişeze

cuvântul de lungime maximă. 7. În directorul curent se află fişierul cuvinte.txt, care conţine mai multe linii de text

formate din cuvinte separate de câte un spaţiu. Să se afişeze cuvintele care au cel puţin 3 consoane sau 3 vocale consecutive.

. Se citeşte un şir de caractere. Să se afişeze şirul oglindit, din care lipsesc vocalele. 9. Se citeşte un text. Textul conţine cuvinte separate printr-un spaţiu. Să se determine

câte cuvinte conţine textul. 10. Dintr-un fişier se citeşte un text. Textul conţine cuvinte separate printr-un spaţiu sau

mai multe. Se va genera un nou fişier, care va conţine textul iniţial, având spaţiile de prisos eliminate (între cuvinte va rămâne numai câte un spaţiu).

11. Simulaţi comanda REPLACE, astfel încât într-un text veţi înlocui un caracter x, citit

de la tastatură, cu un alt caracter y, citit de la tastatură. 12. Se citeşte de la tastatură un cuvânt. Să se stabilească dacă el conţine două litere

alăturate identice, afişându-se un mesaj corespunzator. 13. Dintr-un fişier se citesc numele a n persoane. Să se modifice conţinutul fişierului

astfel încaât toate numele să fie scrise astfel: prima litera mare şi restul litere mici. 14. Într-un fişier sunt scrise cuvinte pe linii separate. Să se afişeze cuvintele care conţin

majuscule. 15. Să se afişeze vocalele unui cuvânt.

118

13. STRUCTURI

Structura este un grup de variabile de tipuri diferite reunite sub acelaşi nume, ce pune la dispoziţia utilizatorului un mod convenabil de pastrare a informaţiilor legate între ele.

Declararea unei structuri creează un nou tip de date, ce poate fi folosit pentru a crea variabile de acel tip, sau pentru a crea direct variabile de acel tip. Variabilele care fac parte din structură se numesc membri, elemente sau câmpuri ale structurii.

Între membrii structurii exista de obicei o legatură logică. Spre deosebire de tablouri, fiecare element al unei structuri poate avea propriul său tip, care poate diferi de tipul oricărui alt element. Forma generala a declararii unei structuri este: struct nume_generic { tip nume_membrul_l; tip nume_membrul_2; tip nume_membrul_n; } lista_variabile; unde: struct - este cuvânt rezervat, numele tipului de date; tip - este orice tip de dată admis de C; nu trebuie sa fie acelaşi

pentru toate câmpurile; nume_generic - numele dat noului tip de date ; opţional; lista_variabile - este o listă de variabile de tip nume_generic (dacă apare) sau

anonim (daca nu apare) ; este opţională; nume_membru_i - este numele câmpului (membrului) i al structurii. Nume_generic şi

lista_variabile sunt opţionale, dar cel puţin una trebuie să apară; dacă nume_generic apare, înseamnă că s-a creat un nou tip de date; dacă apare numai lista_variabile, înseamnă că s-au declarat variabile de tip structură, fără ca structura să aibă tip (tipul structurii create este anonim).

Pentru a accesa un câmp al unei structuri, trebuie specificate numele variabilelor de

tip structură şi numele câmpului, separate printr-un punct. Forma generală de acces la un membru:

nume_variabilă . nume_membru

unde nume_variabilă - numele variabilei de tip structură

119

nume membru - numele câmpului ce se doreşte a fi accesat.

Structurile pot fi aranjate în tablouri. Pentru a accesa un camp al unei anumite structuri din tablou, indexul trebuie

urmat de punct şi de numele câmpului ce trebuie accesat.

Un membru al unei structuri poate fi un tip simplu - unul din tipurile de bază, sau un tip compus, cum ar fi un tablou de caractere, sau tablourile uni şi multidimensionale.

EXEMPLE

A. Numere complexe #include<stdio.h> #include<math.h> typedef struct{ float a; //partea reala float b; //partea imaginara }complex; //numele structurii //citirea unui nr. Complex void citire(complex* z,char s[]) //s retine numele nr. complex { printf("Introducem nr. complex %s:\n",s); printf("\tpartea reala: "); scanf("%f",&(*z).a); printf("\tpartea imaginara: "); scanf("%f",&z->b); //alt mod de scriere } //afisarea unui nr. Complex void afisare(complex z,char s[]) { printf("Nr. complex %s: ",s); if(z.b>=0) printf("%.2f+%.2fi\n",z.a,z.b); else printf("%.2f%.2fi\n",z.a,z.b); }

120

//modulul unui nr. Complex float modul(complex z) { return sqrt(pow(z.a,2)+pow(z.b,2)); } //conjugatul unui numar complex complex conjugat(complex z) { complex t; t.a=z.a; t.b=-z.b; return t; } //suma a doua nr. complexe (varianta cu transfer prin tipul rezultat) complex suma1(complex x,complex y) { complex z; z.a=x.a+y.a; z.b=x.b+y.b; return z; } //suma a doua nr. complexe (varianta cu transfer prin linia de parametri) void suma2(complex x,complex y,complex* z) { z->a=x.a+y.a; //(*z).a=x.a+y.a; z->b=x.b+y.b; } //produsul a doua nr. Complexe complex produs(complex x,complex y) { complex z; z.a=x.a*y.a-x.b*y.b; z.b=x.a*y.b+x.b*y.a; return z; } //functia principala in rulare

121

void main() { complex z1,z2; //citirea celor doua nr. complexe citire(&z1,"z1"); citire(&z2,"z2"); printf("\n"); //afisarea celor doua nr. complexe afisare(z1,"z1"); afisare(z2,"z2"); printf("\n"); //modulele celor doua nr. complexe printf("Modulul lui z1: %.2f\n",modul(z1)); printf("Modulul lui z2: %.2f\n",modul(z2)); printf("\n"); //conjugatele celor doua numere complexe afisare(conjugat(z1),"conjugat z1"); afisare(conjugat(z2),"conjugat z2"); //suma a doua nr. complexe - varianta 1 complex s1; s1=suma1(z1,z2); afisare(s1,"z1+z2"); //suma a doua nr. complexe - varianta 2 complex s2; suma2(z1,z2,&s2); afisare(s2,"z1+z2"); //produsul a doua nr. complexe complex p; p=produs(z1,z2); afisare(p,"z1*z2"); getchar(); int k; scanf("%d", &k); }

122


A. Se reţine un număr complex z = a + bi ca structura

struct complex { float a; float b; };

Să se scrie funcţiile pentru adunarea, scăderea, înmulţirea şi împărţirea a două numere complexe.

B. Se reţine un număr raţional r = a/b ( 0,, ≠∈ bZba ) ca structura

struct rational { long int a; long int b; };

Să se scrie funcţiile pentru adunarea, scăderea, înmulţirea şi împărţirea a două numere raţionale.

C. Se reţine un punct din plan ca structura

struct punct { float a; float b; };

Să se scrie funcţiile pentru calculul distanţei dintre două puncte, calculul pantei şi

ordonatei pentru dreapta care trece prin două puncte, determinarea faptului dacă un punct se găseşte pe dreapta care uneşte două puncte, calculul ariei şi perimetrului unui triunghi determinat de trei puncte.

123

14. LISTE

Lista este o colectie de elemente (noduri, celule) înlănţuite, care formează o structură dinamică, situată in memoria dinamică, în care toate elementele sunt de acelaşi tip (oricât de complex).

Numărul de elemente este variabil, eventual chiar nul. O listă este deci o secvenţă de zero, una, sau mai multe elemente, numite noduri, toate

fiind de acelaşi tip. Spre deosebire de listă, tabloul este o structură statică, situata in memoria dinamică,

în care toate elementele sunt de acelaşi tip, numărul de elemente fiind constant. Un nod al unei liste liniare apare ca o structura recursivă, având o componentă de tip pointer la structură, care reprezintă legatura (înlănţuirea) spre nodul următor. Fiecare element (celulă/nod) din cadrul listei înlanţuite are o structură de tipul: → Informaţie utilă; → Informaţie de înlanţuire către elemental (nodul) următor; //pentru listele dublu înlănţuite → Informaţie de înlanţuire către elemental (nodul) anterior;

Dacă în cadrul elementului/celulei/nodului se face referire doar la elementul /celula/nodul următor, atunci avem liste simplu înlănţuite.

Dacă se face şi referire la nodul anterior, atunci avem liste dublu înlănţuite. Structura unui element / celule / nod:

Pentru lucrul cu liste simplu înlănţuite, este suficient să se cunoască adresa capului listei, iar pentru listele dublu înlantuite se poate ajunge la orice nod, dacă se cunoaşte adresa unui singur nod din listă, oricare ar fi el. Dacă ultimul nod din listă se pune în legătură cu primul nod, avem de-a face cu o listă circulară (simplu sau dublu înlănţuită, după cum lista originală era simplu sau dublu înlănţuită.

ADRESA NODULUI ANTERIOR

DATE NOD

ADRESA NODULUI URMĂTOR

CAP LISTĂ

124

EXEMPLE

A. Operaţii cu liste liniare dublu înlănţuite

#include <fstream.h> #include <conio.h> #include <stdlib.h> struct nod{ nod * ante; int val; nod * post; }; nod * curent, * prim, * ultim, * ajut; void creare(){ clrscr(); curent = new nod; prim=curent; ultim=curent; curent->ante=0; curent->post=0; cout<<"Introduceti valoarea:";cin>>curent->val; } void listarestdr(){ clrscr(); curent=prim; while(curent->post){ cout<<curent->val<<" "; curent=curent->post; } cout<<curent->val; getch(); } void listaredrst(){ clrscr(); curent=ultim; while(curent->ante){ cout<<curent->val<<" "; curent=curent->ante; } cout<<curent->val; getch(); }

125

void insmijloc(){ clrscr(); cout<<"In constructie. Voi insera un nod in interior"; getch(); } void insinaint(){ clrscr(); cout<<"In constructie. Voi insera un nod in prima pozitie"; getch(); } void inscoada(){ clrscr(); curent=new nod; cout<<"Introduceti valoarea:";cin>>curent->val; ultim->post=curent; curent->ante=ultim; curent->post=0; ultim=curent; } void stergint(){ clrscr(); cout<<"In constructie. Voi sterge un nod din interior"; getch(); } void stergprim(){ clrscr(); cout<<"In constructie. Voi sterge primul nod"; getch(); } void stergult(){ clrscr(); cout<<"In constructie. Voi sterge ultimul nod"; getch(); } void salvez(){ int i,n; clrscr(); cout<<"In constructie. Voi salva lista in fisier"; ofstream f("lista.dat"); curent=prim;n=1; while(curent->post){

126

curent=curent->post; n++; } cout<<"Lista are "<<n<<" noduri"<<endl; f<<n<<endl; curent=prim; for(i=1;i<=n;i++){ f<<curent->val<<endl; curent=curent->post; } getch(); } void meniu2(){ int rasp; clrscr(); cout<<"OPERATII CU LISTE :"<<endl<<endl; cout<<" 1: creare"<<endl<< " 2: listare de la stanga la dreapta"<<endl<< " 3: listare de la dreapta la stanga"<<endl<< " 4: inserare nod in interiorul listei"<<endl<< " 5: inserare nod pe prima pozitie"<<endl<< " 6: inserare nod pe ultima pozitie"<<endl<< " 7: stergerea unui nos din interiorul listei"<<endl<< " 8: stergerea primului nod"<<endl<< " 9: stergerea ultimului nod"<<endl<< "10: salvez lista"<<endl; cin>>rasp; switch (rasp){ case 1: creare();break; case 2: listarestdr();break; case 3: listaredrst();break; case 4: insmijloc();break; case 5: insinaint();break; case 6: inscoada();break; case 7: stergint();break; case 8: stergprim();break; case 9: stergult();break; case 10: salvez();break; default: exit(1); } meniu2(); } int citire(){ int i,n; clrscr();

127

cout<<"In constructie. Voi citi lista din fisier"; ifstream f("lista.dat"); f>>n; curent=new(nod); prim=curent; ultim=curent; f>>(curent->val); for(i=2;i<=n;i++){ curent=new(nod); f>>(curent->val); ultim->post=curent; curent->ante=ultim; curent->post=0; ultim=curent; } getch(); return 0; } void meniu1(){ int rasp; clrscr(); cout<<"EXPLOATAREA LISTELOR INLANTUITE"<<endl<<endl; cout<<"1 Citire lista din fisier"<<endl; cout<<"2 Lista noua"<<endl; cin>>rasp; switch (rasp){ case 1: citire();meniu2();break; case 2: meniu2();break; default: exit(1); } } void main(){ clrscr(); meniu1(); }

128


A. Rescrieţi funcţiile din programul de mai sus pentru cazul listelor liniare simplu înlănţuite

B. Rescrieţi funcţiile din programul de mai sus pentru cazul listelor circulare dublu

înlănţuite

129

15. RECURSIVITATE

Recursivitatea este un mecanism general de elaborare a algoritmilor. O funcţie se numeşte recursivă dacă ea se autoapelează, fie direct (în definiţia ei se face apel la ea însăşi), fie indirect (funcţia X apelează funcţia Y, care apelează funcţia X).

Recursivitatea a apărut din necesitati practice, date de transcrierea directă a formulelor matematice recursive. Apoi, acest mecanism a fost extins, fiind utilizat în elaborarea multor algoritmi. De exemplu, definiţia recursivă a lui n ! este :

>−

=altfel

ndacannn

10)!1(*

!

Functia recursivă se va scrie astfel:

long factorial(int n) {if(n==0) return 1; else return factorial(n-1)*n;} void main() {cout<<factorial(5) ;}

Se observă ca funcţia factorial se autoapelează. Autoapelul se realizează prin instrucţiunea return factorial(n-1)*n.

Recursivitatea utilizează segmentul de stivă pentru a memora datele programului apelant, câtă vreme calculatorul rulează programul apelat. De fiecare dată când o funcţie se autoapelează, se creează un nou nivel în segmentul de stivă.

Funcţionarea poate fi urmărită în figura de mai jos:

130

Fiecare apel de funcţie lucrează cu datele aflate pe nivelul corespunzator acelui apel.

La ieşirea din apelul unei funcţii, nivelul respectiv se eliberează şi datele aflate acolo se pierd. Există posibilitatea ca subprogramul să lucreze direct cu variabilele globale, dar în acest caz, subprogramul işi pierde independenţa.

Observaţii :

- în cazul unui număr mare de autoapelări, există posibilitatea ca segmentul de stivă sa se ocupe total, caz în care programul se va termina cu eroarea STACK OVERFLOW. Aceasta se întamplă mai ales atunci când condiţia de terminare este pusă greşit şi subprogramul se apelează la nesfârşit.

- pentru orice algoritm recursiv există unul iterativ, care rezolvă aceeaşi problemă. - mecanismul recursivităţii înlocuieste instrucţiunile repetitive. - datorită faptului că la fiecare autoapel se ocupă o zonă de memorie, recursivitatea

este eficientă numai dacă numărul de autoapelări nu este prea mare, pentru a nu se ajunge la umplerea zonei de memorie alocată.

- recursivitatea oferă avantajul unor soluţii mai clare pentru probleme şi a unei lungimi mai mici a programului. Ea prezintă însă dezavantajul unui timp mai mare de execuţie şi a unui spaţiu de memorie alocată mai mare. Este de preferat ca, atunci când programul recursiv poate fi transformat cu uşurinţă într-unul iterativ, să se facă apel la cel din urmă.

EXEMPLE

A. factorial recursiv

#include <conio.h> #include <iostream.h> unsigned long fact(int n){ if(n==1) return 1; else return n*fact(n-1);

131

} void main(){ int n; clrscr(); cout<<"n=";cin>>n; cout<<n<<"!="<<fact(n); getch(); }

B. Euclid recursiv

#include<iostream.h> #include<conio.h> int euclid(int a, int b){ if(b==0) return a; else euclid(b, a%b); } void main(){ clrscr(); int a, b, c; cout<<"a=";cin>>a; cout<<"b=";cin>>b; c=euclid(a,b); cout<<"cmmdc="<<c; getch(); }

C. Umplerea cu 1 a unei zone închise de valori de 0, delimitate de valori de 1

#include <conio.h> #include <stdlib.h> #include <iostream.h> int nl,nc,i,j,l,c,a[100][100]; char r; void umplu(int l,int c) { a[l][c]=1; if ((l>1)&&(a[l-1][c]==0)) umplu(l-1,c);

132

if ((c>1)&&(a[l][c-1]==0)) umplu(l,c-1); if ((c<nc)&&(a[l][c+1]==0)) umplu(l,c+1); if ((l<nl)&&(a[l+1][c]==0)) umplu(l+1,c); } void main(void){ r='d'; clrscr(); cout<<'\333'; cout<<"linii=";cin>>nl; cout<<"coloane=";cin>>nc; randomize(); for (i=1;i<=nl;i++) for (j=1;j<=nc;j++) a[i][j]=random(2); clrscr(); cout<<" "; for (j=1;j<=nc;j++) cout<<j%10;cout<<endl<<endl; for (i=1;i<=nl;i++) { cout<<i%10<<" "; for (j=1;j<=nc;j++) cout<<a[i][j]; cout<<endl; } cout<<endl; while (r=='d') { cout<<"linia=";cin>>l; cout<<"coloana=";cin>>c; umplu(l,c); clrscr(); cout<<" "; for (j=1;j<=nc;j++) cout<<j%10;cout<<endl<<endl; for (i=1;i<=nl;i++) { cout<<i%10<<" "; for (j=1;j<=nc;j++) cout<<a[i][j]; cout<<endl; } cout<<endl; cout<<"continuati?";r=getch(); cout<<endl; } }

133


A. Să se calculeze recursiv funcţia Ackerman, definită

−−=−=−

=altfelnmAmAnmAmn

nmA))1,(,1(

0)1,1(01

),(

B. Să se calculeze recursiv primele 44 de numere din şirul lui Fibonacci

C. Să se scrie o funcţie recursivă pentru calculul sumei unui număr natural

D. Să se genereze recursiv produsul cartezian a două mulţimi

E. Să se scrie o funcţie pentru generea recursivă a permutărilor unei mulţimi

F. Să se scrie o funcţie pentru generea recursivă a aranjamentelor de n elemente luate

câte k

G. Să se scrie o funcţie pentru generea recursivă a combinărilor de n elemente luate câte k

134

16. METODA DIVIDE ET IMPERA

Metoda Divide et Impera (Imparte şi Stăpâneste) este o metodă de programare care se aplică problemelor care pot fi descompuse în subprobleme independente, similare problemei iniţiale, de dimensiuni mai mici, şi care pot fi rezolvate foarte uşor. Procesul se reia până când (în urma descompunerilor repetate) se ajunge la probleme care admit rezolvare imediată.

Nu toate problemele pot fi rezolvate prin utilizarea acestei tehnici. Numărul celor rezolvabile prin "divide et impera" este relativ mic, tocmai datorită cerinței ca problema să admită o descompunere repetată.

Divide et impera este o tehnică ce admite o implementare recursivă. Principiul general prin care se elaborează algoritmi recursivi este: "ce se întâmplă la un nivel, se întâmplă la orice nivel" (având grijă să asigurăm condiţiile de terminare).

Un algoritm prin divide et impera se elaborează astfel: la un anumit nivel avem două posibilităţi:

1. s-a ajuns la o problemă care admite o rezolvare imediată (condiţia de terminare), caz în care se rezolvă şi se revine din apel;

2. nu s-a ajuns în situaţia de la punctul 1, caz în care problema curentă este descompusă în (două sau mai multe) subprobleme, pentru fiecare din ele urmând un apel recursiv al funcţiei, după care combinarea rezultatelor are loc fie pentru fiecare subproblemă, fie la final, înaintea revenirii din apel. Aceasta metodă (tehnică) se poate implementa atât iterativ cât şi recursiv. Dat fiind că

problemele se împart în subprobleme în mod recursiv, de obicei împărţirea se realizează până când şirul obţinut este de lungime 1, caz în care rezolvarea subproblemei este foarte uşoară.

De exemplu, fie un vector X=[x1, x2, x3, …xi … xp… xj, …xn] asupra căruia se aplică o prelucrare. Pentru orice secvenţă din vector delimitată de indecşii i si j, i<j există o valoare p, astfel încât prin prelucrarea secvenţelor : xi, xi+1, xi+2, xi+3, …xp si xp+1, xp+2, xp+3, …xj se obţin soluţiile corespunzatoare celor două subşiruri care, prin compunere, conduc la obţinerea soluţiei prelucrării secvenţei: xi, xi+1, xi+2, xi+3, …xj

Un exemplu îl constituie căutarea binară: Se consideră un vector ordonat crescator cu N elemente şi o valoare K. Se cere să se scrie o funcţie care returnează poziţia elementului K în vectorul dat. În cazul în care K nu există în vector, se returnează -1. O soluţie ar fi căutarea secvenţială: se parcurge vectorul în mod normal, şi se localizează elementul K. Această soluţie are complexitatea O(N). Metoda optimă de rezolvare este cautarea binară. Aceasta se foloseşte de metoda divide et impera. Se împarte vectorul în jumătate, după care se continuă căutarea, în mod similar, în acea parte a vectorului unde se afla elementul K. Condiţia ca vectorul să fie sortat este esenţială. Complexitatea acestui algoritm este O(logN).

#include<iostream.h> #include<conio.h>

135

http://ro.wikipedia.org/wiki/Recursivitate

int V[MAX_N], N, K; int binarySearch( int st, int dr) { if( dr > st ) return -1; int m = (st + dr) >> 1; if( V[m] == K ) return m; if( V[m] >= K ) return binarySearch(st, m-1); return binarySearch( dr, m+1); } int main() { // se citeste vectorul si valoarile N si K cout << binarySearch( 1, N ); }

EXEMPLE

A. Ghicirea unui număr

#include <fstream.h> #include <conio.h> void main(){ clrscr(); int x, y, z, rasp, gasit=0; char fis[20]; cout<<"numele fisierului de intrare : ";cin>>fis; ifstream f(fis); f>>x>>y; cout<<x<<" "<<y<<endl; while((!gasit)&&(x<=y)){ z=(x+y)/2; f>>rasp; if(rasp) gasit=1; else{ f>>rasp; if(rasp)y=z-1; else x=z+1; } } if(gasit)cout<<z; else cout<<"0"; getch();

136

f.close; }

B. Algoritmi de sortare-Merge sort

Dată fiind o listă neordonată, o împărţim în două liste, de dimensiuni egale sau foarte apropriate, ordonăm cele două liste (folosind acelaşi algoritm) şi apoi efectuăm operaţia "merge", adică vom combina cele două liste ordonate într-una singură, obţinând astfel lista originală ordonată. Operaţia principală care se efectuează este comparaţia dintre elementele listei.

#include<iostream.h> #include<conio.h> int a[1000],n; void interclas(int i,int m,int j) {int b[1000]; int x=i; int k=1; int y=m+1; while(x<=m && y<=j) if(a[x]<a[y]) b[k++]=a[x++]; else b[k++]=a[y++]; while(x<=m) b[k++]=a[x++]; while(y<=j) b[k++]=a[y++]; int t=i; for(k=1;k<=(j-i)+1;k++) a[t++]=b[k]; } int divimp(int i, int j) {if(i<j) {int m=(i+j)/2; divimp(i,m); divimp(m+1,j); interclas(i,m,j);} } void main() {clrscr(); cout<<”n= ”; cin>>n; for(int i=1;i<=n;i++) {cout<<”a[”<<i<<”]= ”; cin>>a[i]; } divimp(1,n); for(i=1;i<=n;i++) cout<<a[i]<<” ”; getch();

137

C. Turnurile din Hanoi

Se dau trei tije verticale A, B şi C. Pe tija A se găsesc un număr n de discuri de diametre diferite, perforate la mijloc, aranjate în ordine descrescătoare a diametrelor discurilor, de la bază spre vârf. Celelalte tije sunt goale. Se cere să se găsească o strategie de mutare a discurilor de pe tija A pe tija B, respectând următoarele reguli:

- La un moment dat se va muta un singur disc (cel care se aflădeasupra celorlalte discuri pe o tijă).

- Un disc oate fi aşezat doar peste un alt disc având diametru mai mare decât al său, sau pe o tijăgoală.

#include <stdio.h> #include <stdlib.h> #include <conio.h> #include <iostream.h> void hanoi(int n,int a, int b, int c){ if (n==1) {cout<<"se muta discul 1 de pe tija "<<a<<" pe tija "<<b<<endl; getch();return;} hanoi(n-1,a,c,b); cout<<"se muta discul "<<n<<" de pe tija "<<a<<" pe tija "<<b<<endl; getch(); hanoi(n-1,c,b,a); } void main(void){ int n; cout<<"n=";cin>>n; hanoi(n,1,2,3); }

138


A. Să se determine produsul a n numere întregi

B. Să se determine maximul (minimul) a n numere întregi

C. Să se determine cel mai mare divizor comun a n valori dintr-un vector

D. Să se caute o valoare într-un vector. Dacă se găseşte, se va afişa poziţia pe care s-a găsit, altfel se va afişa un mesaj.

E. Să se caute o valoare într-un vector ordonat crescator

F. Să se numere câte valori sunt egale cu x dintr-un şir de numere întregi citite

139

17. METODA BACKTRACKING Metoda Backtracking se aplică problemelor care îndeplinesc simultan două condiţii:

a. necesită o soluţie de tip vector, x, cu iAx∈ , unde iA sunt mulţimi finite şi ordonate b. nu dispunem de altă metodă mai rapidă.

Metoda selectează soluţia din produsul cartezian nAAA ××× 21 . Metoda foloseşte pentru generarea produsului cartezian o stivă, al cărui nivel îl notăm

cu st. În momentul în care dispunem de o soluţie parţială (din produsul nstundeAAA st <××× ,21 ), variabila st este incrementată, pentru a căuta o soluţie mai

complexă (eventual completă), din produsul cartezian 121 +××× stAAA . Dacă nici un element din stA nu mai poate constitui o soluţie, variabila st este

decrementată (momentul de “Backtracking”), pentru a încerca alegerea unui nou element din stA , care ar putea, eventual, contribui la construcţia unei soluţii parţiale.

Validitatea unei soluţii (parţiale sau totale) este determinată cu ajutorul unei funcţii-utilizator notată bun şi care primeşte ca parametru valoarea parametri vectorul soluţie x şi valoarea variabilei st.

Dacă x[st] îndeplineşte condiţiile problemei, funcţia bun întoarce valoarea 1, altfel întoarce valoarea 0. O posibilă implementare este următoarea:

#include <conio.h> #include <iostream.h>

int bun(int x[], int st){ return 1; } void main(){ clrscr(); int n, x[20], m[20], i, j, p, st; cout<<"dimensiunea problemei "; cin>>n; for(i=1; i<=n; i++){ cout<<"pana la cat merge x["<<i<<"] ? "; cin>>m[i]; } st=1;x[1]=0; while(st){ p=0; while((!p) && (x[st]<m[st])){

140

x[st]++; if(bun(x,st)) p=1; } if(!p) st--; else if(st<n) { st++; x[st]=0; } else { for(j=1; j<=n; j++) cout<<x[j]<<" "; cout<<endl; } } getch(); }

Faptul că funcţia bun întoarce totdeauna valoarea 1, face ca programul să genereze produsul cartezian nAAA ××× 21 . Orice problemă concretă se rezolvă, atunci, prin simpla modificare (de obicei uşoară şi intuitivă) a funcţiei bun, de aşa natură încât aceasta să întoarcă valoarea 0 pentru soluţiile inacceptabile pentru cazul concret, fără nici o modificare a programului principal.

EXEMPLE

A. Generarea produsului cartezian

Nici o modificare nu este necesară în funcţia bun; programul construieşte în mod nativ produsul cartezian.

B. Permutările unei mulţimi

Suntem în situaţia particulară m[1] = m[2] = … = m[n] = n; Funcţia bun se modifică după cum urmează:

int bun(int x[], int st){ int i; for(i=1; i<=st-1; i++) if(x[i]==x[st]) return 0; return 1; }

C. Aranjamente de n luate câte k

În problema noastră, n joacă rolul lui k, iar m[1] = m[2] = … = m[n] joacă rolul lui n

141

Funcţia bun este


D. Aranjamente de n luate câte k

În problema noastră, n joacă rolul lui k, iar m[1] = m[2] = … = m[n] joacă rolul lui n Funcţia bun este

int bun(int x[], int st){ int i; for(i=1; i<=st-1; i++) if(x[st]<=x[i]) return 0; return 1; }

E. Problema turnurilor de pe o tablă de şah

Se cere să se aşeze n turnuri pe o tablă de şah de dimensiune (n X n), fără ca acestea să se atace reciproc.

Suntem în situaţia particulară m[1] = m[2] = … = m[n] = n; Funcţia bun se modifică după cum urmează:


142


A. Problema reginelor de pe o tablă de şah

Se cere să se aşeze n regine pe o tablă de şah de dimensiune (n X n), fără ca acestea să se atace reciproc.

B. Problema colorării hărţilor

Pentru o hartă cu n ţări, se cer să se găsească toate posibilităţile de colorare a hărţii, utilizând maximum patru culori, astfel încât oricare două ţări care au o frontieră comună sa fie colorate diferit. Harta este prezentată sub forma unui tablou bidimensional care codifică dacă o ţară I se învecinează sau nu cu o ţară j prin valorile 1 sau 0:

=jtaracucomunafrontieraarenuitara

jtaracucomunafrontieraareitarajiA

01

]][[

C. Problema drapelelor

Având la dispoziţie c culori, să se determine toate drapelele tricolore care se pot realize, astfel încât să nu avem două culori successive identice

D. Descompunerea unui număr în sumă de numere prime

Fiind dat un număr natural n, să se scrie ca sumă de numere prime

143

18. GRAFURI ŞI ARBORI

Se numeşte graf orice mulţime finită V prevăzută cu o relaţie binară internă E. Notăm graful cu G = (V, E).

18.1 GRAFURI NEORIENTATE

Se numeşte graf neorientat un graf G = (V, E) în care relaţia binară este simetrică: (v,w)∈E atunci (w,v) ∈E.

DEFINIŢII

Se numeşte nod orice element al mulţimii V, unde G = (V, E) este un graf neorientat. Se numeşte muchie orice element al mulţimii E ce descrie o relaţie existentă între două vârfuri din V, unde G = (V, E) este un graf neorientat;

Adiacenţă: Într-un graf neorientat existenţa muchiei (v,w) presupune că w este adiacent cu v şi v adiacent cu w.

Incidenţă: o muchie este incidentă cu un nod dacă îl are pe acesta ca extremitate. Muchia (v,w) este incidentă în nodul v respectiv w. Grad: gradul unui nod v, dintr-un graf neorientat, este un număr natural ce reprezintă numărul de noduri adiacente cu acesta (sau numarul de muchii incidente cu nodul respectiv)

Nod izolat : un nod cu gradul 0. Nod terminal: un nod cu gradul 1

Lanţ: o secvenţă de noduri ale unui graf neorientat G=(V,E), cu proprietatea că oricare două noduri consecutive din lant sunt adiacente:

L = [w1, w2, w3,. . ,wn] cu proprietatea că (wi, wi+1) ∈ E pentru 1 ≤i <n. Lungimea unui lanţ: numărul de muchii din care este format.

Lanţ simplu: lanţul care conţine numai muchii distincte Lanţ compus: lanţul care nu este format numai din muchii distincte Lanţ elementar: lanţul care conţine numai noduri distincte Ciclu: un lanţ în care primul nod coincide cu ultimul. Ciclu elementar: ciclu format doar din noduri distincte, excepţie făcând primul şi ultimul. Lungimea unui ciclu nu poate fi = 2. Graf parţial : dacă dintr-un graf G = (V,E) se suprimă cel puţin o muchie, atunci noul graf G’ = (V,E’), E’⊂ E se numeşte graf parţial al lui G. Subgraf: dacă dintr-un graf G = (V,E) se suprimă cel puţin un nod, împreună cu muchiile incidente lui, atunci noul graf G’ = (V’,E’), E’⊂ E si V’⊂V se numeşte subgraf al grafului G.

Graf regulat : graf neorientat în care toate nodurile au acelaşi grad;

144

Graf complet: graf neorientat G = (V,E) în care există muchie între oricare două noduri. Numărul de muchii ale unui graf complet este: nr*(nr-1)/2, unde nr este numarul de noduri

Graf conex : graf neorientat G = (V,E) în care pentru orice pereche de noduri (v,w) există un lanţ care le uneşte.

Componentă conexă: subgraf al grafului de referinţă, maximal în raport cu proprietatea de conexitate (între oricare două vârfuri există lanţ); Lanţ hamiltonian: un lanţ elementar care conţine toate nodurile unui graf Ciclu hamiltonian: un ciclu elementar care conţine toate nodurile grafului

Graf Hamiltonian: un graf G care conţine un ciclu hamiltonian Lanţ eulerian: un lanţ simplu care conţine toate muchiile unui graf Ciclu eulerian: un ciclu simplu care conţine toate muchiile grafului Graf eulerian: un graf care conţine un ciclu eulerian. Condiţie necesară şi suficientă:

un graf este eulerian dacă şi numai dacă oricare vârf al său are gradul par. REPREZENTAREA GRAFURILOR NEORIENTATE Fie G = (V, E) un graf neorientat. Există mai multe modalităţi de reprezentare pentru un graf neorientat, folosind diverse tipuri de structuri de date. Reprezentările determină diverşii algoritmi şi programele care implementează pe calculator aceşti algoritmi. Matricea de adiacenţă

∈

=altfel

Ejidacajia

0],[1

],[

Observaţii: - Matricea de adiacenţă asociată unui graf neorientat este o matrice simetrică - Suma elementelor de pe linia k reprezintã gradul nodului k - Suma elementelor de pe coloana k reprezintã gradul nodului k Listele de adiacenţă a nodurilor

Reprezentarea în calculator a unui graf neorientat se poate face utilizând listele de adiacenta a varfurilor, adică pentru fiecare vârf se alcătuieşte lista vârfurilor adiacente cu el.

Ordinea nodurilor în cadrul unei liste nu este importantă. Pentru a genera o astfel de listă vom defini tipul nod :

struct nod {int nd; nod *next;};

Toate listele se vor memora utilizând un vector de liste.

145

Vectori de muchii

Fiecare arc al grafului poate fi privit ca o înregistrare cu două componente, în speţă cele două noduri care constituie extremităţile arcului:

- nod_in -> nodul din care iese arcul (“nodul de început” al arcului); - nod_sf -> nodul în care intră arcul (“nodul de sfârşit” al arcului);

Putem defini tipul de date ARC, astfel:

type ARC=record nod_in, nod_sf: integer; end;

Graful în ansamblul său, este o mulţime de arce, adică o mulţime de elemente de tipul

ARC. În consecinţă, definim graful ca un “vector de arce”, adică un vector de elemente de tipul ARC:

var v: array [1..25] of ARC;

Numărul real de elemente este numărul de arce m. Astfel, elementele efectiv folosite ale vectorului vor fi v[1], v[2],…, v[m]. Fiecare element {1, 2, …, m}) este de tipul ARC şi reprezintă unev[i] (cu i arc al grafului, având două componente: v[i].nod_in şi v[i].nod_sf -> nodurile extremităţi ale arcului.

Aceste moduri de reprezentare (prin matrice de adiacenţă, prin liste de vecini, sau prin

vectori de muchii) se folosesc după natura problemei. Dacă în problemă se doreşte un acces frecvent la muchii, atunci se va folosi matricea de adiacenţă, sau vectorul de muchii; dacă numarul de muchii care se reprezintă este mult mai mic dect n x n, este de preferat sa se folosescă listele de adiacenţă, pentru a se face economie de memorie.

EXEMPLE Exemplul 1. Să se verifice daca un graf neorientat este complet. #include<iostream.h> int n,i,j,m,a[10][10]; int main() {

cout<<"Dati nr. de vf. ";cin>>n; cout<<"Dati elementele matricei de adiacenta"<<endl; for(i=1;i<=n-1;i++)

for(j=i+1;j<=n;j++) {

146

cout<<"a["<<i<<"]["<<j<<"]="; cin>>a[i][j]; a[j][i]=a[i][j];

} // determinarea nr. de muchii m=0; for(i=1;i<=n;i++)

for(j=1;j<=n;j++) if(a[i][j]==1) m++;

m=m/2; if(m == n * (n-1)/2)

cout<<"Graf complet";

else cout<<"Graful nu este complet";

} Exemplul 2. Să se verifice dacă o succesiune de vârfuri date este ciclu pentru un graf. În caz afirmativ, să se stabilească dacă este sau nu ciclu elementar #include<iostream.h> int n,i,j,m,a[10][10],x[50]; int main() {

cout<<"Dati nr. de vf. ";cin>>n; cout<<"Dati elementele matricei de adiacenta"<<endl; for(i=1;i<=n-1;i++)

for(j=i+1;j<=n;j++){ cout<<"a["<<i<<"]["<<j<<"]="; cin>>a[i][j]; a[j][i]=a[i][j];

} // citirea succesiunii de vf. cout<<"Dati nr. de muchii ";cin>>m; for(i=1;i<=m;i++) {

cout<<"x["<<i<<"]="; cin>>x[i];

} // verificare daca este lant: vf. consecutive sa fie muchii in matrice int lant=1; for(i=1;i<=n-1;i++)

if(a[x[i]][x[i+1]]==0) lant=0;

147

// primul si ultimul vf. sunt egale int ok=1; if(lant==1)

if(x[1]!=x[m]) ok=0;

// muchii distincte int ciclu=1; if(ok==1)

for(i=1;i<=m-2;i++) for(j=i+1;j<=m;j++)

if(x[i]==x[j] && x[i+1]==x[j+1] || x[i]==x[j+1] && x[i+1]==x[j])

ciclu=0; // verificare daca este ciclu elementar: vf. sa fie distincte doua cate

doua, mai putin primul si ultimul if(ciclu==1 &&

x[1]==x[m]) cout<<"Ciclu elementar";

else cout<<"Ciclu neelementar";

} Exemplul 3. Se citesc 2 grafuri neorientate, unul cu n noduri şi m muchii, iar celalalt cu k varfuri si l muchii, ambele date prin vectorul muchiilor. Să se determine dacă al doilea graf este subgraf al primului. #include<fstream.h> fstream f("date.in",ios::in); fstream g("date2.in",ios::in); int a[100][100],b[100][100],n,m,k,l; int subgraf() {for(int i=1;i<=k;i++) for(int j=1;j<=k;j++) if(a[i][j]!=b[i][j]) return 0; return 1; }

148

int main(void) {

int x,y,i; f>>n>>m; for(i=1;i<=m;i++) {

f>>x>>y; a[x][y]=1; a[y][z]=1;

} g>>k>>l; for(i=1;i<=l;i++) {

g>>x>>y; b[x][y]=1; b[y][x]=1;

} } if(subgraf())

cout<<"da"; else cout<<"nu";

} Exemplul 4. Memorarea grafurilor neorientate folosind cele trei modalităţi de reprezentare:

a) Matrice de adiacenţă b) Vector de muchii c) Liste de vecini

#include <fstream.h> #include <vector.h> ifstream fin("date.in"); ofstream fout("date.out"); struct muchie {

int i,j; }; int A[50][50]; // matrice de adiacenta muchie M[1000]; // vector muchiilor

149

int V1[50], V2[50]; // liste de vecini

int n,m; //n – nr. de noduri, m – nr. de muchii

void citire() {

int x,y,i; fin>>n>>m; for(i=1;i<=m;i++) {

fin>>x>>y; M[i].i=x; M[i].j=y; A[x][y]=A[y][x]=1; V1[i]=x; V2[i]=y;

} } void afisare() {

int i,j; fout<<"matricea de adiacenta:\n"; for(i=1;i<=n;i++) {

for(j=1;j<=n;j++) fout<<A[i][j]<<" "; fout<<endl;

} fout<<"lista muchiilor:\n"; for(i=1;i<=m;i++) fout<<M[i].i<<" "<<M[i].j<<endl; fout<<"lista vecinilor:\n"; for(i=1;i<=n;i++) {

fout<<i<<": "; fout<<V1[i]<<","<<V2[i]<< " "; fout<<endl;

} fin.close(); fout.close();

150

} int main() {

citire(); afisare();

} Exemplul 5. Se citeşte de pe primul rând dintr-un fişier o valoare n, reprezentând numărul de noduri pentru un graf neorientat, iar de pe urmatoarele n linii şi coloane matricea de adiacenţa corespunzătoare grafului. a) Să se identifice mulţimea X b) Să se identifice mulţimea U c) Să se calculeze gradele nodurilor impare d) Să se verifice dacă graful are vârfuri izolate; dacă da, să se afişeze nodul, dacă nu, să se

afişeze un mesaj #include<iostream.h> #include<conio.h> #include<fstream.h> int a[20][20]; int main() {

ifstream f(“matricegraf.in”); int n,i,j,k; f>>n; //a) for(i=1;i<=n;i++) for(j=1;j<=n;j++) f>>a[i][j]; cout<<”X=”; for(i=1;i<=n;i++) cout<<i<<” “; cout<<endl; //b) cout<<”U=”; for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(a[i][j]==1&&i<j) cout<<”(“<<i<<”,”<<j<<”)”; //c)

151

for(i=1;i<=n;i++) {

k=0; for(j=1;j<=n;j++)

if(i%2==1&&a[i][j]==1) k++;

if(i%2==1) cout<<endl<<”gradul nodului “<<i<<” este “<<k<<endl;

} //d) for(i=1;i<=n;i++) {

r=0; for(j=1;j<=n;j++)

if(a[i][j]==1) return 0; } Exemplul 6. Se citeşte de pe prima linie din fişierul graf.in numărul de vârfuri şi numărul de muchii(n,m), iar de pe următoarele m rânduri, perechi de vârfuri reprezentând muchiile grafului. a) Să se construiască matricea de adiacenţă şi să se scrie în fişierul MAT.OUT b) Să se calculeze gradul fiecarui nod şi să se păstreze gradele într-un vector c) Să se verifice dacă graful are vârfuri izolate #include<iostream.h> #include<conio.h> #include<fstream.h> int a[20][20],v[40]; int main() {

ofstream g(“mat.out”); ifstream f(“graf.in”); int j,i,n,m,h,r=0,x,y,ok=0; f>>n; f>>m; // a) for(i=1;i<=m;i++) {

152

f>>x; f>>y; a[x][y]=a[y][x]=1;

} for(i=1;i<=n;i++) {

for(j=1;j<=n;j++) g<<a[i][j]<<” “; g<<endl;

} //b) for(i=1;i<=n;i++) { h=0; for(j=1;j<=n;

j++) if(a[i][j]==1) h++;

r++; v[r]=h;

} for(i=1;i<=n;i++) cout<<”nodul “<<i<<”are rangul “<<v[i]<<endl; // c) for(i=1;i<=n;i++)

if(v[i]==0) ok=0; else ok=1;

if(ok==0) cout<<”Graful are varfuri izolate”<<” “; else cout<<”Graful nu are varfuri izolate”<<” “;

} Exemplul 7. De pe primul rând din fişierul GRAF.TXT se citeşte numărul de noduri şi numărul de muchii, iar de pe următoarele m rânduri, perechile de noduri reprezentând muchiile. Să se formeze matricea de adiacenţă. Să se enumere nodurile terminale, nodurile intermediare #include<iostream.h> #include<conio.h> #include<fstream.h> int a[20][20]; int main() {

153

int i,j,n,m,x,y,k; ifstream f(“graf.txt”); f>>n; f>>m; for(i=1;i<=n;i++) for(j=1;j<=n;j++) {

f>>x; f>>y; a[x][y]=1; a[y][x]=1;} for(i=1;i<=n;i++)

{ for(j=1;j<=n;j+

+) cout<<a[i][j]<<” “;

cout<<endl; } for(i=1;i<=n;i++) {

k=0; for(j=1;j<=n;j

++) if(a[i][j]==1) k++;

if(k==1) cout<<”Nod terminal =”<<i<<endl; if(k>1) cout<<”Nod intermediar= “<<i<<endl;

} }

Operaţii pe grafuri neorientate Strbaterea în latime si in adancime a grafurilor neorientate

#include <fstream.h> #include <conio.h> #include <stdlib.h> struct nod{ int nr; nod * ante;

154

}; const float pinf= 1.e20; float minf=-1.e20; nod *p, *l[50]; int i,j,k,n,nrarc,m[50][50],c[50],v[50],ic,sc,mdr[5][50],por,sos; char numefis[20]; void bf(){ nod *q; while(ic<=sc){ q=l[c[ic]]; while(q){ if(!v[q->nr]){ sc++; c[sc]=q->nr; v[q->nr]=1; } q=q->ante; } ic++; bf(); } } void bfm(){ int q; while(ic<=sc){ for(q=k;q<=n;q++) if((!v[q])&&(m[c[ic]][q])){ sc++; c[sc]=q; v[q]=1; } ic++; bfm(); } } void df(int k){ nod *q;

155

cout<<k<<" "; q=l[k]; v[k]=1; while(q){ if(!v[q->nr])df(q->nr); q=q->ante; } } void dfm(int k){ int q; cout<<k<<" "; v[k]=1; for(q=k;q<=n;q++) if((!v[q])&&(m[k][q]))dfm(q); } void main(){ clrscr(); cout<<"numele fisierului de intrare ?"; cin>>numefis; ifstream f(numefis); f>>n;f>>nrarc; cout<<"sunt "<<n<<" noduri si "<<nrarc<<" arce"<<endl; for(i=1;i<=n;i++) for(j=1;j<=n;j++) m[i][j]=0; for(k=1;k<=nrarc;k++){ f>>i; f>>j; m[i][j]=1; } cout<<"matricea adiacentelor :"<<endl<<endl; for(i=1;i<=n;i++){ for(j=1;j<=n;j++)cout<<m[i][j]<<" "; cout<<endl; } f.close; ifstream g(numefis); g>>n;g>>nrarc; for(k=1;k<=nrarc;k++)l[k]=0;

156

for(k=1;k<=nrarc;k++){ g>>i; g>>j; cout<<k<<" : arc de la "<<i<<" la "<<j<<endl; p=new nod;p->nr=j;p->ante=l[i];l[i]=p; p=new nod;p->nr=i;p->ante=l[j];l[j]=p; } getch(); g.close(); cout<<endl<<"listele de adiacenta :"<<endl<<endl; for(i=1;i<=n;i++){ cout<<i<<" "; p=l[i]; while(p){ cout<<p->nr<<" "; p=p->ante; } cout<<endl; } cout<<endl<<"strabaterea in latime (cazul listelor de adiacenta) :"<<endl; cout<<"nodul de inceput : "; cin>>k; ic=1; sc=1; c[ic]=k; v[k]=1; bf(); cout<<endl; for(i=1;i<=sc;i++)cout<<c[i]<<" "; cout<<endl<<endl<<"strabaterea in latime (cazul matricei de adiacenta) :"<<endl; cout<<"nodul de inceput : "; cin>>k; bfm(); cout<<endl; for(i=1;i<=sc;i++)cout<<c[i]<<" "; cout<<endl<<endl<<"strabaterea in adancime (cazul listelor de adiacenta) :"<<endl; cout<<"nodul de inceput :"; cin>>k; cout<<endl; for(i=1;i<=n;i++)v[i]=0; df(k);

157

cout<<endl<<endl<<"strabaterea in adancime (cazul matricei de adiacenta) :"<<endl; cout<<"nodul de inceput :"; cin>>k; cout<<endl; for(i=1;i<=n;i++)v[i]=0; dfm(k); getch(); }

158

18.2 GRAFURI ORIENTATE

Un graf orientat reprezintă o pereche ordonată de mulţimi G=(X,U), unde X este o mulţime finită şi nevidă, numită mulţimea nodurilor, şi U este o mulţime formată din perechi ordonate de elemente ale lui X, numită mulţimea arcelor. Exemplu

In graful din figura1, mulţimea nodurilor este X={1, 2, 3, 4, 5, 6, 7} iar mulţimea arcelor este U={u1, u2, u3, u4, u5, u6, u7, u8, u9, u10}={(1,2), (2,3), (3,4), (4,1), (3,5), (5,3), (5,6), (6,7), (7,6), (7,5)}. Conexitate in grafuri orientate Un lanţ dintr-un graf orientat este un şir de arce {u1, u 2, u3 , …, un} cu proprietatea că oricare două arce consecutive au o extremitate comună. Altfel spus, un lanţ este un traseu care uneşte prin arce două noduri, numite extremităţile lanţului, fără a ţine cont de orientarea arcelor componente. Un graf G este conex, dacă oricare ar fi două vârfuri ale sale, există un lanţ care le leagă. Exemplu

Graful este conex pentru că, oricum am lua două noduri, putem ajunge de la unul la celălalt pe un traseu de tip lanţ. De exemplu, de la nodul 4 la nodul 2 putem ajunge pe traseul de

159

noduri (4,3,2), stabilind astfel lanţul {u5, u3}, dar şi pe traseul de noduri (4,1,2) stabilind lanţul {u6, u2}

Din figura 3 nu este conex. Luând submulţimea de noduri {1,2,3}, putem spune că între oricare două noduri din această submulţime există cel putin un lanţ, de exemplu lanţul {u1, u2} sau {u3, u1}. La fel stau lucrurile şi cu submulţimea de noduri {4,5,6}. Dar nu ptuem găsi un lanţ între un nod din prima submulţime şi un nod din a doua submulţime. Plecând dintr-un nod al primei submulţimi şi deplasându-ne pe arce, nu avem cum să trecem în a doua submulţime, pentru că nu există nici un arc direct care să lege cele două submulţimi. De exemplu, plecând din nodul 1, putem ajunge în nodul 2 pe traseul {u3, u2}, dar de aici nu putem ajunge mai departe în nodul 4, deci nu există lanţ de la 2 la 4. Componenta conexa Componenta conexă a unui graf G=(X, U) este un subgraf G1=(X1, U1) conex, a lui G, cu proprietatea că nu există nici un lanţ care să lege un nod din X 1 cu un nod din X-X 1 (pentru orice nod, nu există un lanţ între acel nod şi nodurile care nu fac parte din subgraf). De exemplu, graful din figura 3 nu este conex , însa în el distingem două componente conexe: G1 =(X1, U1), unde X1={1,2,3} şi U1={u1, u2, u3}; şi G2=(X2, U2), unde X2={4,5,6} şi U2={u4, u5}. Graf tare conex Graful tare conex este un graf orientat G=(X, U), dacă pentru oricare două noduri x şi y aparţin lui X, există un drum de la x la y, precum şi un drum de la y la x. Exemplu

5

160

Graful cu n=3 din figura 4 este tare conex. Pentru a demonstra acest lucru, formăm toate perechile posibile de noduri distincte (x, y), cu x, y aparţând mulţimii {1,2,3} şi, pentru fiecare astfel de pereche, căutam un drum de la x la y şi un drum de la y la x. x=1, y=2 De la 1 la 2 – drumul [1,3,2], pe arcele (1,3) si (3,2); De la 2 la 1 – drumul [2,3,1], pe arcele (2,3) si (3,1). x=1, y=3 De la 1 la 3 – drumul [1,2,3], pe arcele (1,2) si (2,3); De la 3 la 1 – drumul [3,2,1], pe arcele (3,2) si (2,1). x=2, y=3 De la 2 la 3 – drumul [2,1,3], pe arcele (2,1) si (1,3); De la 3 la 2 – drumul [3,1,2], pe arcele (3,1) si (1,2). Componentă tare conexă Un subgraf se obţine dintr-un graf G= (X, U) eliminând nişte vârfuri şi păstrând doar acele muchii care au ambele extremităţi în mulţimea vârfurilor rămase. Fie un subgraf tare conex G1=(X1, U1) al grafului G=(X, U). Adăugăm la subgraf un nod x, care nu face parte din mulţimea nodurilor sale (x apartine X-X1). Obţinem astfel mulţimea de vârfuri X1 reunit cu {x}. Subgraful indus pe mulţimea X1 reunit cu {x} se obţine luând şi arcele care trec prin nodul x. Dacă acest subgraf nu mai este tare conex, atunci el se numeşte componentă tare conexă. Exemplu

Acesta este graful G=(X,U) tare conex. Din el eliminăm nodul 4.

161

Am obţinut astfel subgraful tare conex G1=(X1, U1). Acestui graf îi adăugam un nod x care nu face parte din mulţimea nodurilor subgrafului G1.

Graful obţinut este o componentă tare conexă. Matricea costurilor Considerăm un graf orientat G=(X,U) cu n noduri, în care fiecărui arc îi este asociat un număr întreg numit cost. Semnificaţia acestui cost poate fi foarte variată, în funcţie de domeniul pe care îl descrie graful. De exemplu, dacă graful reprezintă harta unui oraş în care arcele sunt străzile iar nodurile sunt intersecţiile dintre stăyi, atunci putem vorbi despre costul deplasării unui automobil între două intersecţii, de-a lungul unei străzi. Acesta s-ar putea măsura în cantitatea de benzină consumată, calculată prin prisma lungimii străzii în m sau in km. Pentru evidenţierea costurilor tuturor arcelor unui graf cu n noduri se poate defini o matrice a, cu n linii *n coloane.există două forme ale acestei matrici: Forma a): Fiecare element a[i,j] poate fi: -c, dacă există un arc de cost c>0 între nodurile i şi j; -0, dacă i=j; -+∞, dacă nu există arc între nodurile i şi j. Forma b): Este absolut similară, cu singura deosebire că în loc de +∞ avem -∞. Forma a)se foloseşte pentru determinarea drumurilor de cost minim între două noduri, iar forma b) este utilizată în aflarea drumurilor de cost maxim. Dacă dorim să citim matricea costurilor, evident că nu putem introduce de la tastatură “+∞”! În loc de “+∞” vom da un num[r de la tastatură foarte mare.

162

Problema determinării drumului minim/ maxim între două noduri face obiectul algoritmului următor. Algoritmul Roy-Floyd Se consideră un graf orientat cu n noduri, pentru care se dă matricea costurilor în forma a). Se cere ca, pentru fiecare pereche de noduri (i, j), să se tipărească costu drumului minim de la i la j. Plecăm de la următoarea idee: dacă drumul minim între două noduri oarecare i şi j trece printr-un nod k, atunci drumurile de la i la k şi de la k la j sunt la rândul lor minime. Pentru fiecare pereche de noduri (i, j ), cu i, j ∈{1,2,…,n}, procedăm astfel: Dăm lui k pe rând valorile 1,2,…,n, pentru ca nodul k despre care vorbeam mai sus poate fi, cel puţin teoretic, orice nod al grafului. Pentru fiecare k: dacă suma dintre costul drumului de la i la j şi costul drumului de la k la j este mai mică decât costul drumului de la i la j {a[i, k]+a[k, j]<a[i, j]}, atunci drumul iniţial de la i la j este înlocuit cu drumul indirect i→k→j. această înlocuire fireşte că se va opera ca atare în matrocea costurilor: {a[i, j]:=a[i, k]+a[k, j]}. Observaţii Drumurile minime între toate nodurile se regăsesc la finele algoritmului tot în matricea costurilor, care a suferit n trasformări, pentru k=1,2,…,n. Unele elemente pot fi +∞, iar pentru simularea lui +∞ am spus că se introduce un număr întreg foarte mare. Prin adunări repetate a două numere întregi foarte mari putem ajunge la un rezultat care depăşeşte cea mai mare valoare posibilă de tipul integer. De aceea, recomandăm ca elementele matricei costurilor să fie de tipul longint. În cazul în care problema cerea pentru fiecare pereche de noduri (i, j) costul drumului maxim, modificările necesare ar fi minore : se foloseşte forma b) a matricei costurilor; condiţia testată în linia if devine “a[i, k]+a[k, j]<a[i, j]” #include <conio.h> #include <fstream.h> int n; float m[50][50]; void drum(int i, int j){ int k=1, gasit=0; while((k<=n) && !gasit){ if((i!=k) && (j!=k) && (m[i][j]==m[i][k]+m[k][j])){ drum(i,k);drum(k,j); gasit=1; } k++; } if (!gasit) cout<<j<<" ";

163

} void main(){ clrscr(); int i,j,k,ni,nf; char numefis[20]; cout<<"numele fisierului de intrare ? ";cin>>numefis; ifstream f(numefis); f>>n; for(i=1;i<=n;i++) for(j=1;j<=n;j++) f>>m[i][j]; for(i=1;i<=n;i++){ for(j=1;j<=n;j++) if(m[i][j]>1.e+19)cout<<"ì ";else cout<<m[i][j]<<" "; cout<<endl; } for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(m[i][j]>m[i][k]+m[k][j]) m[i][j]=m[i][k]+m[k][j]; cout<<endl<<endl; for(i=1;i<=n;i++){ for(j=1;j<=n;j++) if(m[i][j]>1.e+19)cout<<"ì ";else cout<<m[i][j]<<" "; cout<<endl; } cout<<endl<<endl; cout<<"nodul initial ";cin>>ni; cout<<"nodul final ";cin>>nf; if(m[ni][nf]<1.e20){ cout<<ni<<" "; drum(ni,nf);} else cout<<"nu exista drum de la "<<ni<<" la "<<nf; getch(); }

SUGESTII TEME DE LABORATOR Să se rescrie toate funcţiile din programul de mai sus pentru cazul grafurilor orientate

164

19. MINICULEGERE DE PROBLEME

LABORATOR IF – THEN - ELSE

1. Se citesc de la tastatură patru numere întregi a, b, c şi d, toate diferite. Să se afişeze cea mai mare valoare citită.

2. Se citesc de la tastatură patru numere întregi a, b, c şi d, toate diferite. Să se afişeze

cea mai mică valoare citită.

3. Se citesc de la tastatură trei numere întregi a, b şi c, nu neaparat diferite. Să se afişeze numele varibilei care are cea mai mare valoare. Daca mai multe variabie au această valoare, se vor tipări numele tuturor variabilelor care au această valoare, pe linii diferite ale monitorului.

4. Se citeşte de la tastatură un număr natural n. Să se afişeze mesajul “numărul este par”, sau mesajul “numărul este impar”, în funcţie de paritatea numărului n.

5. Se citesc de la tastatură două numere naturale n şi k. Să se afişeze mesajul “numărul n este divizibil la numărul k”, sau mesajul “numărul n NU este divizibil la numărul k”, în funcţie de valorile introduse.

6. Se citeşte de la tastatură un număr natural n, mai mare ca 100. Să se afişeze, în

ordine, pe aceeaşi linie, cifra sutelor, cifra zecilor şi cifra unităţilor numărului n,

separate de câte un spaţiu.

7. Să se rezolve ecuaţia de ordinul I ax+b=0, cu verificarea consistenţei valorilor

introduse de la tastatură pentru parametrii a şi b.

8. Să se rezolve ecuaţia de gradul al II-lea, luând în considerare toate posibilităţile pentru

valorile introduse de la tastatură pentru paramtrii a, b şi c.

BONUS

9. Se citeşte de la tastatură un număr natural n, mai mare decât 100 şi mai mic decât

65000. Să se elimine din număr cifra (cifrele) din mijloc şi să se afişeze numărul

obţinut. * * Dacă numărul n are un număr impar de cifre, se elimină o singură cifră, iar dacă numărul n

are un număr par de cifre, se elimină două cifre.

165

LABORATOR CICLUL FOR

1. Se introduce de la tastatură numărul natural n; se citesc apoi n numere întregi. Să se calculeze şi afişeze produsul numerelor citite cuprinse în intervalul [-5,5) , suma numerelor citite pare şi mai mari decât 20 şi numărul celor mai mici decât 100.

2. Aceeaşi problemă ca mai sus, dar în cazul în care numerele se citesc dintr-un fişier. 3. Aplicând în mod direct definiţia conform căreia “un număr natural este prim dacă nu

se împarte exact la nici un alt număr, în afară de 1 şi el însuşi”, să se stabilească dacă un număr n, introdus de la tastatură, este prim.

4. Să se afişeze pe monitor cifrele constituente ale unui număr natural n de exact 5 cifre,

introdus de la tastatură

5. Să se determine dacă un număr n de exact 4 cifre, introdus de la tastarură, este

palindrom (este acelaşi număr dacă este citit de la stânga la dreapta şi de la dreapta la

stânga).

6. Pentru un număr n, introdus de la tastarură, să se calculeze n! (factorialul)

7. Şirul lui Fibonacci este definit recursiv ca ai = ai-2 + ai-1, cu a0 = 0 şi a1 = 1; să se

afişeze primii 20 de termeni din şir.

8. Pentru un număr n, introdus de la tastarură, să se calculeze iterativ (fără aplicarea

formulelor de tip Gauss) sumele primelor n termeni din

166

LABORATOR WHILE ŞI DO WHILE

1. Se citesc de la tastatură numere întregi, până când se introduce numărul zero. Să se afişeze numărul de valori citite, media aritmetică a valorilor care nu sunt divizibile cu 3, valoarea minima citită şi al câtelea număr introdus are această valoare (dacă mai multe dintre numerele introduse aveau această valoare, se afişează numărul de ordine al primei apariţii)

2. Aplicând faptul că n%10 reprezintă ultima cifră a unui număr natural n, iar operaţia

n=n/10 realizează “scurtarea” cu o cifră a lui n, să se afişeze pe monitor cifrele constitutive ale unui număr natural n, introdus de la tastatură

3. Se citeşte de la tastatură un număr natural n. Să se afişeze suma cifrelor lui n care

sunt divizibile cu 3

4. De câte ori apare o cifră c în numărul n?

5. Să se determine dacă un număr n, introdus de la tastatură este palindrom (este acelaşi număr dacă este citit de la stânga la dreapta şi de la dreapta la stânga)

6. Utilizând algoritmul lui Euclid cu scăderi repetate, să se afişeze cmmdc (cel mai mare

divizor comun) pentru două numere naturale a şi b, introduse de la tastatură, precum şi numărul de paşi efectuaţi

7. Utilizând algoritmul lui Euclid cu împărţiri repetate, să se afişeze cmmdc (cel mai

mare divizor comun) pentru două numere naturale a şi b, introduse de la tastatură, precum şi numărul de paşi efectuaţi

8. Să se calculeze cmmmc (cel mai mic multiplu comun) pentru două numere naturale a

şi b, introduse de la tastatură

167

LABORATOR TABLOURI UNINIMENSIONALE

1. Se citeşte de la tastatură numărul n de componente, apoi elementele (numere naturale), ale vectorului unidimensional v. Să se afişeze maximul, minimul şi poziţiile pe care acestea le ocupă în vector (numărul n şi elementele v[i] vor fi definite unsigned long)

2. Pentru vectorul de la punctul 1, să se afişeze suma tuturor elemetelor pare de pe poziţii impare

3. Să se ordoneze crescător şi să se afişeze vectorul v de la punctul 1, utilizând metoda interschimbării

4. Să se ordoneze crescător şi să se afişeze vectorul v de la punctul 1, utilizând metoda bulelor

5. Utilizând vectorul v de la punctul 1, să se creeze vectorul w, care conţine toate elementele din v, iar între fiecare două elemente successive media aritmetică a acestor elemente

6. Utilizând vectorul v de la punctul 1, să se creeze vectorul w, care conţine numerele prime din v

7. Se citeşte de la tastatură un număr n (unsigned long); să se creeze şi afişeze vectorul w, care conţine cifrele numărului n

8. Se citeşte de la tastatură un număr n (unsigned long); să se afişeze cel mai mare număr natural care se poate obţine utilizând cifrele numărului n

BONUS:

9. Să se rotească circular spre stânga vectorul v de la punctual 1 cu exact k poziţii (k număr natural introdus de la tastatură)

10. Implementaţi o metodă eficientă pentru problema de la punctual 9, în cazul în care n şi k pot fi numere foarte mari

11. În vectorul v, de la punctul 1, să se intercaleze pe poziţia k valoarea m (k şi m citite de la tastatură)

12. Să se şteargă elementul de pe poziţia k din vectorul v (k citit de la tastatură) SUPERBONUS

13. Elementele vectorului v de la punctul 1 reprezintă elementele unei mulţimi A; să se construiasă vectorul w care conţine elementele celei mai largi (cu cel mai mare număr de elemnte posibil) submulţimi B, care satisfice condiţia că suma elementlor este divizibilă prin 3.

168

LABORATOR TABLOURI BIDIMENSIONALE

1. Să se creeeze în memorie şi să se afişeze pe monitor matricea 11 12 13 … 21 22 23 … 31 32 33 … …………...

având nl linii şi nc coloane (nl şi nc valori mai mici decât 10, citite de la tastatură)

2. Pentru matricea de la punctul 1, să se afişeze elementele de pe linia l, cele de pe coloana c, (l şi c citite de la tastatură), cele de pe diagonala principală, de pe diagonala secundară şi cele de pe conturul (chenarul) matricei.

3. Pentru matricea de la punctul 1, să se afişeze elementele “submatricei” cuprinse între

liniile l1 – l2 şi coloanele c1 – c2 (toate inclusiv - valorile l1, l2, c1, c2 se citesc de la

tastatură), apoi elementele aflate deasupra diagonalei principale şi cele de dedesubtul

diagonalei secundare

4. Să se afişeze vectorii definiţi de sumele, produsele, maximele şi minimele elementelor

de pe fiecare linie şi de pe fiecare coloană dintr-o matrice citită de la tastatură

5. În matricea de la punctul 1, să se permute intre ele liniile l1 şi l2, şi coloanele c1 şi c2

(valorile l1, l2, c1, c2 se citesc de la tastatură)

6. Să se scrie un program pentru înmulţirea a două matrice BONUS

7. Diagonalele unei matrice impart matricea în zonele numite intuitive N, E, S, V. Să se afişeze elementele acestor zone

8. Să se afişeze în spirală, în sensul acelor de ceasornic, toate elementele matricei de la punctul 1

9. Să se găsească (dacă există) “punctele şa” ale unei matrice citite de la tastatură (un element al unei matrice este punct şa dacă este simultan maximul de pe linia sa ŞI minimul de pe coloana sa, sau este simultan minimul de pe linia sa ŞI maximul de pe coloana sa)

169

LABORATOR ŞIRURI DE CARACTERE

1. Să se transforme un şir s de caractere (citit de la tastatură) din litere mici în litere

mari, utilizând funcţia corespunzătoare de transformare din string.h, apoi din litere mari în litere mici, tratând şirul ca vector (fără utilizarea funcţiei de transformare din string.h)

2. Se citeşte de la tastatură un şir de caractere s şi un caracter c. Să se determine de câte

ori se găseşte caracterul c în şirul s. 3. Se citeşte un text. Textul conţine cuvinte separate prin unul sau mai multe spaţii. Să se

determine câte cuvinte conţine textul. 4. Să se despartă un text în cuvinte şi să se afişeze cuvintele separate, cu ajutorul funcţiei

strtok 5. Se citeşte de la tastatură un cuvânt. Să se stabilească dacă el conţine două litere

alăturate identice, afişându-se un mesaj corespunzator. 6. Să se afişeze vocalele dintr-un text, în ordinea în care apar ele, apoi, pe rândul

următor, numărul de apariţii pentru fiecare din cele 5 vocale posibile, în ordinea lor alfabetică

7. Să se verifice dacă un text introdus de la tastatură este palindrom. 8. Pentru un text introdus de la tastatură, să se afişeze pe monitor textul în care toate

vocalele sunt dublate, iar literele mari sunt înlocuite prin caracterul “*” BONUS 9. Pentru un text introdus de la tastatură, să se afişeze pe monitor ultima consoană care

apare în text 10. Se citeşte un text. Textul conţine cuvinte separate prin unul sau mai multe spaţii. Să se

afişeze pe monitor textul în care cuvintele îşi păstrează poziţia iniţială, dar fiecare dintre ele este inversat

170

LABORATOR SUBPROGRAME (1)

1. Să se realizeze subprogramele prim şi invers, care primesc fiecare. prin intermediul parametrului n, valoarea unui număr natural lung. Subprogramul prim returnează valoarea 1, dacă numărul n este prim şi 0 în caz contrar; subprgramul invers returnează “oglinditul” numărului primit prin intermediul parametrului n. Programul principal citeste de la tastatură un număr n, care reprezintă numărul de elemente ale unui vector v, ale cărui elemente se vor citi de la tastatură. Cu ajutorul subprogramelor prim şi invers, elementele prime ale vectorului v se vor înlocui cu “oglinditele” lor, iar cele neprime se vor înlocui cu numerele formate prin eliminarea cifrelor pare; vectorul nou format se va tipări pe monitor.

2. Cu ajutorul subprogramelor prim şi invers de la punctul anterior, să se afişeze pe

monitor toate numerele prime de două cifre, care citite invers sunt tot prime.

3. Subprogramul aparcifra are doi parametri: numar – un număr natural lung şi cifra – un număr natural de o singură cifră. Programul returnează numărul de apariţii ale cifrei cifra în numărul numar. Programul principal citeşte de la tastatură un număr n, care reprezintă numărul de elemente ale unui vector v, ale cărui elemente se vor citi de la tastatură, şi o cifră – c. Cu ajutorul subprogramului aparcifra, elementele vectorului v se vor înlocui fiecare cu numărul de apariţii ale cifrei c în respectivul element; vectorul nou format se va tipări pe monitor.

4. Utilizând subprogramul aparcifra de la punctul anterior, să se calculeze câte cifre pare are un număr n, citit de la tastatură.

5. Utilizând subprogramul aparcifra de la punctul anterior, să se calculeze câte cifre distincte are un număr n, citit de la tastatură

6. Subprogramul divmic primeşte, prin intermediul parametrului n, un număr întreg lung şi returnează cel mai mic divisor prim al lui n. Programul principal citeste de la tastatură un număr n, care reprezintă numărul de elemente ale unui vector v, ale cărui elemente se vor citi de la tastatură. Cu ajutorul subprogramului divmic, să se determine care elemente din vectorul v sunt prime.

7. Subprogramul scurtez primeşte, prin intermediul parametului n, valoarea unui număr

natural lung şi returnează numărul primit, din care s-a “tăiat” ultima cifră. Subprogramul sumacifre primeşte, prin intermediul parametului n, valoarea unui număr natural lung şi returnează suma cifrelor numărului primit.

Programul principal citeste de la tastatură un număr n şi apoi, numai prin apeluri utile ale subprogramelor scurtez şi sumacifre (făra a accesa în mod direct cifrele numărului n) determină numărul de cifre ale numărului.

171

LABORATOR SUBPROGRAME (2)

8. Să se realizeze subprogramul prim, care primeşte ca parametru un număr natural n şi returnează cele mai apropiate numere prime a şi b, cu a<n<b

9. Să se realizeze subprogramul minmax, care primeşte ca parametri: - un vector v de numere întregi; - un număr natural n, reprezentând numărul de elemente ale vectorului v; Subprogramul returnează maximul elementelor din vectorul v, precum şi poziţia pe care acesta îl ocupă în vector, şi minimul elementelor din vectorul v, precum şi poziţia pe care acesta îl ocupă în vector

10. Să se realizeze subprogramul parim, care primeşte ca parametri: - un vector v de numere întregi; - un număr natural n, reprezentând numărul de elemente ale vectorului v; - două numere naturale p şi q (1≤p≤q≤n), reprezentând poziţii în vectorul v. Subprogramul returnează, prin intermediul parametrilor par şi impar, poziţiile dintre p şi q pe care se găsesc primul număr par, respectiv ultimul număr impar (p≤par≤≤q; (p≤impar≤q); dacă între p şi q nu se găseşte nici un număr par, parametrul par întoarce valoarea -1, iar dacă între p şi q nu se găseşte nici un număr impar, parametrul impar întoarce valoarea -1.

11. Să se realizeze subprogramul invers, care primeşte ca parametri: - un vector v de numere întregi; - un număr natural n, reprezentând numărul de elemente ale vectorului v; Subprogramul inversează ordinea elementelor din vectorul v; vectorul v NU este o variabilă globală

12. Să se realizeze subprogramul ordon, care primeşte ca parametri:

- un vector v de numere întregi; - un număr natural n, reprezentând numărul de elemente ale vectorului v; Subprogramul returnează doi vectori, a şi b, conţinând vectorul v ordonat crescător, respectiv descrescător; vectorii v NU sunt variabile globale

13. Să se realizeze subprogramul doivect, care primeşte ca parametri:

- un vector v de numere întregi; - un număr natural n, reprezentând numărul de elemente ale vectorului v; - un vector w de numere întregi; - un număr natural m, reprezentând numărul de elemente ale vectorului w. Subprogramul tipăreşte pe monitor elementele comune din vectorii v şi w

172

LABORATOR RECURSIVITATE ŞI DIVIDE ET IMPERA 1. Să se calculeze în mod recursiv n! 2. Să se calculeze în mod recursiv al n-lea termen din şirul lui Fibonacci 3. Să se calculeze în mod recursiv valoarea funcţiei Manna Pnueli

4. Să se calculeze în mod recursiv valoarea funcţiei Ackerman

5. Să se scrie un program recursiv care rezolvă problema turnurilor din Hanoi 6. Să se scrie un program recursiv care caută un număr k într-un şir ordonat, returnând

poziţia acestuia, în cazul în care numărul a fost găsit, şi -1, în cazul în care numărul nu a fost găsit

173

cuprins 1. baze Şi sisteme de...

Documents