cpp 1 intro - · PDF fileSiruri de caractere 44 8. Pointeri ... optice de caractere, ......
Transcript of cpp 1 intro - · PDF fileSiruri de caractere 44 8. Pointeri ... optice de caractere, ......
1
Programarea calculatoarelor
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
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
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
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:
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;
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.
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
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
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
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
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.
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.
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:
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.
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
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;
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
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
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
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
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)
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