cpp 1 intro - · PDF fileSiruri de caractere 44 8. Pointeri ... optice de caractere, ......

23
1 Programarea calculatoarelor

Transcript of cpp 1 intro - · PDF fileSiruri de caractere 44 8. Pointeri ... optice de caractere, ......

Page 1: cpp 1 intro - · PDF fileSiruri de caractere 44 8. Pointeri ... optice de caractere, ... -limbaje de timp real (pentru programarea unor evenimente in concordanta cu timpul real al

1

Programarea calculatoarelor

Page 2: cpp 1 intro - · PDF fileSiruri de caractere 44 8. Pointeri ... optice de caractere, ... -limbaje de timp real (pentru programarea unor evenimente in concordanta cu timpul real al

2

Cuprins

I. Introducere

1. Generalitati despre calculatoarele electronice 3

2. Sisteme de numeratie 10

3. Descrierea algoritmilor in pseudocod 15

II. Programarea in C++

4. Programul C++ 26

5. Instructiuni 33

6. Tablouri 41

7. Siruri de caractere 44

8. Pointeri 50

9. Variabile dinamice 47

10. Structuri 53

11. Uniuni 57

12. Enumerari 58

13. Functii 60

14. Afisarea pe ecran in modul text 66

15. Afisarea pe ecran in modul grafic 70

16. Functii recursive 75

17. Functii inline 75

18. Tratatrea exceptiilor 76

19. Parametrii functiei main 79

20. Pointeri de functii 81

III. Structuri de date

21. Liste 84

22. Cozi 90

23. Stive 94

24. Grafuri 97

25. Arbori 100

IV. Programarea orientată pe obiecte

26. Noţiuni introductive despre POO 104

27. Clase. Constructori şi destructori 104

28. Supradefinirea operatorilor 111

29. Funcţii şi clase prietene 117

30. Moştenire. Clase derivate 120

31. Moştenire multiplă 125

Bibliografie 128

Page 3: cpp 1 intro - · PDF fileSiruri de caractere 44 8. Pointeri ... optice de caractere, ... -limbaje de timp real (pentru programarea unor evenimente in concordanta cu timpul real al

3

I. INTRODUCERE

1. GENERALITATI DESPRE CALCULATOARELE ELECTRONICE

Structura si functionarea unui calculator electronic

Sistemul de calcul este un ansamblu de echipamente fizice care prelucreaza informatia

codificata conform unui program ce indica o succesiune determinata de operatii aritmetice si logice.

Calculatorul este alcatuit din doua subsisteme principale:

-subsistemul hardware;

-subsistemul software.

Subsistemul hardware.

Subsistemul hardware este reprezentat prin totalitatea echipamentelor si dispozitivelor fizice

din sistemul de calcul. Structura de baza a unui calculator secvential, cu program memorat, a fost

stabilita de catre celebrul informatician John von Neumann si a fost publicata in iunie 1945 in

lucrarea “Prima schita de raport asupra EDVAC”. Un astfel de calculator este compus din cinci

unitati functionale (fig.1.1.1).

Fig.1.1.1 Structura unui calculator secvemtial.

Unitatea de intrare (UI) permite introducerea informatiilor in calculator, realizand conversia

reprezentarii acesteia de la forma externa la un format intern binar. Evident ca reprezentarea interna

binara este o consecinta a faptului ca la constructia calculatoarelor electronice se utilizeaza circuite

cu doua niveluri stabile de tensiune la iesiri: un nivel ridicat, la care se asocieaza valoarea logica 1

si un nivel coborat, la care se asocieaza valoarea logica 0. Unitatea de intrare este reprezentata prin

echipamente periferice de intrare, cum sunt: tastatura, mouse, scanner, joy-stick, light-pen, cititoare

optice de caractere, cititoare de bare.

Memoria (unitatea de memorare, UM) este unitatea functionala a unui calculator in care se

stocheaza informatia (programe si date de prelucrat). Din unitatea de memorare informatia poate fi

citita, prelucrata, rememorata sau transferata in exterior. O caracteristica importanta a memoriei este

capacitatea acesteia, masurata prin numarul de biti de informatie pe care ii poate stoca. Ca unitate

de masura se utilizeaza octetul (sau „byte” in limba engleza), care este un ansamblu de 8 biti (in

realitate sunt cel putin 9 biti, caci se utilizeaza un bit de verificare a corectitudinii informatiei, bitul

de paritate, sau pot fi chiar si mai multi biti, in cazul utilizarii codurilor corectoare si detectoare de

erori). Se mai poate utiliza ca unitate de masura a capacitatii memoriei si in general a unei cantitati

UM

UI

UC

UAL UE

Page 4: cpp 1 intro - · PDF fileSiruri de caractere 44 8. Pointeri ... optice de caractere, ... -limbaje de timp real (pentru programarea unor evenimente in concordanta cu timpul real al

4

de informatie, cuvantul, precizand numarul de biti (de exemplu, 16 biti, 32 biti, 128 biti, etc.). Se

utilizeaza si multiplii ai octetului, avand urmatoarele relatii de transformare:

1 Koctet = 210

octeti

1 Moctet = 220

octeti

1 Goctet = 230

octeti

1 Toctet = 240

octeti

respectiv, multiplii ai cuvantului: Kcuvant, Mcuvant, Gcuvant si Tcuvant.

Memoria unui calculator nu este omogena, din considerente de perfomanta si cost (costul

unei memorii este cu atat mai mare cu cat si performantele acesteia sunt mai bune). Este necesar sa

se realizeze un compromis intre performantele memoriei unui calculator si costul acesteia. Din

aceasta cauza memoria este realizata ierarhic (fig.1.1.2) si se disting cel putin urmatoarele niveluri:

-memoria de registre (sau registrele procesorului) este foarte rapida, avand o viteza

comparabila cu viteza de operare a unitatii aritmetice-logice, dar evident si costul acesteia este

foarte mare. Aici se pastreaza in general operanzii care se prelucreaza la un moment dat.

Capacitatea acestui nivel este redusa, fiind de cateva zeci sau sute de octeti.

-memoria intermediara (sau memoria „cache”) este rapida, dar ceva mai lenta decat

memoria de registre si pastreaza fragmente de cod si date care sunt necesare sistemului de calcul la

momentul curent, fiind inlocuite cu noi fragmente pe masura ce executia programului avanseaza.

Capacitatea memoriei intermediare se situeaza aproximativ intre limitele 16 Kocteti si 1 Moctet.

-memoria principala (sau memoria operativa) este de asemenea rapida, dar mai lenta decat

memoria intermediara. Aici se pastreaza, in principiu, intregul program aflat in executie si datele

corespunzatoare. Capacitatea memorie principale pentru sistemele secventiale este aproximativ 16

Mocteti – 1 Goctet. Primele trei niveluri de memorie formeaza impreuna memoria interna a

sistemului de calcul.

-memoria secundara (sau memoria externa) este reprezentata prin echipamente periferice de

memorare, avand o capacitate nelimitata. Cele mai utilizate astfel de echipamente sunt diferitele

tipuri de unitati de disc (disc flexibil sau „floppy disk”, disc dur, sau „hard disk”), unitati de discuri

optice (CD-ROM, DVD), unitati de benzi magnetice si casete magnetice.

creste

capacitatea

creste

viteza

UAL

Fig.1.1.2 Organizarea ierarhica a memoriei.

Unitatea aritmetica-logica (UAL) efectueaza toate operatiile aritmetice si logice din

calculator. Astfel, aici se executa operatiile logice cum sunt operatiile NU, SAU, SI, SAU-

EXCLUSIV, etc. Tabelele de adevar pentru aceste operatii sunt prezentate in continuare:

Memoria secundara

Memoria principala

Memoria cache

Memoria de registre

Page 5: cpp 1 intro - · PDF fileSiruri de caractere 44 8. Pointeri ... optice de caractere, ... -limbaje de timp real (pentru programarea unor evenimente in concordanta cu timpul real al

5

x NU x X y x SAU y x y x SI y x y x SAU-EX y

0 1 0 0 0 0 0 0 0 0 0

1 0 0 1 1 0 1 0 0 1 1

1 0 1 1 0 0 1 0 1

1 1 1 1 1 1 1 1 0

Operatiile aritmetice cuprind evident operatiile aritmetice de baza (adunare, scadere, inmultire si

impartire) pentru numere cu diferite precizii de reprezentare.

Unitatea de iesire (UE) permite furnizarea in exterior a rezultatelor prelucrarilor, realizand

conversia din formatul intern binar intr-un format extern. Exista doua categorii de formate externe:

-prima categorie de formate se adreseaza direct utilizatorului uman si este reprezentata prin

numere, texte, grafice, imagini, sunete. In acest caz, unitatea de iesire este reprezentata prin

echipamente periferice de iesire si interfetele acestora.

-a doua categorie de formate este reprezentata de semnale electrice, destinate actionarii de

echipamente. In acest caz, unitatea de iesire este implementata prin module speciale, continand

circuite convertoare numeric-analogice (CNA), care convertesc rezultatele numerice in semnale

electrice (la calculatoarele de proces). Astfel, din procesul tehnologic se culeg informatii de interes

cu ajutorul unor traductoare care transforma marimile fizice cum sunt presiunea, temperatura, etc. in

semnale electrice, ce sunt apoi convertite in valori numerice binare prin intermediul unor module

continand convertoare analog-numerice (CAN), aflate in unitatea de intrare. Datele achizitionate

sunt prelucrate conform algoritmului implementat, iar rezultatele numerice sunt apoi transformate in

semnale electrice, care actionand o serie de echipamente regleaza procesul tehnologic controlat.

Unitatea de comanda (UC) controleaza functionarea celorlalte unitati ale sistemului de

calcul. Controlul se face conform cerintelor utilizatorului, specificate prin intermediul programului

memorat si aflat in curs de executie. Caracterul secvential al unui astfel de sistem de calcul rezulta

din modul de executie a unui program. Astfel, unitatea de comanda citeste din memorie

instructiunea curenta (faza de fetch), o decodifica (faza de decodificare), citeste operanzii daca

acestia sunt necesari (faza de citire operanzi), executa operatia ceruta de instructiune (faza de

executie), iar apoi trece la executia instructiunii urmatoare, parcurgandu-se aceleasi faze (de

remarcat cele patru faze necesare executiei unei instructiuni!). Astfel programul este executat

instructiune cu instructiune, deci intr-o maniere secventiala. Chiar daca la sistemele de calcul

uniprocesor actuale se realizeaza anumite suprapuneri intre fazele de executie a instructiunilor, in

primul rand suprapunerea fazei de executie a instructiunii curente cu faza de citire a instructiunii

urmatoare, se considera ca si aceste sisteme sunt de asemenea secventiale.

In constructia sistemelor de calcul actuale se utilizeaza microprocesoare. Un microprocesor

este un circuit integrat pe scara foarte larga (cu un numar foarte mare de componente elementare pe

pastila de siliciu) care implementeaza total sau partial functii ale unor unitati din calculator, in

primul rand functiile unitatii de comanda si ale unitatii aritmetice-logice . Deci microprocesorul este

in primul rand UC+UAL. Dar majoritatea microprocesoarelor integreaza si functii ale altor unitati

functionale, de exemplu, integreaza intotdeauna din cadrul UM nivelul memorie de registre, iar

uneori cel putin o parte a nivelului memoriei cache. Unele microprocesoare integreaza si functii ale

UI+UE avand capabilitati de comunicatie cu exteriorul (de exemplu interfata seriala).

Primul microprocesor comercial a fost realizat in anul 1971 de firma Intel (Intel 4004, pe 4

biti). Dezvoltarea microprocesoarelor a fost din ce in ce mai rapida, datorita concurentei puternice

de pe piata de componente. Cateva exemple mai semnificative de microprocesoare, grupate in

functie de lungimea cuvantului prelucrat:

Page 6: cpp 1 intro - · PDF fileSiruri de caractere 44 8. Pointeri ... optice de caractere, ... -limbaje de timp real (pentru programarea unor evenimente in concordanta cu timpul real al

6

-microprocesoare pe 8 biti: Intel 8080, Zilog Z80, Motorola 6800;

-microprocesoare pe 16 biti: Intel 8086, Zilog Z8000, Motorola 68000;

-microprocesoare pe 32 biti: Intel 80386 (primul microprocesor pe 32 biti), Motorola 68030,

Intel Pentium (intern pe 32 biti, magistrala externa de date pe 64 biti);

-microprocesoare pe 64 biti: Sun UltraSPARC, Intel Core 2 Extreme.

Subsistemul software

Subsistemul software este reprezentat prin totalitatea programelor si structurilor de date.

Primele calculatoare electronice au fost programate initial direct in cod masina (secvente de biti 0 si

1), ceea ce facea ca aceasta activitate sa fie deosebit de laborioasa. Apoi, anumite secvente de biti

care se repetau au fost reprezentate prin nume simbolice, care erau translatate automat in cod

masina, aparand astfel primele limbaje de programare. Limbajele de programare au evoluat

continuu, ajungandu-se la multitudinea de limbaje de astazi.

Se poate face o clasificare a limbajelor de programare. Exista doua mari categorii:

-limbaje de nivel coborat;

-limbaje de nivel inalt.

Limbajele de nivel coborat sunt specifice fiecarui tip de calculator. Un astfel de limbaj

desemneaza operatii elementare la nivelul cel mai de jos al masinii fizice, facand referiri directe la

locatii de memorie, registre ale procesorului, porturi de intrare/iesire. Programarea intr-un astfel de

limbaj presupune din partea programatorului o cunoastere buna a structurii sistemului de calcul.

Avantajul programelor scrise in aceste limbaje este viteza superioara de executie.

Limbajele de nivel inalt sunt universale. Programele scrise in aceste limbaje se pot executa

pe aproape orice tip de calculator. Un astfel de limbaj desemneaza operatii complexe asupra datelor,

facand abstractie de structura fizica a sistemului de calcul, ceea ce permite programatorului sa se

concentreze mai mult pe problema de rezolvat. Limbajele de nivel inalt se pot clasifica la randul lor

in cateva categorii, in functie de natura prelucrarilor:

-limbaje pentru calcule tehnico-stiintifice, avand un volum mare de calcule si un volum

relativ mic de date, cum sunt ALGOL, FORTRAN, BASIC, PASCAL, C;

-limbaje pentru calcule economice, cu un volum mic de calcule, dar un volum mare de date,

exemple: COBOL, DBASE, FOXPRO, SQL;

-limbaje de timp real (pentru programarea unor evenimente in concordanta cu timpul real al

utilizatorului), cum sunt RTL/2 si PASCAL Concurent;

-limbaje pentru calcule nenumerice, aici fiind incluse limbajele inteligentei artificiale, ca de

exemplu LISP si PROLOG.

Software-ul unui calculator poate fi clasificat in doua mari categorii:

-software de aplicatii;

-software de baza.

Software-ul de aplicatii este reprezentat prin programe de aplicatii care permit rezolvarea

unor probleme practice din diferite domenii de utilizare. Aceste programe sunt scrise in general de

catre utilizatorii sistemului de calcul, iar programele mai complexe de catre firme specializate de

software.

Software-ul de baza permite o utilizare eficienta si comoda a sistemului de calcul, fiind scris

in general de catre constructorii sistemului de calcul sau de firme specializate. Sistemul de operare

este un ansamblu de programe ce realizeaza gestiunea resurselor calculatorului. Principalele functii

ale sistemului de operare sunt:

-exploatarea eficienta a echipamentelor;

Page 7: cpp 1 intro - · PDF fileSiruri de caractere 44 8. Pointeri ... optice de caractere, ... -limbaje de timp real (pentru programarea unor evenimente in concordanta cu timpul real al

7

-rezolvarea conflictelor ce apar intre utilizatori sau task-uri (cereri simultane pentru aceleasi

resurse);

-gestiunea procesorului central (evidenta starii proceselor, sincronizarea proceselor, alocarea

procesorului);

-gestiunea echipamentelor periferice (urmarirea starii echipamentelor periferice, alocarea si

eliberarea acestora, initierea operatiilor de intrare / iesire);

-gestiunea memoriei interne (alocarea zonelor de memorie, securitatea acestora);

-comunicarea utilizatorului cu sistemul de calcul printr-un limbaj de comanda (comenzile

sistemului de operare, exemplu Unix) sau in mod grafic (exemplu Windows);

-contabilizarea automata a lucrarilor;

-intocmirea automata a unor statistici privind aparitia defectelor;

-lansarea in executie a unor programe de test la momente bine stabilite.

Istoric

Momente timpurii. In jurul anului 500 i.H. a fost construit in China antica abacul, un

dispozitiv rudimentar de calcul.

In evul mediu au fost realizate cateva calculatoare mecanice, dintre care s-au remarcat:

-in 1617 John Napier construieste un dispozitiv asemanator riglei de calcul;

-in 1642 fizicianul francez Blaise Pascal realizeaza o masina de adunat;

-in 1671 Gottfried Wilhelm von Leibniz pune la punct prima masina mecanica pentru

operatia de inmultire;

Mai aproape de zilele noastre profesorul de la Universitatea din Cambridge, Charles

Babbage, lucrand pentru perfectionarea tabelelor de logaritmi, a realizat in anul 1823 masina

diferentiala, care utiliza cartele perforate. In 1830 incepe lucrul la un alt echipament, masina

analitica, importanta acesteia constand in introducerea unor concepte noi, cum sunt: program,

subprogram, memorie, unitate aritmetica.

Calculatoare electronice. In anul 1943 guvernul britanic a finantat realizarea primului

calculator electronic Colossus, in mare secret, pentru decodificarea mesajelor germane in timpul

celui de-al doilea razboi mondial.

Pe data de 7 august 1944 Howard Aiken de la Universitatea Harvard, in colaborare cu IBM

(International Business Machines) si Bell Telephone lanseaza Mark I, un calculator electro-mecanic

utilizat pentru calculul traiectoriilor balistice.

O echipa condusa de Eckert si Mauchly de la Universitatea din Pensylvania, avand drept

consultant pe John von Neumann, realizeaza in anul 1946 calculatorul bazat pe aproximativ 30.000

tuburi electronice, ENIAC (Electronic Numerical Integrator and Computer). Sistemul dispunea de

mai multe elemente de calcul care lucrau in paralel si o singura unitate de comanda.

In iunie 1945 o echipa condusa de von Neumann finalizeaza sistemul EDVAC (Electronic

Discrete Variable Automatic Computer), care dispunea de o singura unitate de calcul, suficienta

datorita vitezei mari a componentelor electronice si pastra programele in memorie. Cu aceasta

ocazie von Neumann publica o lucrare intitulata „Prima schita de raport asupra EDVAC”, in care

sunt evidentiate unitatile functionale ale unui calculator secvential.

Ar trebui amintite aici inca doua realizari importante si anume, in anul 1951 UNIVAC I,

primul calculator comercial (firma infiintata de Eckert si Mauchly), iar in 1952 sistemul IAS

(Institute for Advanced Studies), realizat de von Neumann la Institutul Princeton.

Dezvoltarea tehnicii de calcul in Romania. Primul calculator electronic din Romania a fost

realizat in anul 1957 de un colectiv condus de dr.ing. Victor Toma si numit CIFA 1 (Calculator al

Institutului de Fizica Atomica), cu tuburi electronice. A urmat apoi CIFA 101.

Page 8: cpp 1 intro - · PDF fileSiruri de caractere 44 8. Pointeri ... optice de caractere, ... -limbaje de timp real (pentru programarea unor evenimente in concordanta cu timpul real al

8

La Timisoara in 1961 este realizat MECIPT 1 (Masina Electronica de Calcul Institutul

Politehnic Timisoara) cu tuburi electronice, iar ceva mai tarziu MECIPT 2 si 3, cu tranzistoare.

In anul 1966 la Cluj a fost construit DACICC 1.

Bazele industrie de calculatoare au fost puse in tara noastra in anul 1970 prin construirea

Fabricii de Calculatoare Bucuresti si intrarea in productie de serie a sistemului Felix C256, dupa o

licenta franceza. Dintre produsele de succes ale acestei intreprinderi ar trebui amintite urmatoarele:

-FELIX M18, M18B, M118, cu microprocesor Intel 8080 la 2 MHz, 64 Kocteti de memorie

interna, display grafic de 512x256 pixeli (numai la M118), unitati de disc flexibil de 8”, sistem de

operare CP/M si SFDX-18;

-CUB-Z, cu microprocesor Zilog Z80 la 2.5 MHz, 64 Kocteti de RAM, display grafic

512x256 pixeli, sistem de operare CP/M;

-FELIX M216, sistem biprocesor cu 8086 si 8080, memorie RAM de 128 Kocteti,

extensibila pana la 1 Moctet, display grafic color de 512x512 pixeli;

-FELIX PC, realizat cu microprocesor Intel 8086 (8088), coprocesor matematic 8087,

memorie RAM de 256 Kocteti, extensibila la 640 Kocteti pe placa de baza, unitati de disc flexibil

de 5¼”, sistem de operare MS-DOS;

-CORAL 4030, cu microprocesor bit-slice, structura microprogramata, memorie de 4

Mocteti, sistem de operare RSX-11;

-HC-85, destinat utilizarii acasa sau in scoli, cu microprocesor Zilog Z80, 64 Kocteti de

RAM, interfata cu unitate de caseta magnetica audio (casetofon audio), afisare pe televizor si

interpretor BASIC;

-FELIX 5000, calculator de capacitate medie pe 32 de biti, compatibil software cu sistemele

FELIX C256, C512, C1024, unitate centrala de prelucrare microprogramata, memorie RAM de 4

Mocteti, sistem de operare HELIOS si U (Unix).

Generatii de calculatoare

Sistemele de calcul construite incepand inca din anii ’40 si pana in zilele noastre se pot

grupa in functie de nivelul tehnologic in asa numitele generatii de calculatoare. Astfel se pot

delimita urmatoarele generatii:

Generatia I (1946-1952) utiliza tuburi electronice, avand o structura serie, cablaj prin fire,

cu 10-20 instructiuni simple. Raportul intre timpul pentru o operatie de inmultire si timpul pentru o

operatie de adunare t*/t+=20, iar t+≈1-5 ms. Calculatoarele dispuneau de putine echipamente

periferice de tipul cititor / perforator de banda de hartie. Memoria interna era realizata cu tambur

magnetic avand 1000-4000 de cuvinte. Programarea se facea direct in cod masina, iar viteza de

calcul era mica (sute-mii de operatii / secunda).

Generatia a II-a (1952-1963) se remarca prin inlocuirea tuburilor electronice cu tranzistoare

cu germaniu si siliciu, oferind astfel un gabarit redus, fiabilitate sporita, putere consumata mai

scazuta, siguranta in functionare si tensiuni de alimentare si comanda mai mici. Alte caracteristici:

memorie interna cu ferita, cablaj imprimat, tipizarea circuitelor logice (simplificand activitatea de

proiectare si depanare). Echipamentele periferice s-au diversificat: tambur magnetic, banda

magnetica cu densitate mica de inregistrare, dispozitiv de imprimare, trasator de curbe, dispozitiv de

afisare pe tub catodic. Raportul dintre timpul pentru o operatie de inmultire si timpul pentru o

operatie de adunare t*/t+=10, iar t+≈40-400 µs. Au aparut si primele limbaje de programare:

FORTRAN (FORmula TRANslation) in 1956, ALGOL (ALGOrithmical Language) in 1958 si

COBOL (Common Business Oriented Language) in 1959.

Generatia a III-a (1963-1974) se caracterizeaza prin utilizarea circuitelor integrate pe scara

simpla, cablaj multistrat, memorii externe de mare capacitate. Raportul intre timpul pentru o

operatie de inmultire si timpul pentru o operatie de adunare t*/t+=2.5, iar t+≈2-5 µs. Limbajele de

Page 9: cpp 1 intro - · PDF fileSiruri de caractere 44 8. Pointeri ... optice de caractere, ... -limbaje de timp real (pentru programarea unor evenimente in concordanta cu timpul real al

9

programare se perfectioneaza, aparand si limbaje noi: PL/1, ALGOL 60-68, FORTRAN IV,

COBOL, LISP. In dezvoltarea echipamentelor periferice se remarca pe de o parte imbunatatirea

celor existente, iar pe de alta parte construirea de echipamente noi, in special pentru preluarea

informatiilor din documentele primare. Apar concepte noi, cum sunt multiprelucrarea,

multiprogramarea, microprogramarea, programarea in timp real.

Generatia 3,5 (1974-1980) se remarca prin utilizarea circuitelor integrate pe scara larga, a

memoriilor cu circuite integrate, si a primelor microprocesoare pe 8 si 16 biti.

Generatia a IV-a (1980-astazi) utilizeaza in realizarea echipamentelor de calcul circuite

integrate pe scara foarte larga (VLSI), avand timpi de comutatie de 1-5 ns, memorii rapide cu timp

de acces sub 10 ns. Sunt realizate noi echipamente periferice performante. O alta caracteristica a

acestei generatii este interconectarea calculatoarelor in retele.

Se poate vorbi si de viitoarea generatie de calculatoare, generatia a V-a. Necesitatea acesteia

a aparut datorita performantelor relativ modeste ale sistemelor actuale in aplicatii complexe, care

includ prelucrari de imagini, recunoasterea vorbirii, simulare etc. De asemenea, componentele

electronice au ajuns aproape de viteza limita de functionare. Tehnologia viitoare pentru

implementarea acestei noi generatii se va baza pe circuite integrate pe scara ultra larga (ULSI) si

3D. Arhitectura unui astfel de calculator va cuprinde trei componente de baza: 1) interfata

inteligenta cu utilizatorul uman, comunicatia realizandu-se prin limbaj natural, voce, imagini; 2)

masina pentru rezolvarea de probleme care sa realizeze singura rationamente logice care sa conduca

la solutia problemei; 3) baza de cunostinte cu volum imens si in care cautarea sa se faca rapid, prin

hardware.

2. SISTEME DE NUMERATIE

Sistem de numeratie este totalitatea regulilor de reprezentare a numerelor cu ajutorul unor

simboluri numite cifre. Cifra este un simbol care reprezinta o cantitate intreaga. Baza (radacina)

sistemului de numeratie este numarul de simboluri permise pentru reprezentarea cifrei.

In activitatea de programare se utilizeaza cel mai mult sistemele de numeratie cu bazele 2, 8,

10 si 16. In continuare este prezentat un tabel cu reprezentarile unor numere naturale in cele patru

baze:

b=10 b=2 b=8 b=16

0 0 0 0

1 1 1 1

2 10 2 2

3 11 3 3

4 100 4 4

5 101 5 5

6 110 6 6

7 111 7 7

8 1000 10 8

9 1001 11 9

10 1010 12 A

11 1011 13 B

12 1100 14 C

13 1101 15 D

14 1110 16 E

15 1111 17 F

Page 10: cpp 1 intro - · PDF fileSiruri de caractere 44 8. Pointeri ... optice de caractere, ... -limbaje de timp real (pentru programarea unor evenimente in concordanta cu timpul real al

10

16 10000 20 10

17 10001 21 11

18 10010 22 12

19 10011 23 13

20 10100 24 14

21 10101 25 15

... ... ... ...

Se observa ca pentru fiecare sistem de numeratie numarul de cifre diferite utilizate este egal cu

baza. In baza 16 pe langa cele 10 cifre zecimale se utilizeaza primele sase litere ale alfabetului

pentru reprezentarea cifrelor cu valorile 10(10)-15(10).

Schimbarea bazei de numeratie

O problema importanta care se pune in legatura cu sistemele de numeratie este schimbarea

bazei de numeratie pentru reprezentarea numerelor. Considerand un numar real fara semn (sau

pozitiv), schimbarea bazei se face separat pentru partea intreaga si separat pentru partea subunitara.

Se considera un numar intreg fara semn N reprezentat in baza x si se doreste reprezentarea

acestuia intr-o noua baza y. Operatia de conversie este echivalenta cu aflarea coeficientilor

polinomului in puteri pozitive ale noii baze y, prin care se poate reprezenta numarul:

N = anyn + an-1y

n-1 + ... + a1y + a0

Se efectueaza impartiri succesive la noua baza y, retinand la fiecare operatie restul. Se face o prima

operatie de impartire la noua baza, obtinandu-se:

N / y = anyn-1

+ an-1yn-2

+ ... + a1 + a0/y

Restul impartirii a0 este prima cifra, cea mai putin semnificativa a rezultatului, iar catul (numar

intreg) se noteaza cu N1 si se face o noua impartire:

N1 / y = anyn-2

+ an-1yn-3

+ ... + a2y + a1/y

Din nou, restul impartirii a1 este cifra urmatoare a rezultatului, iar catul se noteaza cu N2 si se face o

noua impartire la y,..., astfel incat la un pas oarecare se obtine:

Nk / y = anyn-k-1

+ an-1yn-k-2

+ ... + ak+1y + ak/y

Rezulta cifra curenta a rezultatului conversiei ak, ca fiind restul impartirii, iar catul se noteaza cu

Nk+1 si se continua. Conversia se incheie atunci cand dupa o operatie de impartire se obtine catul

zero (chiar daca dupa acest moment se continua algoritmul se vor obtine numai cifre 0 la rest, ceea

ce inseamna zerouri nesemnificative in stanga unui numar intreg).

Exemplu. Sa se realizeze conversia numarului N = 41(10) din baza 10 in noua baza 2.

41 : 2 => cat =20 si rest = 1 => a0 = 1

20 : 2 => cat =10 si rest = 0 => a1 = 0

10 : 2 => cat = 5 si rest = 0 => a2 = 0

5 : 2 => cat = 2 si rest = 1 => a3 = 1

2 : 2 => cat = 1 si rest = 0 => a4 = 0

1 : 2 => cat = 0 si rest = 1 => a5 = 1

Page 11: cpp 1 intro - · PDF fileSiruri de caractere 44 8. Pointeri ... optice de caractere, ... -limbaje de timp real (pentru programarea unor evenimente in concordanta cu timpul real al

11

S-a obtinut astfel ca N = 101001(2). Se poate face si o verificare a rezultatului obtinut facand

conversia inversa din baza 2 in baza 10, prin adunarea tuturor produselor intre fiecare cifra a

reprezentarii in baza 2 si ponderea sa:

N = 1·25 + 0·24 + 1·23 + 0·22 + 0·21 + 1·20 = 41

deci, conversia s-a facut corect.

Aplicatie. Sa se scrie un algoritm in pseudocod pentru conversia unui numar intreg din

zecimal in binar.

citeste nr

i = 0

cat timp nr ≥ 2i executa │ a[i] = 0

└ i = i + 1

i = i - 1; n = i; a[n] = 1; nr = nr – 2i

cat timp nr ≠ 0 executa │ i = i – 1

│ daca nr ≥ 2i atunci │ │ a[i] = 1

└ └ nr = nr – 2i

scrie (a[i], i = 0,n)

Se considera un numar N subunitar, fara semn, scris in baza x si se doreste realizarea

conversiei intr-o noua baza y. Operatia de conversie este echivalenta cu aflarea coeficientilor

polinomului in puteri negative ale noii baze y, prin care se poate reprezenta numarul:

N = a-1y-1

+ a-2y-2

+ ... + a-my-m

Indicii negativi ai coeficientilor polinomului nu au nici o semnificatie speciala, s-a incercat numai

punerea in corespondenta a acestora cu puterile corespunzatoare ale bazei y. Pentru aflarea

coeficientilor este necesar sa se efectueze inmultiri succesive cu noua baza y, retinand de fiecare

data partea intreaga a rezultatului. Astfel, la prima inmultire se obtine:

N·y = a-1 + a-2y-1

+ a-3y-2

+ ... + a-my-m+1

Partea intreaga a rezultatului a-1 este prima cifra, cea mai semnificativa, a rezultatului conversiei.

Partea subunitara se noteaza cu N1 si se face o noua inmultire:

N1·y = a-2 + a-3y-1

+ a-4y-2

+ ... + a-my-m+2

Rezulta a-2 cifra urmatoare a rezultatului, iar partea subunitara se noteaza cu N2 executand o noua

inmultire, etc., astfel incat la un pas oarecare se obtine:

Nk·y = a-k-1 + a-k-2y-1

+ a-k-3y-2

+ ... + a-my-m+k+1

Se obtine partea intreaga a-k-1, iar partea subunitara se noteaza Nk+1 si se continua. Conversia se

incheie fie in momentul in care se obtine partea subunitara a rezultatului inmultirii egala cu zero

(daca in acest moment s-ar continua algoritmul, atunci s-ar obtine numai cifre 0 nesemnificative in

dreapta unui numar subunitar), fie cand s-a calculat numarul propus de cifre (s-a atins precizia

dorita). Spre deosebire de conversia numerelor intregi, care se realizeaza intotdeauna exact,

conversia numerelor subunitare se face de cele mai multe ori aproximativ (in functie de cele doua

Page 12: cpp 1 intro - · PDF fileSiruri de caractere 44 8. Pointeri ... optice de caractere, ... -limbaje de timp real (pentru programarea unor evenimente in concordanta cu timpul real al

12

baze sau de numerele care se convertesc). De aceea, pentru numerele subunitare se propune de la

inceput numarul de cifre pe care sa se reprezinte rezultatul, iar in momentul in care s-au calculat

toate cifrele conversia se incheie.

Exemplu. Sa se converteasca numarul N = 0.37(10) din baza 10 in baza 2. Ne propunem ca

rezultatul sa fie obtinut pe 7 biti (este precizia rezultatului).

0.37 x 2 = 0.74 => a-1 = 0

0.74 x 2 = 1.48 => a-2 = 1

0.48 x 2 = 0.96 => a-3 = 0

0.96 x 2 = 1.92 => a-4 = 1

0.92 x 2 = 1.84 => a-5 = 1

0.84 x 2 = 1.68 => a-6 = 1

0.68 x 2 = 1.36 => a-7 = 1

S-a obtinut N ≈ .0101111(2) . Se poate face o verificare asupra preciziei rezultatului, efectuand

conversia din baza 2 in baza 10, cum s-a facut si pentru numerele intregi, prin adunarea produselor

intre cifre si ponderile acestora.

N ≈ 0·2-1+1·2-2+0·2-3+1·2-4+1·2-5+1·2-6+1·2-7 =

= (0·26+1·25+0·24+1·23+1·22+1·21+1·20)/27 =

= 47 / 128 = 0.367

Rezultatul este destul de aproape de valoarea initiala, tinand cont de numarul mic de biti care s-au

utilizat pentru reprezentarea rezultatului. Evident, marind numarul de biti se poate obtine o precizie

mai buna.

Aplicatie. Sa se scrie un algoritm in pseudocod pentru conversia unui numar subunitar din

zecimal in binar, cu precizia pe m biti.

citeste nr, m

pentru i=1,m executa

└ a[i] = 0

i = 0

cat timp (nr ≠ 0)si(i < m) executa │ i = i + 1

│ daca nr ≥ 2-i atunci │ │ a[i] = 1

└ └ nr = nr – 2-i

scrie (a[i], i = 1,m)

Exemplu. Sa se converteasca numarul N = 41.37(10) din baza 10 in baza 2. Ne propunem ca

partea subunitara sa fie obtinuta pe 7.

Se realizeaza conversia separat pentru numarul intreg 41 si separat pentru numarul subunitar

0.37 (ca in exemplele precedente), iar apoi se concateneaza cele doua rezultate, obtinand in final N

≈ 101001.0101111(2).

Cazuri particulare

Exista doua cazuri particulare la schimbarea bazei de numeratie, cand conversia se face in

mod direct, fara operatii de impartire si inmultire, iar rezultatul este exact si pentru partea

subunitara.

Page 13: cpp 1 intro - · PDF fileSiruri de caractere 44 8. Pointeri ... optice de caractere, ... -limbaje de timp real (pentru programarea unor evenimente in concordanta cu timpul real al

13

1) x = yn . In acest caz se inlocuieste fiecare cifra a reprezentarii in baza x printr-un grup de

n cifre corespunzatoare in baza y.

Exemplu. Sa se converteasca numarul N = 3CF.4AE(16) din baza 16 in baza 2.

Intre cele doua baze exista relatia 16 = 24, deci n = 4. Pentru conversie se va inlocui fiecare

cifra a reprezentarii in baza 16 printr-un grup de patru cifre in baza 2. Astfel:

3 C F . 4 A E

↓ ↓ ↓ ↓ ↓ ↓ 0011 1100 1111 . 0100 1010 1110

Se poate renunta la scrierea zerourilor de la inceput si sfarsit, asa ca rezultatul final obtinut

este N = 1111001111.01001010111(2). Foarte important, conversia s-a facut exact.

2) xn = y. In acest caz se formeaza in cadrul reprezentarii in vechea baza x, grupuri de cate n

cifre de la punctul zecimal spre stanga pentru partea intreaga si de la punctul zecimal spre dreapta

pentru partea subunitara (daca este necesar se vor completa grupurile extreme cu zerouri), iar apoi

se inlocuieste fiecare grup printr-o cifra corespunzatoare in noua baza y. De asemenea, rezultatul

este exact.

Exemplu. Sa se converteasca numarul N = 11001111.1101011(2) din baza 2 in baza 8.

Avem relatia 23 = 8 intre cele doua baze, deci n = 3. Se formeaza grupuri de cate trei cifre in

cadrul reprezentarii in baza 2, se completeaza cu zerouri grupurile extreme si se inlocuiesc apoi

grupurile cu cifrele corespunzatoare in baza 8.

011 001 111 . 110 101 100

↓ ↓ ↓ ↓ ↓ ↓ 3 1 7 . 6 5 4

S-a obtinut astfel rezultatul (exact !) N = 317.654(8), fara sa se utilizeze operatii de impartire si

inmultire.

3. DESCRIEREA ALGORITMILOR IN PSEUDOCOD

Pentru reprezentarea algoritmilor se utilizeaza in principal doua instrumente de descriere:

-schemele logice (organigramele);

-limbajul pseudocod.

Schemele logice sunt constituite dintr-un set de figuri geometrice cu semnificatii

prestabilite, desemnand diferite operatii de baza: atribuirea, decizia, citirea, scrierea, etc.

In limbajul pseudocod actiunile (operatiile) sunt desemnate prin cuvinte cheie (cuvinte cu

inteles prestabilit) reprezentate in text prin litere subliniate sau ingrosate, pentru a le deosebi de

restul textului scris. Se utilizeaza de asemenea cateva reguli pentru alinierea pe verticala a textului

scris.

Limbajul pseudocod permite descrierea algoritmilor prin doua tipuri de enunturi (propozitii):

-enunturi standard;

-enunturi nestandard.

Page 14: cpp 1 intro - · PDF fileSiruri de caractere 44 8. Pointeri ... optice de caractere, ... -limbaje de timp real (pentru programarea unor evenimente in concordanta cu timpul real al

14

Enunturile standard reprezinta operatii cu corespondente directe intr-un limbaj de

programare de nivel inalt. Enunturile nestandard sunt fraze in limbaj natural reprezentand operatii

complexe asupra datelor. Acestea se utilizeaza in fazele incipiente de proiectare a algoritmilor, iar

pe masura clarificarii solutiilor, aceste enunturi nestandard sunt transformate integral in enunturi

standard. In final algoritmul este descris numai cu enunturi standard si scrierea programului

corespunzator intr-un limbaj de nivel inalt este o problema de rutina.

Operatii de baza

citeste lista_variabile

Se citeste de la echipamentul standard de intrare (tastatura) o lista de valori constante care se

atribuie in ordine variabilelor din lista.

scrie lista_iesire

Permite trimiterea la echipamentul de iesire (display) a rezultatelor prelucrarilor. Lista de iesire

cuprinde identificatori (nume) de variabile pentru care se afiseaza valorile acestora si siruri de

carcatere cuprinse intre ghilimele, care se afiseaza intocmai la display (mesaje).

variabila=expresie

Este operatia de atribuire. Se evalueaza expresia, iar valoarea obtinuta este atribuita variabilei.

stop

Opreste executia algoritmului.

Exemplu. Algoritm care pentru o suma de lei afiseaza numarul minim de bancnote de 100

lei, 50 lei, 10 lei, 5 lei si 1 leu.

scrie "Introduceti suma in lei:"

citeste s

n100=s/100 //impartire intreaga, se obtine catul intreg al impartirii

scrie n100, "bancnote de 100 lei"

s=s%100 //restul impartirii

n50=s/50

scrie n50, "bancnote de 50 lei"

s=s%50

n10=s/10

scrie n10, "bancnote de 10 lei"

s=s%10

n5=s/5

scrie n5, "bancnote de 5 lei"

s=s%5

scrie s, "bancnote de 1 leu"

stop

Decizia

Decizia permite selectarea unei secvente de operatii din doua secvente posibile, pe baza

testarii unei conditii. Forma generala:

Page 15: cpp 1 intro - · PDF fileSiruri de caractere 44 8. Pointeri ... optice de caractere, ... -limbaje de timp real (pentru programarea unor evenimente in concordanta cu timpul real al

15

daca conditie

secventa 1

altfel

secventa2

Modul de executie: se evalueaza conditia (expresie logica), daca are valoarea adevarat se executa

numai secventa 1, altfel (are valoarea fals) se executa numai secventa 2. In cazul in care pentru

conditie neindeplinita nu trebuie executata nicio operatie (secventa2 este vida) se poate utiliza o

forma simplificata a deciziei:

daca conditie

secventa 1

Exemplu. Rezolvarea ecuatiei de gradul al doilea ax2+bx+c=0, unde a, b, c ∈R.

scrie "Introduceti coeficientii ecuatiei:"

citeste a, b, c

daca a==0

daca b==0

daca c==0

scrie "Infinitate de solutii!"

altfel

scrie "Solutie vida!"

altfel

// ecuatie de gradul I

x=b

c−

scrie "x=", x

altfel

// ecuatie de gradul al II-lea

delta=b2-4·a·c daca delta ≥ 0 // radacini reale

x1=a

deltab

+−

2

x2=a

deltab

−−

2

scrie x1, x2

altfel

// radacini complexe

x1r=a

b

2

x2r=x1r

x1i=a

delta

2

x2i=−x1i

scrie x1r, x1i, x2r, x2i

stop

Cicluri

Cele mai multe probleme implica executia repetata a unor secvente de operatii, deci

folosirea ciclurilor. Exista trei tipuri de cicluri: ciclul cu test initial, ciclul cu test final si ciclul cu

contor.

Page 16: cpp 1 intro - · PDF fileSiruri de caractere 44 8. Pointeri ... optice de caractere, ... -limbaje de timp real (pentru programarea unor evenimente in concordanta cu timpul real al

16

Ciclul cu test initial

Secventa de operatii se executa cat timp o anumita conditie este indeplinita. Forma generala

este:

cat timp conditie

secventa

Modul de executie:

1) se evalueaza conditia: daca are valoarea adevarat se trece la pasul 2, daca are valoarea

fals se iese din ciclu;

2) se executa secventa din corpul ciclului si se trece apoi la pasul 1.

Observatii. Conditia poate fi orice expresie cu valori logice. Secventa din corpul ciclului

poate fi orice secventa si poate sa contina la randul ei alte cicluri. Este necesar ca operatiile din

corpul ciclului sa modifice valoarea conditiei, in sensul neindeplinirii acesteia pentru a se iesi din

ciclu.

Exemplu. Algoritmul lui Euclid pentru calcularea celui mai mare divizor comun a doua

numere intregi.

scrie "Introduceti doua numere intregi"

citeste m, n

r=m%n // calculeaza restul impartirii

cat timp r!=0

m=n

n=r

r=m%n

scrie "c.m.m.d.c.=", n

stop

Ciclul cu test final

Secventa de operatii din corpul ciclului se executa de asemenea cat timp este indeplinita o

anumita conditie, dar testul se efectueaza la sfarsitul ciclului. Forma generala:

executa

secventa

cat timp conditie

Modul de executie:

1) executa secventa de operatii din corpul ciclului si se trece la pasul 2;

2) evalueaza conditia, daca adevarat se trece la pasul 1, daca fals se iese din ciclu.

Exemplu. Algoritmul lui Euclid pentru calcularea celui mai mare divizor comun a doua

numere intregi.

scrie "Introduceti doua numere intregi"

citeste m, n

executa

r=m%n // calculeaza restul impartirii

m=n

n=r

cat timp r!=0

scrie "c.m.m.d.c.=", m

Page 17: cpp 1 intro - · PDF fileSiruri de caractere 44 8. Pointeri ... optice de caractere, ... -limbaje de timp real (pentru programarea unor evenimente in concordanta cu timpul real al

17

stop

Exemplu. Tabelarea valorilor unei functii, pe un interval si cu un pas >0.

],[1

3)(

2bax

x

xxf ∈

+

=

executa

scrie "Introduceti marginile intervalului si pasul"

citeste a, b, pas

cat timp (a≥b∪pas≤0) // verifica corectitudinea datelor initiale x=a

scrie " x y" // cap de tabel

cat timp x≤b

y=1

32

+

x

x

scrie x, y

x=x+pas

stop

Exemplu. Dezvoltarea in serie:

...!

...!3!2!1

132

++++++=

n

aaaae

na

In solutia acestei probleme se insumeaza un numar de termeni pana cand termenul general

indeplineste conditia:

0,!

>< εε

k

ak

executa

scrie "Introduceti pct penrtu dezvoltarea in serie si pragul"

citeste a, epsilon

cat timp epsilon≤0 suma=1

tg=a //termenul general al seriei

n=1 //calculeaza factorialul de la numitor

cat timp │tg│≥epsilon suma=suma+tg

n=n+1

tg=tgn

a⋅

scrie "Dezvoltarea in serie =", suma

stop

Ciclul cu contor

Ciclul cu contor permite executia unei secvente de operatii de un numar prestabilit de ori.

Forma generala este:

pentru var_contor=val_init, val_finala, val_pas

secventa

unde:

var_cont: variabila contor utilizata pentru contorizarea repetarilor secventei;

Page 18: cpp 1 intro - · PDF fileSiruri de caractere 44 8. Pointeri ... optice de caractere, ... -limbaje de timp real (pentru programarea unor evenimente in concordanta cu timpul real al

18

val_init: valoarea initiala a variabilei contor;

val_finala: valoarea finala a variabilei contor;

val_pas: valoarea pasului cu care se actualizeaza valoarea variabilei contor. Acest parametru

poate sa lipseasca, valoarea implicita fiind 1 (multe probleme includ cicluri cu contor avand

valoarea pasului 1).

Modul de executie:

1) se evalueaza expresiile pentru valoarea initiala, valoarea finala si valoarea pas,

determinandu-se astfel inca de la inceput numarul de repetari ale secventei;

2) se initializeaza var_contor cu val_init;

3) se compara valoarea var_contor cu val_finala, daca var_contor are o valoare ≤ val_finala

atunci se trece la pasul 4, altfel se iese din ciclu;

4) se executa secventa de operatii din corpul ciclului;

5) se incrementeaza valoarea var_contor cu val_pas si se trece la pasul 3.

Exemplu. Calcularea factorialului unui numar natural.

scrie "Introduceti un numar natural:"

citeste n

fact=1

pentru i=2,n

fact=fact·i

scrie "Factorial=", fact

stop

Exemplu. Calcularea mediei aritmetice a valorilor >0 dintr-o secventa de n numere introduse

de la tastatura.

scrie "Introduceti lungimea secventei de numere:"

citeste n

suma=0

contor=0 //contor de numere >0

pentru i=1,n

scrie "Introduceti numarul ", i, "din secventa:"

citeste x

daca x>0

suma=suma+x

contor=contor+1

daca contor==0

scrie "Nu exista numere >0 in secventa!"

altfel

suma=suma/contor //calculeaza media

scrie "Media=", suma

stop

Exemplu. Descompunerea unui numar intreg in factori primi.

scrie "Introduceti un numar intreg:"

citeste nr

fact_max=nr/2 // valoarea maxima a unui posibil factor

prim=adevarat // initial se presupune numar prim

pentru fact=2,fact_max

putere=0

cat timp nr%fact==0

nr=nr/fact

putere=putere+1

prim=fals

daca putere>0

Page 19: cpp 1 intro - · PDF fileSiruri de caractere 44 8. Pointeri ... optice de caractere, ... -limbaje de timp real (pentru programarea unor evenimente in concordanta cu timpul real al

19

scrie "Factor=", fact, " la puterea=", putere

daca prim

scrie "Numarul este prim!"

stop

Tablouri

Un tablou este o colectie de date elementare, toate de acelasi tip. Tablourile pot fi organizate

pe o dimensiune (vectori), doua dimensiuni (matrici) sau mai multe dimensiuni (tablouri n-

dimensionale).

Un element de tablou poate fi specificat prin pozitia pe care acesta o ocupa in cadrul

tabloului, utilizand cate o expresie pentru fiecare dimensiune, numita expresie indiciala:

nume_tablou [expr_indic1][expr_indic2]...[expr_indicn]

Pentru analogia cu limbajele C/C++ se va considera ca pe fiecare dimensiune de lungime k indicii

de tablou au valori de la 0 la k-1.

Exemplu. Determinarea maximului dintr-o secventa de numere (vector) si a pozitiei sale.

scrie "Introduceti lungimea vectorului:"

citeste n

scrie "Introduceti elementele vectorului"

pentru i=0,n-1

scrie "x[", i, "]="

citeste x[i]

maxim=x[0] //se presupune ca prima valoare este cea maxima

pozitia=0

pentru i=1,n-1

daca x[i]>maxim

maxim=x[i] //actualizeaza maximul

pozitia=i

scrie "Maxim=", maxim, " in pozitia=", pozitia

stop

Exemplu. Ordonarea crescatoare a unei secvente de numere (vector) prin metoda bulelor

(Bubble Sort).

scrie "Introduceti lungimea vectorului:"

citeste n

scrie "Introduceti elementele vectorului"

pentru i=0,n-1

scrie "x[", i, "]="

citeste x[i]

executa

ordonat=adevarat

pentru i=1,n-1

daca x[i-1]>x[i]

temp=x[i-1]

x[i-1]=x[i]

x[i]=temp

ordonat=fals

cat timp nu(ordonat)

scrie "Vectorul ordonat crescator:"

pentru i=0,n-1

scrie "x[", i, "]=",x[i]

stop

Page 20: cpp 1 intro - · PDF fileSiruri de caractere 44 8. Pointeri ... optice de caractere, ... -limbaje de timp real (pentru programarea unor evenimente in concordanta cu timpul real al

20

Exemplu. Calcularea mediei aritmetice a elementelor >0 dintr-o matrice oarecare.

scrie "Introduceti dimensiunile matricii:"

citeste m,n //numar de linii si numar de coloane

pentru i=0,m-1

pentru j=0,n-1

scrie "a[",i,"][",j,"]="

citeste a[i][j]

suma=0

contor=0 //contor de elemente >0

pentru i=0,m-1

pentru j=0,n-1

daca a[i][j]>0

suma=suma+a[i][j]

contor=contor+1

daca contor==0

scrie "Nu exista elemente >0!"

altfel

suma=suma/contor

scrie "Media=", suma

stop

Exemplu. Produsul a doua matrici:

Al,m·Bm,n = Cl,n

unde fiecare element al matricii produs se calculeaza cu relatia:

1,...,1,0

1,...,1,0

1

0

,,,

−=

−=⋅=∑−

=

njpentru

lipentrubac

m

k

jkkiji

scrie "Introduceti dimensiunile celor doua matrici:"

citeste l,m,n

scrie "Introduceti prima matrice:"

pentru i=0,l-1

pentru j=0,m-1

scrie "a[",i,"][",j,"]="

citeste a[i][j]

scrie "Introduceti a doua matrice:"

pentru i=0,m-1

pentru j=0,n-1

scrie "b[",i,"][",j,"]="

citeste b[i][j]

pentru i=0,l-1

pentru j=0,n-1

s=0

pentru k=0,m-1

s=s+a[i][k]·b[k][j]

c[i][j]=s

scrie "Matricea produs este:"

pentru i=0,l-1

pentru j=0,n-1

scrie "c[",i,"][",j,"]=",c[i][j]

stop

Page 21: cpp 1 intro - · PDF fileSiruri de caractere 44 8. Pointeri ... optice de caractere, ... -limbaje de timp real (pentru programarea unor evenimente in concordanta cu timpul real al

21

Functii si proceduri

Functiile si procedurile sunt secvente de operatii care se definesc intr-un algoritm o singura

data, dar pot fi executate (apelate) de mai multe ori, chiar cu unele variabile schimbate. Procedurile

pot furniza mai multe rezultate prin intermediul parametrilor. O functie furnizeaza in principiu un

singur rezultat (rezultatul principal), dar poate furniza si rezultate suplimentare prin intermediul

parametrilor, la fel ca o procedura. Deoarece in limbajele C/C++ nu sunt disponibile procedurile, in

continuare vor fi discutate numai functiile.

Forma generala a unei functii este:

functia nume_f (parametri)

secventa

unde:

nume_f : numele functiei prin intermediul caruia functia poate fi apelata;

secventa : secventa de operatii pseudocod care se executa la un apel;

parametri : prezinta partea variabila a functiei, ceea ce inseamna ca secventa de operatii se

poate executa la fiecare apel cu un alt set de variabile.

Parametrii din definitia functiei sunt parametri formali, au rol descriptiv si in principiu nu

corespund unor date concrete ale problemei de rezolvat. Apelul unei functii se face prin utilizarea

nume_f (parametri) in cadrul unor expresii. Parametrii de la apel sunt parametrii efectivi: acestia

trebuie sa corespunda ca numar cu cei formali de la definitia functiei si inlocuiesc in ordine

parametrii formali din secventa de operatii inainte de executia acesteia. Rezultatul principal,

corespunzator numelui functiei este furnizat la executia secventei printr-o operatie:

intoarce expresie

Se pot defini si functii care nu intorc un rezultat principal, deci in secventa din corpul functiei nu

exista nicio operatie intoarce. La apelul functiei anumiti parametri furnizeaza date initiale de

prelucrat pentru secventa de operatii din corpul functiei, de aceea acesti parametri pot fi considerati

parametrii de intrare. Alti parametri furnizeaza rezultate suplimentare ale prelucrarilor, in plus fata

de rezultatul principal, de aceea acestia pot fi considerati parametrii de iesire. Evident ca o functie

poate avea parametri cu dublu rol, deci sunt parametrii de intrare / iesire.

Exemplu. Calcularea )!(!

!

kmk

mC k

m−

= folosind formula factorialelor, pentru o secventa de

perechi de numere naturale m≥k. Pentru calcularea factorialului unui numar natural se va defini o

functie in cadrul algoritmului.

functia factorial (n)

fact=1

pentru i=2,n

fact=fact·i

intoarce fact

// modulul principal al algoritmului

scrie "Introduceti lungimea secventei de perechi de numere:"

citeste lung

pentru j=1,lung

executa

scrie "Introduceti doua numere naturale, m≥k:" citeste m, k

cat timp m<k

Page 22: cpp 1 intro - · PDF fileSiruri de caractere 44 8. Pointeri ... optice de caractere, ... -limbaje de timp real (pentru programarea unor evenimente in concordanta cu timpul real al

22

comb=)()(

)(

kmfactorialkfactorial

mfactorial

−⋅

scrie "Combinari=", comb

stop

Exemplu. Se definesc functii pentru calcularea produsului si catului a doua numere

complexe reprezentate sub forma trigonometrica si utilizand aceste functii se calculeaza valoarea

expresiei:

43

21

zz

zzz

⋅=

functia produs (ro1, alfa1, ro2, alfa2, ro, alfa)

ro=ro1·ro2

alfa=alfa1+alfa2

functia cat (ro1, alfa1, ro2, alfa2, ro, alfa)

ro=ro1/ro2 //testul ro2≠0 se face inainte de apel alfa=alfa1-alfa2

// modulul principal

scrie "Introduceti numerele complexe in forma trigonometrica"

citeste r1, a1, r2, a2, r3, a3, r4, a4

produs (r1, a1, r2, a2, r12, a12)

produs (r3, a3, r4, a4, r34, a34)

daca r34==0

scrie "Numitor zero! Nu se poate calcula!"

altfel

cat (r12, a12, r34, a34, r, a)

scrie "Expresia:", r, a

stop

Exemplu. Pentru o matrice citita de la tastatura se determina coloana cu numarul maxim de

zerouri. In acest scop se defineste o functie care pornind de la o matrice genereaza un vector in care

fiecare element reprezinta numarul de zerouri de pe coloana corespunzatoare a matricii. Se defineste

o alta functie care determina maximul dintre elementele unui vector si pozitia acestuia.

functia genvect (x, v, nl, nc)

pentru i=0, nc-1

cont=0

pentru j=0, nl-1

daca x[j][i]==0

cont=cont+1

v[i]=cont

functia maxvect (v, lung, vmax, vpoz)

vmax=v[0]

vpoz=0

pentru i=1, lung-1

daca v[i]>vmax

vmax=v[i]

vpoz=i

//modulul principal

scrie "introduceti dimensiunile matricii:"

citeste m,n

pentru i=0,m-1

pentru j=0,n-1

scrie "a[",i,"][",j,"]="

citeste a[i][j]

genvect (a, b, m, n)

maxvect (b, n, bmax, bpoz)

Page 23: cpp 1 intro - · PDF fileSiruri de caractere 44 8. Pointeri ... optice de caractere, ... -limbaje de timp real (pentru programarea unor evenimente in concordanta cu timpul real al

23

scrie "matricea are maxim ", bmax, " zerouri in coloana ", bpoz

stop

Exemplu. Rezolvarea unui sistem de trei ecuatii liniare cu trei necunoscute prin metoda

Cramer. Sistemul este:

a0,0·x0+ a0,1·x1+ a0,2·x2= b0

a1,0·x0+ a1,1·x1+ a1,2·x2= b1

a2,0·x0+ a2,1·x1+ a2,2·x2= b2

sau sub forma matriciala:

· =

functia det3 (y)

dete=y[0][0]*y[1][1]*y[2][2]+y[1][0]*y[2][1]*y[0][2]+

y[0][1]*y[1][2]*y[2][0]-y[2][0]*y[1][1]*y[0][2]-

y[0][1]*y[1][0]*y[2][2]-y[1][2]*y[2][1]*y[0][0]

intoarce dete

functia inloc (y, w, v, col)

pentru i=0, 2

pentru j=0, 2

w[i][j]=y[i][j]

pentru i=0, 2

w[i][col]=v[i]

// modulul principal

scrie "Introduceti coeficientii necunoscutelor:"

pentru i=0, 2

pentru j=0, 2

scrie "a[",i,"][",j,"]="

citeste a[i][j]

scrie "Introduceti termenii liberi: "

pentru i=0, 2

scrie "b[",i,"]="

citeste b[i]

ds=det3(a)

daca ds==0

scrie "Sistemul nu este Cramer!"

altfel

pentru i=0,2

inloc (a,c,b,i)

x[i]=det3(c)/ds

scrie "x[",i,"]=",x[i]

stop

A X B