UNIVERSITATEA SPIRU HARETFACULTATEA DE MATEMATIC INFORMATIC

GRIGORE ALBEANU (coordonator) LUMINIA RPEANU, LUMINIA RADU, ALEXANDRU AVERIAN

TEHNICI DE PROGRAMARE- Lucrri practice de programarea calculatoarelor -

EDITURA FUNDAIEI ROMNIA DE MINE, BUCURETI, 2003

Descrierea CIP a Bibliotecii Naionale a Romniei Tehnici de programare / Grigore Albeanu, Luminia Rpeanu, Luminia Radu, Alexandru Averian. - Bucureti: Editura Fundaiei Romnia de Mine, 2003 224 p., 20,5 cm Bibliogr. ISBN 973-582-665-8 I. Albeanu, Grigore II. Rpeanu, Luminia III. Radu, Luminia IV. Averian, Alexandru 004.42

Editura Fundaiei Romnia de Mine, 2003 ISBN 973-582-665-8

Coperta: Marilena BLAN Bun de tipar: 24.01.2003; Coli tipar: 14 Format: 16/61 x 86 Editura i Tipografia Fundaiei Romnia de Mine Splaiul Independenei, nr. 313, Bucureti, S. 6, O. P. 83 Tel.: 410 43 80; Fax. 410 51 62; www.spiruharet.ro

CUPRINS

Prefa ... 1. Operaii de intrare/ieire n limbajele Pascal i C 1.1. Fiiere n limbajul Pascal ... 1.2. Fiiere n limbajul C ...... 2. Structuri de date .. 2.1. Liste simplu nlnuite ... 2.2. Liste dublu nlnuite . 2.3. Liste circulare .... 2.4. Stive ... 2.5. Cozi .... 2.6. Grafuri .... 2.7. Arbori ..... 3. Metode pentru rezolvarea problemelor .... 3.1. Metoda Divide et Impera 3.2. Metoda programrii dinamice 3.3. Metoda Greedy 3.4. Metoda backtracking 3.5. Metoda Branch and Bound 4. Programare modular n Turbo Pascal ... 5. Introducere n programarea orientat obiect folosind limbajul C++ 6.Teste pentru verificarea cunotinelor ... 6.1. Teoria i practica programrii .... 6.2. Probleme pentru concursuri ... Bibliografie ...

5 7 7 17 31 32 46 50 53 55 62 87 101 101 107 116 125 135 145 173 201 201 222 224

3

Capitolele lucrrii au fost elaborate dup cum urmeaz: Prof. univ. dr. Grigore ALBEANU Prefaa, Cap. IV, Cap. V 2, Cap VI 2, Bibliografia Prof. gr. 2 Luminia RPEANU Cap. II, Cap. III, 2, Cap. VI 1. Prof. Luminia RADU Cap. I Prep. Alexandru AVERIAN Cap III 1, 3, 4, 5, Cap. V 1. Lectura textului integral al lucrrii, structurarea materialului, verificarea programelor (Pascal, C, C++) i procesarea final a materialului au fost efectuate de Prof. univ. dr. Grigore Albeanu.

4

Prefa

Realizarea unui software complex presupune att organizarea intrrilor i ieirilor, ct i o foarte bun gestiune a datelor i prilor componente. Aceast lucrare continu demersul iniiat n cadrul volumului Algoritmic i programare n limbajul Pascal, Editura Fundaiei Romnia de Mine, 2001, oferind cadrul teoretic i practic n nvarea tehnicilor de programare fundamentale. Sunt tratate modaliti de lucru cu fiiere, structuri de date complexe, metode de elaborarea algoritmilor, organizarea subprogramelor n uniti de translatare precum i conceptele de baz ale metodei de proiectare bazat pe lucrul cu obiecte. Conceptele, tehnicile i strategiile sunt ilustrate prin exemple, att n limbajul Pascal, ct i n limbajul C. Ultima parte ilustreaz metodologia OOP (engl. Object Orieted Programming) cu ajutorul limbajului C++. Materialul este util att elevilor i studenilor ce urmeaz specializrile informatic i matematic-informatic, absolvenilor n vederea examenelor de titularizare, definitivat, ct i pregtirii complementare n cadrul nvmntului postuniversitar de informatic. Prin colecia de exemple, probleme propuse (la nivelul fiecrui capitol) i teste de evaluare general (capitolul 5) lucrarea este util pregtirii individuale sau n cadrul cercurilor de elevi sau seminariilor studeneti, pentru participarea la concursurile de programare i la diferite examene: bacalaureat, licen, titularizare etc. Studenii de la cursurile cu frecven redus i nvmnt la distan vor gsi exemple utile aprofundrii noiunilor transmise n cadrul cursurilor: Algoritmic i programare, Tehnici de programare, Informatic i Bazele informaticii.Grigore ALBEANU 5

6

1. Operaii de intrare/ieire n limbajele Pascal i C1.1. Fiiere n limbajul Pascal Definiia 1.1.1. Se numete fiier, o structur de date ale crei componente, numite nregistrri, de dimensiune fix sau variabil, sunt stocate (depuse), de obicei, pe un suport magnetic (band sau disc) de pe care pot fi citite/scrise direct din program. Observaia 1.1.1. Dac nregistrrile din fiier au o dimensiune variabil, se impune existena unor marcaje speciale numite separatori de nregistrare. Observaia 1.1.2. Organizarea datelor n fiiere este necesar, dac: volumul datelor prelucrate este foarte mare i depete capacitatea memoriei interne disponibile. datele trebuie stocate n vederea unei prelucrri ulterioare, n cadrul aceluiai program sau al altora. Observaia 1.1.3. n Turbo Pascal se poate lucra cu trei tipuri de fiiere: 1) fiiere cu tip componentele au acelai tip i sunt stocate pe disc. 2) fiiere fr tip componentele sunt blocuri de informaii de lungime fix i sunt stocate pe disc. 3) fiiere text componentele sunt caractere structurate pe linii de lungimi variabile putnd fi stocate pe suport magnetic sau, fac obiectul operaiilor de intrare-ieire cu consola (tastatura, ecran). Observaia 1.1.4. Tipul fiier se aseamn cu tipul tablou prin faptul c toate componentele au acelai tip, dar se deosebete de acesta prin modul de acces la componente i prin accea c numrul componentelor unui tip fiier nu este limitat. Accesul la componentele unui fiier poate fi: 1) secvenial - pentru a accesa o anumit component trebuie parcurse toate componentele care o preced. 2) direct orice component se poate accesa imediat dac se precizeaz numrul ei de ordine in fiier, fr s fie necesar parcurgerea elementelor precedente. Accesul direct este permis numai pentru fiierele cu sau fr tip stocate pe disc. Discul este singurul suport adresabil, care permite calculul adresei unei componente, dac i se cunoate lungimea i numrul de ordine n fiier.7

Fiecrui fiier cu sau fr tip stocat pe disc i se asociaz de ctre compilator o variabil numit indicator de fiier care cuprinde, n tot timpul prelucrrii fiierului, numrul de ordine al componentei curente. Observaia 1.1.5. ntr-un program Turbo Pascal un fiier se identific printr-o variabil de tip fiier. Aceast variabil de tip fiier nu are voie s apar n atribuiri sau expresii. Prelucrarea fiecrui fiier trebuie precedat de apelul unei proceduri standard ASSIGN, prin care variabilei de tip fiier i se asociaz numele unui anumit fiier fizic. Toate operaiile n care se va specifica variabila respectiv se vor face asupra fiierului fizic asociat prin procedura assign. Procedure assign Forma general Efect Apelul Procedure assign (var fiier;nume:string); I se asociaz variabilei de tip fiier din program, numele fiierului fizic de pe suportul extern . assign (fiier, nume); unde fiier reprezint identificatorul variabilei de tip fiier din program, iar nume reprezint o expresie de tip string, a crei valoare este numele fiierului fizic de pe suport extern.

Observaia 1.1.6. Asocierea rmne valabil pn la un alt apel al procedurii assign, asupra aceluiai fiier extern. Apelul se termin cu eroare dac fiierul fizic este deschis n momentul apelului. Prelucrrile admise asupra unui fiier sunt: Crearea fiierului Scrierea componentelor n fiier. Exploatarea fiierului Citirea i prelucrarea componentelor fiierului Actualizarea fiierului Adugarea, modificarea sau tergerea unor componente ale fiierului. Observaia 1.1.7. Oricare ar fi modul de prelucrare a unui fiier, accesul la componentele acestuia este permis numai dac acesta este deschis. Deci orice prelucrare ncepe cu deschiderea fiierului i se ncheie cu nchiderea sa. Deschiderea unui fiier se realizeaz prin comenzile reset (fiier) sau rewrite(fiier). nchiderea fiierului prin comanda close(fiier).8

Executarea procedurii reset (fiier) realizeaz: Iniializarea indicatorului de fiier cu valoarea 0 (pentru fiiere cu sau fr tip); Iniializarea variabilei Filemode din unit-ul System astfel nct s permit, n continuare, executarea de operaii de citire pentru fiiere de tip text sau operaii de citire/scriere pentru fiiere cu tip sau fr tip. Observaia 1.1.8. Apelul se termin cu eroare, dac fiierul fizic nu exist. Dac fiierul este deschis n momentul apelului, acesta se nchide, apoi se redeschide. Apelul procedurii rewrite are forma: Rewrite(fiier) i executarea procedurii const n: Iniializarea indicatorului de fiier cu valoarea 0 (pentru fiier cu sau fr tip). Iniializarea variabilei filemode pentru a permite n continuare: operaii de scriere pentru fiier de tip text, respectiv operaii de scriere/citire pentru fiiere cu sau fr tip. Observaia 1.1.9. Apelul se termin cu eroare, dac nu este loc suficient pe disc pentru noul fiier. Dac fiierul fizic asociat exist pe suportul extern coninutul su este ters. Dac fiierul s-a deschis prin executarea acestei proceduri, operaiile de citire sunt permise numai dup ce s-au fcut scrieri. Apelul procedurii close are forma: close(fiier) i are ca efect nchiderea fiierului prin care operaiile de citire/scriere a componentelor lui sunt interzise pn la o nou deschidere. Definiia 1.1.2. Poziia curent dintr-un fiier (zona n care se efectueaz operaiile de intrare/ieire) se numete indicator de fiier. Fiiere text. Creare i exploatare Un fiier text este format din caractere structurate pe linii. Fiecare linie este terminat cu un marcaj sfrit de linie (eng. eol - end of line), format din caracterele CR i LF (tastei ENTER i corespunde secvena de caractere CR (eng. carriage return) i LF (eng. line feed) cu codurile ASCII 13, respectiv 10, secven care reprezint marcajul de sfrit de linie). Observaia 1.1.10. Fiierele text se stocheaz pe disc sau sunt asociate unui dispozitiv logic (i se termin cu caracterul ^Z)9

Observaia 1.1.11. Tipul fiier text se declar conform diagramei: Tip fiier texttext

Dimensiunea zonei tampon asociat unui fiier text este, n general 128 bytes. Un fiier text poate fi deschis prin apelul procedurilor: rewrite - sunt permise numai operaii de scriere reset - sunt permise numai operaii de citire append - sunt permise numai operaii de scriere; realizeaz deschiderea la sfrit a unui fiier creat pe disc i permite adugarea unor noi linii la sfritul fiierului. Observaia 1.1.12. Accesul poate fi numai secvenial (pas cu pas), nu poate fi accesat direct. Procedurile i funciile pentru prelucrarea fiierelor text Procedura read Apelul: Read (fiier, v1 [, v2, , vn]); Efect: Citete din fiierul fizic asociat variabilei fiier n variabila (variabilele) v1[, , vn] unde: fiier este numele variabilei asociate fiierului fizic (dac lipsete se consider INPUT), iar v1, v2, , vn sunt n variabile (n>1) care pot fi de tip: char, string, integer i variantele, real i variantele n virgul mobil. Procedura readln Apelul: Readln (fiier, v1[, v2 ,, vn]); Efect: Citete din fiierul fizic asociat variabilei fiier n variabila v1[, , vn] i trece la linie nou n fiier. Este echivalent cu secvena: read(fiier, v1[, v2 ,, vn]); readln(fiier); Procedura write Apelul: Write(fiier, v1[, v2, , vn]); Efect: Scrie n fiierul fizic asociat variabilei fiier, variabilele v1[, v2, , vn]. Procedura writeln Apelul: Writeln (fiier, v1 [, v2, , vn]); Efect: Scrie n fiierul fizic asociat variabilei fiier, variabilele v1[, v2, , vn] i un marcaj de sfrit de linie n fiierul fizic asociat variabilei fiier. Este echivalent cu secvena: write(fisier, v1[, v2, ..., vn]); writeln(fisier);10

Funcia EOF (End Of File) este de tip boolean, deci ntoarce dou valori: true, dac poziia curent n fiier este dup ultimul caracter al fiierului, sau fiierul este vid, respectiv false, n celelalte cazuri. Apel: eof [(var fiier)] Funcia seekoln este de tip boolean, deci ntoarce dou valori: true, dac avem sfrit de linie, respectiv false, n caz contrar Apel: seekeoln[(fiier)]; Efect: atunci cnd caracterul curent ce urmeaz a fi citit din zona tampon asociat fiierului este un caracter egal cu SPAIU sau TAB, se crete adresa caracterului curent din zona tampon astfel nct s fie un caracter diferit de spaiu sau tab. Returneaz true, cnd caracterul curent care urmeaz s fie citit din zona tampon reprezint un marcaj de sfrit de linie sau de sfrit de fiier; false altfel. Funcia EOLN returneaz un rezultat de tip boolean, true dac indicatorul este la sfrit de linie, iar false, n caz contrar. Apel: eoln[(fiier)]; Observaia 1.1.13. Funcia seekeoln difer de funcia eoln prin faptul c face salt peste caracterul SPAIU (blanc) sau TAB, nainte de a testa sfritul de linie. Funcia SEEKEOF este de tip boolean Apel Seekeof [(fiier)]; Efect a) se modific adresa caracterului curent din zona tampon astfel nct acesta s fie un caracter diferit de spaiu, tab sau sfrit de linie (face salt peste ele) b) returneaz: true, cnd poziia curent n fiier este dup ultimul caracter al acestuia i false, n caz contrar. Observaia 1.1.14. Funcia seekeof difer de eof prin faptul c face un salt peste caracterele: tab, blanc, sfrit de linie, nainte de a testa sfritul de fiier. Procedura APPEND(nume fiier) deschide fiierul n vederea adugrii la sfarit n fiier. Procedura ERASE Apelul: Erase(fiier); Efect: Realizeaz tergerea fiierului fizic asociat variabilei fiier. n momentul apelului fiierul trebuie s fie nchis. Procedura RENAME schimb n program numele fiierului de pe suport extern. Apelul rename (fiier,nume) realizeaz redenumirea11

fiierului fizic asociat variabilei fiier cu numele dat prin irul de caractere nume. n momentul apelului fiierul asociat variabilei fiier trebuie s existe, s fie nchis i nu trebuie s existe un alt fiier cu numele nume. Exemplificare: rename(f,'document.dat') schimb numele fizic asociat lui f cu numele fizic document. Aplicaia 1.1.1. S se afieze numrul cuvintelor citite dintr-un fiier text, introdus de la tastatur (cuvintele sunt separate prin unul sau mai multe spaii). Soluie:program nr_cuv_din_fis_INPUT; var c:char; n:longint; begin n:=0; write('linia:'); while not eof do begin while seekeoln do begin read(c); while (c' ') and not eoln do read(c); n:=n+1 end; readln; write('Introducei linia:') end; writeln('Fiierul cuprinde:',n,'cuvinte') end. {n reine numarul de cuvinte din text}

Exemplu de executare: Intrare: Ana are main Crina are calculator

Ieire: Fiierul are 6 cuvinte.

Aplicaia 1.1.2. S se afieze numrul numerelor din fiecare linie a fiierului standard de intrare INPUT. Soluie:program afis_nr_de_numere_din_liniile_fisierului_input; var n,nr,i:byte; begin i:=1; write('linia', i,':'); 12

while not eof do begin n:=0; while not seekeoln do begin read(nr); inc(n) end; readln; writeln('din linia', i, 's-au citit' ,n, 'numere'); inc(i); write('linia',i,':') end end.

Exemplu de executare: Intrare: linia 1: 10 20 30 linia 2: 40 50 Fiiere cu tip

Ieire: din linia 1 s-au citit 3 numere din linia 2 s-au citit 2 numere.

Definiia 1.1.3. Fiierele cu tip sunt construite din articole cu lungime fix, de acelai tip (pot fi: array, string, set, record sau tipuri simple de date-intregi, char, etc); se mai numesc i fiiere cu prelucrare la nivel de articol. Declararea unui fiier cu tip se realizeaz astfel:FILE OF IDENTIFICATOR DE TIP

Exemplul 1. S declarm un fiier ale crui articole sunt numere ntregi. Soluie: type fisint = file of integer; var a:fisint; sau var a: file of integer; Exemplul 2. S se declare un fiier cu articole de tip record. Soluie: type inreg = record nume:string[30]; varsta:byte; end; fisier = file of inreg; var f:fisier;{f-reprezint fiierul cu tip ce poate conine articole }13

Observaia 1.1.15. Accesul la datele fiierului cu tip este secvenial sau direct. Citirea i scrierea din/in fiier 1) read(fiier, v1, v2, , vn); - prelucreaz n componente succesive din fiier, ncepand cu componenta situat la poziia indicatorului de articol i se memoreaz n variabilele v1, v2, , vn (valoarea indicatorului de articol crete cu 1, dup citirea unei componente). 2) write(fisier, v1, v2, , vn); - se scrie coninutul variabilelor v1,v2,,vn n componentele succesive ale fiierului fiier (indicatorul creste cu 1 dup scrierea fiecrei variabile), evident tot ncepand de la poziia iniial a indicatorului. Funcii i proceduri utile n prelucrarea fiierelor cu tip 1) EOF(fiier) ntoarce true, dac pointerul este la sfaesit de fiier, sau false, altfe; 2) Filesize(fiier) ntoarce numrul de componente al fiierului asociat variabilei fiier; 3) Filepos(fiier) ntoarce poziia pointerului(numrul de ordine al componentei curente); 4) Seek(fisier,n) - pointerul se poziioneaz la valoarea n. Exemplu: seek(fisier,7)-pointerul de fiier puncteaz a aptea valoare. 5) Truncate(fiier) terge toate componentele fiierului ncepand cu componenta indicat de pointerul de fiier pan la ultima component din fiier. 6) Erase(fiier)- terge fiierul; 7) Rename(fiier,noul-nume) schimb din program numele fiierului de pe suport extern. Aplicaia 1.1.3. Se consider fiierul cu nregistrri DATE , care are urmtoarea structur: S se scrie un program care sorteaz fiierul descris anterior dup valorile campului cod material. Soluie:type inr = record cod_mat:integer; den_mat:string[20]; cod_mag:integer; cant:real; um:string[4]; pu:real; end; fisier = file of inr; var inr1, inr2:inr; f:fisier;ok:boolean; i, j, t, mag:integer; m1,m2:integer; c_er:integer; 14 cod_mat:string[5]; den_m:string[20]; cod_mag:integer; cant:real; um :string[4]; pu:real;

procedure sort1(i,j:integer); var k:integer; begin repeat ok:=true; for k:=i to j-1 do begin seek(f,k); read(f,inr1,inr2); if inr1.cod_mat>inr2.cod_mat then begin seek(f,k); write(f,inr2,inr1); ok:=false end end; until ok; end; {program principal} begin assign(f,'date');reset(f); repeat ok:=true; for i:=0 to filesize(f)-2 do begin seek(f,i); read(f,inr1,inr2); if inr1,cod_mag>inr2.cod_mag then begin seek(f,i); write(f,inr2,inr1);ok:=false end; end until ok; close(f); reset(f);read(f,inr1); mag:=inr1.cod_mag; i:=0; writeln('Magazia:',inr1.cod_mag); while not eof(f) do begin read(f,inr1); with inr1 do if mag=cod_mag then begin j:=filepos(f)-1; sort1(i,j) end else begin i:=filepos(f)-1; mag:=inr1.cod_mag; writeln(Magazia:, cod_mag); end; end; end. 15

Fiiere fr tip Definiia 1.1.4. Fiierele fr tip sunt constituite din blocuri de lungime fix i aceeai pentru fiecare bloc. Observaia 1.1.15. Un bloc cuprinde o succesiune de octei. Citirea/scrierea dintr-un fiier fr tip presupune transferul unuia sau mai multor blocuri. Declararea fiierelor fr tip se realizeaz astfel:FILE

Deschiderea fiierelor fr tip se realizeaz astfel: Rewrite(fiier,[dimensiune_bloc]) Reset(fiier,[dimensiune_bloc]); unde dimensiune_bloc este de tip ntreg i reprezint numrul de octei pe care a fost scris blocul(implicit este 65536 octei) Citirea i scrierea: Blockread(fiier, variabil, nr_blocuri_care_se_vor_citi)-citete din fiier n variabila un numr de blocuri specificate. Blockwrite(fiier, variabil, nr_blocuri_care_se_vor_scrie)scrie blocurile specificate. Observaia 1.1.16. Indicatorul de fiier reine numrul blocului curent. Accesul poate fi secvenial sau direct. Observaia 1.1.17. Asemnator cu fiierele cu tip se pot folosi urmtoarele funcii/proceduri: seek, eof, filesize, filepos, erase, rename. Aplicaia 1.1.4. S se creeze un fiier fr tip cu n inregistrri avand cmpurile: nume:string[16]; varsta:integer;type inregistrare=record nume:string[20]; varsta:integer; end; var f:file;inr:inregistrare; n,i:integer; begin assign(f,'date');write('n=');readln(n); rewrite(f); for i:=1 to n do begin write('Nume=');readln(inr.nume); write('Varsta=');readln(inr.varsta); blockwrite(f,inr,1); end; close(f); end. 16

1.2. Fiiere n limbajul C Fiierul este un grup de octei stocai pe un suport de memorie extern care este tratat n mod unitar de ctre sistemul de operare. Lucrul cu fiiere n C presupune cunoscut modul de lucru cu date de tip struct i cu pointeri. Se utilizeaz conceptul de flux (stream). Un flux se reprezint, n C, printr-un pointer la o entitate de tip FILE care conine informaii despre poziia curent n flux, indicatori de eroare i de sfrit de fiier, zone tampon (eng. buffers) asociate. Limbajul C permite folosirea a dou tipuri de flux: text i binare. Un flux text presupune transferul de caractere organizate n linii de caractere. Fluxul binar reprezint o succesiune de octei care nu suport nici o modificare n timpul transferului. Deschiderea i nchiderea unui fiier Orice fiier nainte de a fi prelucrat trebuie deschis. Dup terminarea prelucrrii unui fiier acesta trebuie nchis. Forma general a funciei pentru deschidere: FILE *fopen(const char *numele_fis, const char *mod); - "deschide un fiier" i-i asociaz numele respectiv; - returneaz un pointer spre tipul FILE (vezi fiierul STDIO.H) sau Null, n caz de eroare unde: numele_fis = pointer ctre numele fiierului ce urmeaz a fi deschis; mod = pointer spre un ir de caractere care definete modul de prelucrare al fiierului, dup deschidere. Se definete astfel: r = deschiderea unui fiier text pentru citire w = deschiderea unui fiier text pentru scriere a = deschiderea unui fiier text pentru adugare r+ = deschiderea unui fiier text pentru modificare r+b = citire/scriere binar rb = citire binar wb = scriere binar Observaia 1.2.1. Cu funcia fopen, un fiier inexistent se poate "deschide" n modul r, w sau a, iar n acest caz este i creat. Observaia 1.2.2. Dac se deschide un fiier existent n modul w atunci se va crea unul nou cu acelai nume, vechiul coninut se pierde. Apelul: fp = fopen("INPUT.TXT") - la apel se deschide fiierul cu numele INPUT.TXT i se stabilete o legtur logic ntre pointerul fp i fiierul INPUT.TXT.17

Observaia 1.2.3. Deschiderea unui fiier n modul a pentru adugarea de nregistrri dup ultima nregistrare existent n fiier. Observaia 1.2.4. Fiierele corespunztoare dispozitivelor standard nu se deschid de ctre utilizator, ntruct ele sunt deschise automat la lansarea programului. Observaia 1.2.5. Fiierele disc i dispozitivele periferice sunt gestionate de variabila pointer. Prelucrarea pe caractere a unui fisier Fiierele standard pot fi scrise i citite caracter cu caracter, folosind dou funcii simple: putc i getc. Forma general: int putc(int c, FILE *pf); returneaz valoarea lui c, reprezentand codul ASCII al caracterului scris n fiier sau -1, dac este eroare; pf reprezint pointer spre tipul FILE a crui valoare a fost returnat de funcia fopen la deschiderea fiierului n care se scrie. Observaia 1.2.6. n particular pf poate fi unul din pointerii: stdout ieire standard; stderr - ieire pe terminal n caz de eroare; stdaux ieire serial; stdprn - ieire paralel la imprimant. Forma general: int getc(FILE *pf); returneaz codul ASCII al caracterului citit sau EOF la sfrit de fiier; pf - pointer spre tipul FILE a crui valoare a fost returnat de funcia fopen la deschiderea fiierului. n particular pf poate fi pointerul stdin (citire (intrare) de la tastatur). nchiderea unui fiier (eliberarea spaiului de memorie alocat folosind fopen i ntreruperea legturii logice) se realizeaz cu funcia fclose care are prototipul int fclose (FILE *pf); i returneaz valoarea: 0, la nchidere normal sau -1, n caz de eroare. Aplicaia 1.2.1. S se elaboreze un program pentru a copia intrarea standard la ieirea standard folosind funciile putc i getc. Soluie: #include void main(void) { int c; c= getc (stdin); while (c != EOF) {putc(c, stdout); c=getc(stdin);} }18

Aplicaia 1.2.2. Cum se copiaz intrarea standard la imprimant? Soluie: # include void main(void){ int c; c= getc (stdin); while (c != EOF){putc(c, stdprn); c=getc(stdin);} } Operaii de intrare/ieire cu iruri de caractere Biblioteca standard a limbajului C conine funciile: fgets i fputs care permit citire dintr-un, repectiv scrierea ntr-un fiier ale crui nregistrri sunt iruri de caractere. Prototipul: char *fgets (char *s, int n, FILE *pf); returneaz valoarea pointerului s sau NULL la ntlnirea sfritului de fiier; s - pointerul spre zona n care se pstreaz caracterele citite (numele unui tablou de tip char de dimensiune cel puin n); n - dimensiunea n octei a zonei n care se citesc caracterele din fiier; pf - pointerul spre tipul FILE a crui valoare s-a definit la deschiderea fiierului. Observaia 1.2.7. Citirea se oprete la ntlnirea caracterului '\n' sau dup citirea a cel mult n-1 caractere. n acest caz, n zona receptoare se transfer caracterul '\n' i apoi caracterul '\0' (NULL) Funcia fputs scrie ntr-un fiier un ir de caractere care se termin prin '\0' i are prototipul int fputs(const char *s, FILE *pf); Returneaz codul ASCII al ultimului caracter scris n fiier sau 1 la eroare; pf - pointer spre tipul FILE care definete fiierul n care se scrie; s-pointerul spre zona care conine irul de caractere, care se scrie. Observaia 1.2.8. Pentru a citi de la intrarea standard stdin, se poate folosi funcia gets, care nu mai are parametrii pf i n. Parametrul pf este implicit stdin. Observaia 1.2.9. La fiierele text, cnd este ntalnit caracaterul '\n', acesta este transformat ntr-o secven "newline". Fiierele binare nu produc transformri. Operaii de intrare-ieire cu format Acest lucru se realizeaz folosind funciile: fscanf- citire cu format dintr-un fiier; fprintf - scriere cu format n fiier. Opereaz la fel ca printf i scanf cu excepia faptului c lucreaz cu fiiere, nu cu consola.19

Apelul lui fscanf: fscanf(FILE *pf, char *format, par1, par2, ,parn) citete date, conform formatului, din stream; returneaz valoare EOF, la ntalnirea sfaritului de fiier; pf - pointer spre tipul FILE, a crui valoare a fost definit prin apelul funciei fopen; format - conine texte i/sau specificatori de format (_). Parametrii par1, par2, ,parn definesc zonele receptoare ale datelor citite prin intermediul funciei fscanf. Exemplificare: Apelul fscanf(pf, "%d %c %f", &i, &n, &c); Apelul fprintf(FILE *pf, char *format, par1, parn) - scrie date, n stream, conform formatului. Poziionarea ntr-un fiier Pan acum am citit/scris datele unui fiier n mod secvenial de la nceput pn la sfarit. Utiliznd funcia fseek se poate accesa orice articol al unui fiier (acces aleator). Cu ajutorul ei se poate deplasa capul de citire/scriere al discului n vederea prelucrrii ntregistrrilor fiierului ntr-o ordine oarecare, diferit de cea secvenial. Prototipul Returneaz Int fseek(FILE *pf, long deplasament, int origine); 0, la poziia corect sau o valoare diferit de 0, n caz de eroare;

unde: deplasament reprezint numrul de octei peste care se va deplasa capul de citire/scriere al discului, iar origine ia una din valorile: 0 1 2 Deplasamentul se consider de la nceputul fiierului; Deplasamentul se consider din poziia curent a capului de citire/scriere; Deplasamentul se consider de la sfaritul fiierului.

O alt funcie util n cazul accesului aleator este funcia ftell, care indic poziia capului de citire/scriere din fiier. Prototip Returneaz Long ftell(FILE *pf); O valoare de tip long care definete poziia curent a capului de citire/scriere, i anume reprezint deplasamentul n octei a poziiei capului fa de nceputul fiierului .

Aplicaia 1.2.3. Folosind funcia fseek( ) cutai i citii orice byte dintr-un fiier specificat20

Soluie: #include #include void main(void) { FILE *pf; long loc; if ((pf= fopen("g1.cpp", "r"))==NULL) { printf ("Nu pot deschide fisierul! "); exit (1); } printf(Introducei locaia , n octeti, din fiier, ce se va vizualiza! ); scanf(%d, &loc); if (fseek(fp, loc, 0)){ printf("Eroare de cautare! "); exit(1); } printf("Valoarea de la locatia %ld este %c", loc, getc(pf)); fclose(pf); } Alte funcii pentru prelucrarea fiierelor 1 nchiderea unui fiier se realizeaz cu ajutorul funciei fclose care are prototipul: int fclose (FILE *f); Funcia returneaz valoarea 0 la nchidere normal, respectiv -1 n caz de eroare. 2 Testarea atingerii sfritului de fiier se poate realiza cu ajutorul funciei feof, care are prototipul: int feof (FILE*f); Funcia feof returneaz valoare 0, dac indicatorul de fiier nu este la sfritul fiierului, respectiv o valoare diferit de 0, dac indicatorul de fiier este la sfrit. 3 int rename(const char *nume_vechi, const char *nume_nou);redenumete un fiier; 4 int remove(const char *filename); - terge un fiier de pe suportul de informaie pe care este memorat; 5 size_t fread(void *ptr, size_t size, size_t n, FILE *stream);citete date dintr-un fiier; mai precis, citete n elemente, fiecare cu lungimea size din stream, ntr-un bloc specificat de ptr; 6 size_t fwrite(const void *ptr, size_t size, size_t n, FILE * stream) - adaug fiierului stream n elemente, fiecare avand dimensiunea size din blocul specificat de ptr.21

1.3. Probleme rezolvate R1.3.1. Se consider un fiier text IN.txt ce conine numere ntregi dispuse pe mai multe linii i separate prin spaii. Scriei un program care creeaz un fiier OUT.txt ce conine pe fiecare linie media aritmetic a numerelor situate pe aceeai linie n fiierul IN.txt. Media aritmetic va fi scris cu doua zecimaleVarianta Pascal program medie; var x,s,i:integer; f,g:text; begin assign(f,'IN.TXT'); RESET(f); assign(g,'out.TXT'); REWRITE(g); while not eof(f) do begin s:=0; i:=0; repeat read(f,x); i:=i+1; s:=s+x; until eoln(f); writeln(g,s/i:4:2); writeln(s/i:4:2); readln(f); end; close(f); close(g); end.Varianta C #include #include void main (void){FILE *fin, *fout; char sir[256],sn[256]; long int n,i,j1,j2,suma; float media; if (!(fin=fopen("IN.txt","r"))){ printf("\n Nu pot deschide sursa!"); exit(1);} if (!(fout=fopen("OUT.TXT","w"))){ printf("\n Nu pot crea fisierul destinatie!"); exit(1);} while (!feof(fin)){ fgets(sir,256,fin); n=0;i=0;j1=0;j2=0;suma=0; while(sir[i]){ if (sir[i]=' ') {sn=substr(sir,j1,j2); suma=suma+atoi(sn); j1=j2=i+1;sn=' ';i++; } else {i++; j2++;}} media=suma/n; fprintf(fout, "%10.2f\n",media); } fclose(fin);fclose(fout); } char substr(char sir[256]; int j1,j2){ char ss[]="';int i; if ((j1>strlen(sir)||(j2>strlen(sir)) return 1; for(i=j1;i6 par. S se determine toate reprezentrile lui n ca sum de numere prime (sum cu numr minim de termeni). Rezultatele vor fi scrise n fiierul OUTPUT.TXT, fiecare linie coninand toi termenii dintr-o reprezentare. Exmplu: Pentru n = 8, atunci OUTPUT.TXT conine 35 53 Nu se consider perechile (1, 7) i (7, 1) din cauza numrului 1. AP16. [Factor prim] Se consider un ir de n numere ntregi. S se determine factorul prim care apare la puterea cea mai mare n descompunerea produsului celor n numere. Pe prima linie a fiierului INPUT.TXT este scris numrul n, reprezentand numrul de elemente din ir; pe urmtoarea linie sunt scrise cele n numere. Rspunsul se va afia pe ecran sub forma: i^j cu semnificaia: factorul i la puterea j Exemplu: INPUT.TXT pe ecran se va afia : 4 3^4 24 9 17 2127

AP17. [Cel mai mare divizor comun] Se consider n numere scrise n baza 16. S se determine cel mai mare divizor comun al celor n numere. Pe prima linie a fiierului INPUT.TXT este scris numrul de numere n; pe urmtoarele n linii se gsesc numerele scrise n hexazecimal. Numrul care reprezint c.m.m.d.c. al celor n numere, se va afia pe ecran. Exemplu: INPUT.TXT se va afisa : 4\n 1A \n 8 \n 10 \n 2 2 AP18. [Cifre romane] S se scrie un program care transform un numr scris cu cifre romane n scrierea cu cifre arabe. n fiierul INPUT.TXT sunt scrise mai multe numere n scriere romana (corecte), fiecare pe cte o linie. Este posibil ca unele din cifrele romane sa fie scrise cu litere mici. Rspunsurile se vor afia pe ecran, fiecare numr pe cte o noua linie. Exemplu: INPUT.TXT pe ecran se va afia: CDLIV 454 MMMMDLXXIII 4573 MCLXVI 1166 CMXLLVIII 948 AP19. [Propoziii] Se consider un text scris pe n linii (n fiierul de intrare INPUT.TXT). Fiecare linie constituie o propoziie. Cuvintele sunt formate doar din litere mari i litere mici i sunt desprite prin: spaiu, virgul i punct. Nici o propozitie nu are mai mult de 250 de caractere. Textul nu conine cuvinte n care s apar liniua de desprire (exemplu: "ntr-un"). S se determine propoziia cu cele mai multe cuvinte i s se afieze pe ecran scriind fiecare cuvnt pe linie nou avnd prima liter majuscul; separatorii nu se vor afia. Exemplu: INPUT.TXT Ce faci Unde esti O sa reusim buna dimineata Alo, este ora sapte si treizeci de minute, fix. se va afisa Alo Este Ora Sapte Si Treizeci De

28

Minute Fix AP20. [Matrice] Se d matricea A cu m linii i n coloane. S se scrie un program care prin intermediul unui meniu realizeaz urmtoarele operaii: Elimin din matrice linia L i coloana k fr a folosi o nou matrice; Ordoneaz cresctor elementele de pe o coloan oarecare j prin interschimbri de linii. Datele de intrare se vor citi dintr-un fiier text. AP21. [Ordonare] Se consider un tablou bidimensional ptratic de dimensiune n*n de numere ntregi. Se cere s se inverseze liniile i coloanele acestuia astfel nct tabloul obinut s conin elemente de pe diagonala principal n ordine cresctoare. Datele de intrare se citesc din fiierul de intrare INPUT.TXT sub forma urmtoare: pe prima linie este scris numrul n, reprezentnd numrul de linii i coloane, iar pe urmtoarele n linii, se gsesc elementele tabloului linie dup linie. Rezultatul va fi scris n fiierul OUTPUT.TXT. Pe fiecare linie a fiierului se va scrie o linie a tabloului obinut. Exemplu: INPUT.TXT OUTPUT.TXT 3 -1 8 7 243 234 156 165 -1 7 8 AP22. [Frecvene] Se consider un fiier INPUT.TXT care conine un text. Se cere determinarea listei cu frecvena de apariie maxim. In cazul cand exist mai multe soluii se vor afia toate. Fiierul de intrare conine pe fiecare linie cel mult 250 de caractere. Nu se va face distincie ntre litera mic i litera mare. Rezultatul se va afia pe ecran. Exemplu: INPUT.TXT pe ecran se va afisa: Mama si cu tata merg la piata A apare de 7 ori Memoriu, memoriu! M apare de 7 ori

29

AP23. [Ordonare n matrice] Se consider o matrice de dimensiune n*m. S se reaeze elementele n matrice astfel nct ele s apar n ordine cresctoare att pe linii ct i pe coloane. Matricea A se gsete n fiierul de intrare INPUT.TXT, fiecare linie a matricei pe cte o linie din fiier. Nu sunt specificate valoarile pentru n i m. Matricea obinut se va scrie, n mod similar, n fiierul OUTPUT.TXT. n cazul n care exist mai multe soluii se va scrie n fiier numai una. Exemplu: INPUT.TXT OUTPUT.TXT 3 2 5 44 3 1 122222 6 7 55 4 3 2 333334 4 10 4 2 4 5 444445 34 5 6 8 2 4 555667 5 3 2 4 41 3 8 10 34 41 44 55 AP24. O matrice cu elemente ntregi este memorat n fiierul text in.txt sub urmtorul format: pe prima linie numrul n de linii i numrul m de coloane. Pe urmtoarele n linii, elementele de pe fiecare linie a matricii. Citii matricea i tiprii-o pe coloane n fiierul out.txt. AP25. Citii un text scris pe mai multe linii n fiierul text.txt. Calculai, pentru fiecare liter a alfabetului, procentul de cuvinte care ncep cu acea liter. Separatori ntre cuvinte vor fi considerai: blancul, punctul, virgula i sfritul de linie. AP26. Creai cu editorul Pascal un fiier text pe mai multe linii. Scriei un program care calculeaz: a) Numrul de cuvinte din fiier. Ca separatori ntre cuvinte se vor considera blancurile i sfritul de linie. b) Tiprii liniile care conin cel puin o vocal. c) Cte linii conin mai mult de n cuvinte, n citit de la tastatur?

30

2. Structuri de dateO structur de date este o mulime de date organizate ntr-un anumit mod mpreun cu relaiile dintre acestea. n funcie de modul de alocare, structurile de date se clasific n: structuri de date statice : tabloul, nregistrarea, mulimea, fiierul. Structurile de date statice ocup o zon de memorie constant pe toat durata de executare a blocului n care apare declaraia i elementele ocup poziii fixe. Fiierele sunt structuri de date externe (vezi capitolul 1). structuri de date semistatice: stiva alocat static, coada alocat static. Structurile de date semistatice ocup o zon de memorie de dimensiune constat, alocat pe toat durata executrii blocului n care apare declaraia de structur, iar elementele ocup poziii variabile pe parcursul executrii programului. structuri de date dinamice: lista nlnuit, structuri arborescente. Structurile de date dinamice ocup o zon de memorie de dimensiune variabil, alocat dinamic. Alocarea dinamic permite gestionarea memoriei n timpul executrii programului. Ele sunt mult mai flexibile dect cele statice i din aceast cauz sunt extrem de avantajoase. Liste: O list este o colecie de elemente de informaie (noduri) aranjate ntr-o anumit ordine. Lungimea unei liste este numrul de noduri din list. Structura corespunztoare de date trebuie s ne permit s determinm eficient care este primul/ultimul nod n structur i care este predecesorul/succesorul (dac exist) unui nod dat. Limbajele Pascal sau C(++) ofer posibiliti de implementare a acestor structuri att static ct i dinamic. Operaiile curente care se fac n liste sunt: inserarea unui nod, tergerea (extragerea) unui nod, concatenarea unor liste, numrarea elementelor unei liste etc. Implementarea unei liste se poate face n principal n dou moduri: Implementarea secvenial, n locaii succesive de memorie, conform ordinii nodurilor n list. Avantajele acestei tehnici sunt accesul rapid la predecesorul/succesorul unui nod i gsirea rapid a primului/ultimului nod. Dezavantajele sunt inserarea/tergerea relativ complicat a unui nod i faptul c nu se folosete ntreaga memorie alocat listei. Implementarea nlnuit. Fiecare nod conine dou pri: informaia propriu-zis i adresa nodului succesor. Alocarea31

memoriei fiecrui nod se poate face n mod dinamic, n timpul rulrii programului. Accesul la un nod necesit parcurgerea tuturor predecesorilor si, ceea ce poate lua ceva mai mult timp. Inserarea/tergerea unui nod este, n schimb, foarte rapid. Listele se pot clasifica dup numrul de legturi n: liste simple liste duble liste circulare O list simpl are o singur legtur, legtura ultimului element este adresa NIL/NULL. Pentru a accesa lista avem nevoie de o variabil care s pstreze adresa primului element (cap sau prim). O list dubl are dou legturi: legtura de tip urmtor i legtura de tip precedent sau anterior. O lista circular este o lista n care, dup ultimul nod, urmeaz primul, deci fiecare nod are succesor i predecesor. Listele se pot clasifica dup locul n care se fac operaiile de adugare/eliminare astfel: stive cozi 2.1. Liste simplu nlnuite ntre nodurile unei liste simplu nlnuite este definit o singur relaie de ordonare. Fiecare nod conine un pointer a crui valoare reprezint adresa nodului urmtor din list.Limbajul Pascal

type lista

= ^nod nod=record inf:tip ; urm: lista; end;

Limbajul C(++) typedef struct nod { tip inf; struct nod *urm; }lista;

unde urm este adresa urmtorului nod (pointer ctre urmtorul nod), iar inf este un cmp de informaie util. Operaii asupra listei simplu nlnuite Crearea unei liste simplu nlnuite: 1. Se iniializeaz pointerul prim cu Nil/NULL, deoarece lista la nceput este goal; 2. Se rezerv zon de memorie n memoria heap pentru nodul curent;32

3. Se ncarc nodul curent cu date; 4. Se determin adresa ultimului nod i se realizeaz legtura cu nodul creat; 5. Se reia cu pasul 2 dac se introduce un nod nou. Inserarea unui element x al crui cmp cheie a fost iniializat n faa unei liste nlnuite LISTA-INSEREAZA(p,x) 1: urm(x) p 2: dac pNIL atunci px Cutarea ntr-o list nlnuit p a elementului x se realizeaz prin subprogramul LISTA-CAUTA i returneaz pointerul la acest obiect. LISTA-CAUTA(p,x) 1. qp 2. ct timp qNIL i cheie(q)x execut qurm(q) 3. returneaz q Probleme rezolvate 1. Fiind dat o list simplu nlnuit cu elemente numere ntregi s se realizeze un program care s execute urmtoarele operaii: crearea, parcurgerea, adugarea unui nod la nceputul listei, adugarea unui nod la sfritul listei, tergerea unui nod de pe o poziie dat. Observaii:Limbajul Pascal: Procedura NEW(pointer)- alocarea dinamic a memoriei pentru variabila dinamic pointer. Procedura DISPOSE(pointer)eliberarea memoriei ocupate de ctre variabila dinamic pointer. Limbajul C(++) Funcia MALLOC se folosete pentru a rezerva octei din memoria heap. Trebuie inclus fiierul antet: stdlib.h sau alloc.h

Rezolvare: Parcurgerea unei liste liniare simplu nlnuite se realizeaz cu un pointer care pleac de la capul listei i va referi pe rnd fiecare nod, prelucrnd informaiile din nod apoi se trece la urmtorul nod, prelucrm informaiile din nod etc.33

tergerea unui nod de pe o poziie dat p din interiorul listei se realizeaz astfel: se parcurge lista pn la pozitia p-1, se pstreaz nodul de pe poziia p, se realizeaz legtura ntre nodul p-1 i p+1 i, apoi se elibereaz memoria ocupat de nodul p. Implementare n Pascal:type lista=^nod; nod=record inf:integer; urm:lista end; var p,x:integer;cap:lista;{adresa primului nod al listei} procedure adaug(var cap:lista;x:integer); {adaugarea la sfarsitul listei} var nou,q:lista; begin new(nou);nou^.inf:=x;nou^.urm:=nil; if cap=nil then cap:=nou else begin q:=cap; while q^.urm nil do q:=q^.urm; q^.urm:=nou; end; end; procedure adaug_inc(var cap:lista;x:integer); {adaugarea la inceput} var nou:lista; begin new(nou);nou^.inf:=x;nou^.urm:=nil; {crearea nodului nou} if cap=nil then cap:=nou else begin nou^.urm:=cap;cap:=nou; {realizarea legaturii si primul nod devine nodul creat} end; end; procedure listare(cap:lista);{listarea listei} var t:lista; begin t:=cap; while tnil do begin write(t^.inf,' '); {prelucrarea informatiei} t:=t^.urm; {trecerea la urmatorul nod} end; end; procedure sterge(var cap:lista; p:integer); 34

{stergerea nodului de pe pozitia p} q,w,t:lista;i:integer; var begin if cap=nil then writeln('Lista vida !!! ') else if p=1 then begin {stergere la inceputul listei} q:=cap; cap:=cap^.urm; dispose(q); end else if (cap nil) then begin t:=cap; i:=1; while (t^.urm nil) and (i+1urm; free(p); return prim; } void adauga(lista*prim) { /*adauga un nod la o lista simplu inlantuita si returneaza pointerul spre nodul adaugat sau zero daca nu s-a realizat adaugarea*/ lista *p,*q; for (p=prim;p->urm!=NULL;p=p->urm) q=(lista*) malloc(sizeof(q)); scanf("%d",&q->inf); q->urm=NULL; p->urm=q; } void main(){ lista *prim; prim=creare(); parcurgere(prim); prim=sterg_inc(prim); printf("\n"); parcurgere(prim); adauga(prim); parcurgere(prim); } lista *creare(){ int n,i,inf; lista *prim,*p,*q; printf("nr. de elemente");scanf("%d",&n); printf("informatia primului nod"); scanf("%d",&inf); prim=(lista*)malloc(sizeof(prim)); prim->inf=inf;prim->urm=NULL; for(q=prim,i=2;iinf=inf;p->urm=NULL; q->urm=p; q=p; } return(prim); } void parcurgere(lista *p){ lista *q; for (q=p;q;q=q->urm) printf("%d ",q->inf); } 36

2. Inversarea legturilor ntr-o list simplu nlnuit. Rezolvare: Se parcurge lista iniial folosind trei variabile dinamice p1, p2, p3 care vor face referire la elementele consecutive din list. p1 va fi capul listei modificate. Implementare Pascal: program invers; type lista=^nod; nod=record inf:integer; urm:lista end; var i,n,x:integer; p:lista; procedure creare(var p:lista; x:integer); var q:lista; begin if p=nil then begin new(p); p^.inf:=x; p^.urm:=nil end else begin q:=p; while q^.urmnil do q:=q^.urm; new(q^.urm); q^.urm^.inf:=x; q^.urm^.urm:=nil; end; end; procedure listare(p:lista); var q:lista; begin q:=p; while qnil do begin write(q^.inf,' '); q:=q^.urm end; end; function inversare(p:lista):lista; Subprogramul de inversare n C: lista* invers(lista*p){ var p1,p2,p3:lista; lista *p1,*p2,*p3; begin p1=p; p1:=p; p2=p->urm; p2:=p^.urm; p->urm=NULL; p^.urm:=nil; while (p2){ while p2nil do begin p3=p2->urm; p3:=p2^.urm; p2->urm=p1; p2^.urm:=p1; p1=p2; p1:=p2; p2=p3; p2:=p3; } end; return p1; inversare:=p1; } end;37

begin read(n); for i:=1 to n do begin read(x); creare(p,x) end; listare(p);writeln; p:=inversare(p); listare(p) end. 3. S se efectueze suma a dou polinoame rare (polinom cu foarte muli coeficieni egali cu zero) folosind liste simplu nlnuite. Rezolvare: Lista are ca informaie gradul i coeficientul fiecrui termen de coeficient nenul. Pentru a calcula suma este necesar s parcurgem listele celor dou polinoame i s adugm corespunztor n cea de-a treia list. Implementare Pascal: type lista=^nod; nod=record grad:1..5000; coef:integer; urm:lista end; var a,b,p,q,r:lista; i,n,m:integer; procedure creare(var p:lista); begin write('cati coeficienti nenuli are polinomul');readln(n); new(p);readln(p^.coef,p^.grad); p^.urm:=nil;b:=p; {b este adresa ultimului nod} for i:=2 to n do begin new(a); write('coef ',i,':');readln(a^.coef); write('grad ',i,':');readln(a^.grad); b^.urm:=a; b:=a; b^.urm:=nil end end; procedure listare(p:lista); var a:lista; begin a:=p; while anil do begin write(a^.coef,'x^', a^.grad,' +'); a:=a^.urm end; writeln(#8,' '); end;38

procedure aduna(p,q:lista;var r:lista); var a,b,c,d:lista; begin a:=p;b:=q; {c este adresa ultimului nod pentru lista suma} while (anil) and (bnil) do if a^.grad=b^.grad then begin if r=nil then begin new(c);c^.grad:=a^.grad; c^.coef:=a^.coef +b^.coef; r:=c; r^.urm:=nil; end else begin new(d); d^.grad:=a^.grad; d^.coef:=a^.coef+b^.coef; c^.urm:=d;c:=d;c^.urm:=nil end; a:=a^.urm;b:=b^.urm; end else if a^.gradurm=NULL; } else if (prim->inf>inf){ nou->urm=prim;prim=nou; } else { p=q=prim; while(p&&p->infurm;} if (p) {q->urm=nou; nou->urm=p;} else{q->urm=nou; nou->urm=NULL;} } } return prim; } void parcurgere(lista *p){ lista *q; for (q=p;q;q=q->urm) printf("%d ",q->inf); }43

Exerciiu: S se implementeze aplicaia de mai sus n Pascal. 6. S se scrie un program pentru interclasarea a dou liste ordonate simplu nlnuite. Rezolvare: Se va parcurge simultan cele dou liste urmnd ca introducerea unui nod n lista final s fie fcut din lista care are valoarea informaiei din nod mai mic. Implementare C: #include #include #include typedef struct nod {int inf; struct nod*urm;}lista; lista *inter(lista *prim1, lista*prim2){ lista *prim,*ultim; if (prim1->inf>prim2->inf){ prim=prim2;prim2=prim2->urm; } else { prim=prim1; prim1=prim1->urm; } ultim=prim; while(prim1&&prim2) if (prim1->inf>prim2->inf){ ultim->urm=prim2; ultim=prim2; prim2=prim2->urm; } else {ultim->urm=prim1; ultim=prim1; prim1=prim1->urm; } if (prim1) ultim->urm=prim1; else ultim->urm=prim2; return prim; } lista *creare(void); void parcurgere(lista *p);44

void main(){ lista *prim1,*prim2,*prim; prim1=creare(); prim2=creare(); /* parcurgere(prim1) */; prim=inter(prim1,prim2); parcurgere(prim1); } lista *creare(){ int n,inf; lista *prim,*p,*q,*nou; printf("nr. de elemente");scanf("%d",&n); prim=NULL; for(int i=1;iinf=inf; if (prim==NULL){ prim=nou; prim->urm=NULL; } else if (prim->inf>inf){ nou->urm=prim;prim=nou; } else { p=q=prim; while(p&&p->infurm;} if(p) {q->urm=nou;nou->urm=p;} else { q->urm=nou;nou->urm=NULL; } } } return prim; } void parcurgere(lista *p){ lista *q; for (q=p;q;q=q->urm) printf("%d ",q->inf); } Exerciiu: S se implementeze aplicaia de mai sus n limbajul Pascal.45

2.2. Liste dublu nlnuite Pentru liste duble create dinamic modul de definire a unui nod este:Limbajul Pascal type lista=^nod; nod=record inf:tip; urm, ant:lista; end; typedef struct nod{ inf tip; struct nod *urm; struct nod *ant; }lista;

Operaiile care se pot defini asupra listelor dublu nlnuite sunt aceleai ca i n cazul listelor simplu nlnuite: - crearea unei liste dublu nlnuite; - accesul la un element al unei liste dublu nlnuite; - inserarea unui nod ntr-o list dublu nlnuit; - tergerea unui nod dintr-o list dublu nlnuit; - tergerea unei liste dublu nlnuite. Probleme rezolvate 1. S se scrie un program care va conine un meniu cu principale operaii asupra listei dublu nlnuite. Implementarea Pascal a soluiei: type lista=^nod; nod=record inf:integer; urm,ant:lista end; var cap:lista; x:integer; procedure creare(var cap:lista); begin new(cap); write('inf=');readln(cap^.inf); cap^.urm:=nil;cap^.ant:=nil; end; procedure adaugare(var cap:lista); var q,nou:lista; begin new(nou);readln(nou^.inf);nou^.urm:=nil; q:=cap; while q^.urm nil do q:=q^.urm; q^.urm:=nou;nou^.ant:=q; end;46

procedure inserare(var cap:lista); var nou,q:lista; k,i:integer; begin writeln('unde inserezi? '); read(k);new(nou); write('ce? ');readln(nou^.inf); if k=1 then begin cap^.ant:=nou; nou^.urm:=cap; nou^.ant:=nil; cap:=nou; end else begin q:=cap; i:=1; while (q^.urmnil) and (iurm=prim->ant=NULL; ultim=prim; for(i=2;iinf); p->ant=ultim;ultim->urm=p; p->urm=NULL; ultim=p; } } void parcurg(lista*p){ if (p){ printf("%d ",p->inf); parcurg(p->urm); } } void parcurg1(lista *p){ lista *q; for (q=p;q;q=q->ant) printf("%d ",q->inf); }49

2.3. Liste circulare Dup numrul de legturi, listele circulare se mpart n: liste simple i liste duble. Listele circulare simple sunt liste simple care au n plus propietatea c valoarea cmpului urmtor a ultimului nod este adresa capului listei. Listele circulare duble sunt liste duble care au propietatea c legtura urmtor a celui de-al doilea cap este primul cap i legtura anterior a primului cap este al doilea cap. Crearea i parcurgerea listei circulare simplu nlnuite n limbajul C: #include #include #include typedef struct nod{ int inf; struct nod *urm;}lista; void main(){ lista *prim,*p,*q; int i,n; /*crearea listei circulare*/ printf("inf primului nod"); prim=(lista*)malloc(sizeof(lista)); scanf("%d",&prim->inf);prim->urm=NULL; p=prim; printf("nr de elemente");scanf("%d",&n); for (i=2;iinf); p->urm=q;p=q; } p->urm=prim; /*parcurgerea listei*/ printf("%d ",prim->inf); for (q=prim->urm;q!=prim;q=q->urm) printf("%d ",q->inf); } Problem rezolvat: Se d un grup de n copii aezai n cerc, care sunt numrai din m n m. Copilul care a fost numrat cu valoarea m este eliminat. Dndu-se pasul de eliminare m se cere s se precizeze ordinea ieirii din cerc.50

Rezolvare: Simularea eliminrii copiilor se realizeaz cu o list circular la care se realizeaz eliminarea nodului care are ca informaie numrul copilului scos din joc. Numrarea se va face parcurgnd m elemente de la poziia de unde s-a efectuat ultima tergere. Implementarea Pascal (Lista circular este simpl.) type lista=^nod; nod=record inf:integer; urm:lista end; var i,n,m,j:integer; prim,q,p:lista; procedure creare(var prim:lista;x:integer); begin new(prim); prim^.inf:=x; prim^.urm:=prim end; procedure adaugare(var prim:lista;x:integer); var q,p:lista; begin new(q); q:=prim; while q^.urmprim do q:=q^.urm; new(p); p^.inf:=x; q^.urm:=p;p^.urm:=prim; end; procedure listare(prim:lista); var q:lista; begin new(q);q:=prim; write(q^.inf,' '); while q^.urmprim do begin q:=q^.urm; write(q^.inf,' ') end; end; begin {program principal} read(n); creare(prim,1); for i:=2 to n do adaugare(prim,i); listare(prim); read(m); p:=prim; for i:=1 to n-1 do begin if i=1 then for j:=1 to m-2 do p:=p^.urm else for j:=1 to m-1 do p:=p^.urm; q:=p^.urm; write(q^.inf,' '); p^.urm:=q^.urm; dispose(q); end; writeln('castigator=',p^.inf); end.51

Implementarea C (Lista circular este dubl). #include #include typedef struct nod{int inf; struct nod *urm,*ant; }lista; lista *prim,*p,*q; void creare(void); void parcurgere(void); int n,m,i,k; void main(){ creare(); printf("pasul de numarare");scanf("%d",&m); parcurgere(); while (p!=p->ant){ for( i=1;iurm; printf("%d ",p->inf); p->ant->urm=p->urm; p->urm->ant=p->ant; q=p;p=p->urm;free(q); } printf("%d",p->inf); } void parcurgere(){ for (p=prim,i=1;iurm) printf("%d",p->inf); /* p=p->urm;*/ } void creare(){ printf("nr. de copii");scanf("%d",&n); prim=(lista*)malloc(sizeof(lista));prim->inf=1; prim->urm=prim->ant=NULL; p=prim; for (i=2; iinf=i; p->urm=q; q->ant=p; p=q; } q->urm=prim;prim->ant=q; }

52

2.4. Stive O stiv (stack) este o list liniar cu proprietatea c operaiile de inserare/extragere a nodurilor se fac n/din vrful listei. Ultimul nod inserat va fi i primul ters, stivele se mai numesc i liste LIFO (eng. Last In First Out) sau liste pushdown.

push popCel mai natural mod de reprezentare pentru o stiv este implementarea secvenial ntr-un tablou S[1 .. n], unde n este numrul maxim de noduri. Primul nod va fi memorat n S[1], al doilea n S[2], iar ultimul n S[top], unde top este o variabil care conine adresa (indicele) ultimului nod inserat. Algoritmii de inserare i de tergere (extragere) a unui nod: function push(x, S[1 .. n]) {adauga nodul x in stiva} if top = n then return stiva plina top top+1 S[top] x return succes function pop(S[1 .. n]) {sterge ultimul nod inserat din stiva si il returneaza} if top =0 then return stiva vida x S[top] top top-1 return x Cei doi algoritmi necesit timp constant, deci nu depind de mrimea stivei.53

Problem rezolvat: Realizai un meniu n limbajul Pascal care s conin operaii asupra stivei.

type stiva=^nod; nod=record inf:integer; urm:stiva end; var cap:stiva; x:integer; procedure adauga(var cap:stiva); var nou:stiva; begin new(nou); writeln('Ce sa adaug? '); readln(nou^.inf); nou^.urm:=nil; if cap=nil then cap:=nou else begin nou^.urm:=cap; cap:=nou; end; end; procedure sterge(var cap:stiva); var q:stiva; begin if cap=nil then writeln('Stiva vida') else begin q:=cap; cap:=cap^.urm; dispose(q) end; end; procedure parcurgere(cap:stiva); var q:stiva; begin q:=cap; while q nil do begin writeln('|',q^.inf,'|'); q:=q^.urm end; writeln('___') end;54

Rezolvare: Implementarea Pascal:

begin while x 4 do begin writeln('1.Adaugare'); writeln('2.Stergere'); writeln('3.Listare'); writeln('4.Iesire'); writeln('Dati optiunea'); readln(x); case x of 1:adauga(cap); 2:sterge(cap); 3:parcurgere(cap) end end end. Exerciiu: S se implementeze n limbajul C aplicaia de mai sus. Probleme propuse 1. S se scrie un program care citind numere ntregi din fiierul in.txt creeaz o stiv i o afieaz. S se transforme un numr din baza 10 n baza b folosind o stiv. 2. Pe o linie de cale ferat se gsesc, ntr-o ordine oarecare, n vagoane numerotate de al 1 la n. Linia continu cu alte k linii de manevr. Cunoscnd ordinea iniial a vagoanelor, s se obin la ieire vagoanele n ordine: 1,2 ,n; liniile de manevr sunt destul de lungi nct s ncap pe o singur linie toate cele n vagoane. Indicaie: Se dorete partiionarea vagoanelor n k submulimi care au vagoanele ordonate cresctor 2.5. Cozi O coad (eng. queue) este o list liniar n care inserrile se fac doar n capul listei, iar extragerile doar din coada listei. Cozile se numesc i liste FIFO (eng. First In First Out). O reprezentare secvenial pentru o coad se obine prin utilizarea unui tablou C[0 .. n-1], pe care l tratm ca i cum ar fi circular: dup locaia C[n-1] urmeaz locaia C[0]. Fie p variabila care conine indicele locaiei predecesoare primei locaii ocupate i fie u variabila care conine indicele locaiei ocupate ultima oar. Variabilele p i u au aceeai valoare atunci i numai55

atunci cnd coada este vid. Iniial, avem p= u= 0. Inserarea i tergerea (extragerea) unui nod necesit timp constant. Operaii asupra cozii: function insert-queue(x, C[0 .. n-1]) {adauga nodul x in capul cozii} p (p+1) mod n if p=u then return coada plina C[p] x return succes function delete-queue(C[0 .. n-1]) {sterge nodul din coada listei si il returneaza} if p=u then return coada vida u (u+1) mod n x C[u] return x Testul de coad vid este acelai cu testul de coad plin. Dac s-ar folosi toate cele n locaii, atunci nu am putea distinge situaia de coad plina i cea de coad vid, deoarece n ambele situaii am avea p = u. Se folosesc efectiv numai n-1 locaii din cele n ale tabloului C, deci se pot implementa astfel cozi cu cel mult n-1 noduri. Problem rezolvat: Relizarea unui meniu pentru implementarea static a cozii. Rezolvare: Cea mai simpl implementare a cozii static este folosirea unui tablou. Pentru gestionarea cozii este nevoie de dou elemente: p poziia primului element i u poziia de dup ultimul element din coad. Se va face o utilizare circular a spaiului alocat astfel: urmtoarea poziie este p mod n +1. Implementarea Pascal: TYPE coada=array[1..50] of integer; var c:coada; p,n,u,o,x:integer; procedure adaugare(var c:coada; var p,u:integer;x:integer); begin if p(u mod n)+1 then begin c[u]:=x; u:=u mod n +1 end else writeln('coada plina'); end;56

procedure stergere(var c:coada; var p,u,x:integer); begin if pu then begin x:=c[p]; p:=p mod n+1 end else writeln('coada goala'); end; procedure listare(c:coada;p,u:integer); var i:integer; begin if p=u then writeln('coada goala') else begin i:=p; while iu do begin write(c[i],' '); i:=i mod n+1 end; end; end; begin writeln('nr max de elem'); read(n);n:=n+1; p:=1;u:=1; repeat writeln('1..adaugare'); writeln('2..stergere'); writeln('3..listare'); write('citeste optiunea');readln(o); case o of 1: begin write('introduceti numarul adaugat');readln(x); adaugare(c,p,u,x); end; 2: begin stergere(c,p,u,x); if pu then writeln(x); end; 3: listare(c,p,u); end; writeln; until o=4; end. Exerciiu: S se implementeze aplicaia de mai sus n limbajul C++.57

Problem rezolvat: S se creeze un program care s conin un meniu cu operaii asupra unei cozi alocate dinamic. Rezolvare: Implementarea n limbajul C++: #include #include #include // intrri-ieiri n C++ typedef struct nod {int inf; struct nod *urm; }lista; void adaug(lista* &prim, int x){ lista *nou, *p; nou=new lista; // crearea unui nod n C++ nou->inf=x;nou->urm=NULL; if (prim==NULL) prim=nou; else { nou->urm=prim; prim=nou; } } lista * creare(){ int n,x; lista*prim; prim=NULL; clrscr(); coutn; for (int i=0;ij atunci relaia: ai,j = li,1u1,j + li,2u2,j + +li,j-1uj-1,j + li,juj,j conduce la: li,j = (ai , j

lk =1

j 1

i ,k

u k , j ) u j , j , i > j 2.

Soluia sistemului considerat se obine prin rezolvarea sistemelor Ly=b (inferior triunghiular) i Ux=y (superior riunghiular). Observm c, dac exist 1 j n astfel nct uj,j =0 atunci procedeul nu mai poate continua. De asemenea, cnd uj,j este mic, acurateea rezultatelor scade deoarece erorile de rotunjire se nmulesc cu 1/uj,j. Este necesar astfel, interschimbarea ecuaiilor sistemului astfel nct la pasul j, valoarea uj,j s fie, n valoare absolut (modul), cea mai mare. Se va obine, astfel, descompunerea PA=LU unde P este o matrice obinut din matricea In=i,j=(if i = j then 1 else 0), prin147

interschimbarea liniilor conform interschimbrii intervenite pentru matricea A. Urmtorul pas const n rezolvarea sistemelor Ly=Pb i Ux=y. Implementarea variantei stabile este realizat de procedurile LUSTAB i LUSISTAB din unitatea de translatare MATH i vor fi utilizate n cadrul aplicaiei R4.4. Programul prezentat mai jos, utilizeaz descompunerea LU fr interschimbare, implementat de procedura LUDESC pentru rezolvarea sistemului de ecuaii dat. n plus se calculeaz determinantul matricei sistemului i inversa acesteia (cnd exist din punct de vedere al reprezentrii numerelor n virgul mobil). Se folosesc procedurile suplimentare LUSISTEM i LUDET. Aceast metod este util atunci cnd avem de rezolvat mai multe sisteme cu aceeai matrice sau cnd dorim o soluie cu precizie ridicat. Textul surs al unitii MATH este descris n finalul seciunii. Programul Pascal este urmtorul: program R4_1; uses math; var a:matrice; {tip de date definit in math} b,x,y,c,e:vector; {tip de date definit in math} i,j,k,n:integer; det:real; begin writeln; write('Dimensiunea sistemului');readln(n); writeln('Matricea sistemului este :'); for i:=1 to n do begin write('Linia',i:2,' '); for j:=1 to n do read(a[i,j]); writeln end; writeln; writeln('Termenul liber este :'); for i:=1 to n do read(b[i]); writeln; ludesc(n,a); if not succes {variabil definit n math} then writeln(' Sistemul este LUDESC incompatibil') else begin lusistem(n,a,b,x); writeln; writeln(' Solutia sistemului este :');writeln; for i:=1 to n do writeln(x[i]:10:6); writeln;148

end.

ludet(n,a,det); writeln('LU-Determinantul matricei sistemului este: ',det); writeln; writeln('Matricea inversa - pe coloane este:'); for j:=1 to n do begin write(' Coloana ',j,' '); for i:=1 to n do e[i]:=0; e[j]:=1; lusistem(n,a,e,y); for i:=1 to n do begin write(y[i]:10:4,' '); if i mod 6 = 0 then writeln end; writeln end end

R4.2. [LLT] O matrice cu numere reale, simetric este pozitiv definit, dac se poate scrie ca produsul dintre matricea inferior triunghiular L i transpusa acesteia. S se scrie o procedur care s testeze dac o matrice este pozitiv definit i n caz afirmativ, s obin descompunerea LLT, unde prin LT notm transpusa matricei L. S se utilizeze aceast procedur pentru a rezolva un sistem de ecuaii, cu matrice pozitiv definit. Rezolvare: Dac A este o matrice simetric i pozitiv definit, atunci exist o matrice inferior triunghiular L, astfel nct A=LLT. Elementele matricei L se obin prin scrierea egalitii : a1,1 a1, 2 L a1,n l1,1 0 L 0 l1,1 l 2,1 L l n ,1 a 2,1 a 2, 2 L a 2,n = l 2,1 l 2, 2 L 0 0 l 2, 2 L l n , 2 , M M O M M O M M M O M M a 0 L l n,n n,1 a n , 2 L a n ,n l n ,1 l n, 2 L l n, n 0 prin urmtoarele relaii:

l1,1 = a1,1 ;

li ,1 = ai ,1 l1,1 ; i>1;149

n l j , j = a j , j l 2,k , j>1; j k =1 j 1 li , j = ai , j l i ,k l j ,k l j , j , i>j>1. k =1

12

Procedeul se blocheaz cnd exist 1 j n astfel nct rezultatul expresiei de sub radical este negativ sau zero. n aceast situaie matricea nu este pozitiv definit. Dac matricea este simetric i pozitiv definit atunci pentru a rezolva sistemul Ax = b se consider cele doua sisteme Ly = b i LTx=y care se rezolva prin substitutie (eliminare) nainte, respectiv napoi. Procedura LLTD verific dac matricea, primit ca argument, este pozitiv definit i obine descompunerea LLT, n caz afirmativ. Procedura LLSISTEM rezolv cele dou sisteme triunghiulare. Procedurile sunt incluse n unitatea de translatare MATH. Ele sunt folosite n programul de mai jos. program r4_2; uses math; var a:matrice;n,i,j:integer; b,x,y:vector; begin writeln; write('Dimensiunea sistemului:');read(n); for i:=1 to n do begin write('Linia ',i); for j:=1 to n do read(a[i,j]); writeln end; writeln('Termenul liber :'); for i:=1 to n do read(b[i]); writeln; lltd(n,a); if not nenul then write('Eps este prea mare ') else if not pozdef then write('Matricea nu este pozitiv definita') else begin writeln('Matricea sistemului este pozitiv definita'); llsistem(n,a,b,x); writeln('Solutia sistemului este :'); for i:=1 to n do writeln (x[i]:8:4); end end.150

R4.3. [Iterativitate]. S se utilizeze metodele iterative Iacobi i GaussSeidel pentru a rezolva un sistem de ecuaii liniare (numrul ecuaiilor fiind egal cu numrul necunoscutelor). Rezolvare: Considerm sistemul Ax=b, unde A este o matrice ptratic, de dimensiune n, cu elemente reale. Presupunem c ai,i 0 pentru oricare 1 i n . Atunci sistemul ai,1 x1 + ai,2 x2 + + ai,n xn = bi , i=1,2, ... ,n; se mai poate scrie astfel :

xi = bi ai , j x j ai ,i , i = 1, 2, , n. j i Dac presupunem c x(0) este o aproximare iniial a soluiei sistemului, atunci formula de mai sus sugereaz urmtoarea metod iterativ pentru determinarea soluiei sistemului Ax=b:

xi( m +1) = bi ai , j x (jm ) ai ,i , i = 1, 2, , n; m 0. j i Aceasta este metoda aproximrii simultane (metoda lui Iacobi). Dac n membrul drept al relaiei anterioare, utilizm componentele recent calculate, obinem metoda aproximrii succesive (metoda Gauss-Seidel). Iteraia Gauss-Seidel este definit prin formula:i 1 xi( m +1) = bi ai , j x (jm +1) j =1

j =i +1

a

n

i, j

x (jm ) ai ,i , i=1, 2, .., n; m 0.

Cele dou metode converg n cazul unui sistem liniar cu matrice diagonal dominant: a i ,i > ai , j , i =1, 2, , n.

j i

Funcia Pascal diag_dom verific dac o matrice ptratic de dimensiune n este diagonal dominant. Procedurile Iacobi i Seidel implementeaz cele dou formule iterative. Acestea sunt folosite n programul urmtor, care determin soluia unui sistem de ecuaii liniare cu matrice diagonal dominant. Algoritmul se oprete dup un numr de iteraii specificat sau cnd precizia eps a fost atins.151

program r4_3; uses math; var a:matrice; b,x:vector; i,j,n,niter:integer; begin writeln; write('Dimensiunea sistemului>');read(n); writeln('Coloanele matricei --- b '); for i:=1 to n do begin for j:=1 to n do read(a[i,j]); read (b[i]); writeln end; write('Numar-iteratii >');read(niter); if diag_dom(n,a) then begin for i:=1 to n do x[i]:=0; iacobi(n,a,b,niter,x); writeln; writeln('Solutia obtinuta prin metoda Iacobi :'); for i:=1 to n do writeln (x[i] ); for i:=1 to n do x[i]:=0; Seidel(n,a,b,niter,x); writeln; writeln('Solutia obtinuta prin metoda Gauss-Seidel:'); for i:=1 to n do writeln(x[i]) end else write(' Algoritmii Iacobi i Gauss-Seidel nu converg.') end. R4.4. [Prelucrarea datelor prin metoda celor mai mici ptrate] Fie ARxR, A = {(x1 ,y1), (x2 ,y2), ..., (xn ,yn)}. Presupunem c yi sunt valorile n xi ale unei funcii reale a crei expresie analitic nu este cunoscut. Se cere identificarea unui model f, care s minimizeze suma ptratelor erorilor:

S = ( y i f ( xi ) ) .2 i =1

n

Rezolvare: Pentru a determina un astfel de model, se folosete metoda celor mai mici ptrate. Aceasta este aplicat frecvent pentru urmtoarele modele (dintre care se va face alegerea ): y = a + b x (liniar); y = a xb (putere); y = a bx (exponential); y = c1 +c2 x+...+ ck+1xk(polinomial); y = a + b/x152

(hiperbolic) etc. i implic rezolvarea unor sisteme de ecuatii, necunoscutele fiind coeficienii curbei. Pentru modelul liniar sistemul (cu necunoscutele a i b) ce trebuie rezolvat este urmtorul:n n na + b xi = y i ; i =1 i =1 n n n 2 a x i + b x i = x i y i . i =1 i =1 i =1

Determinarea parametrilor modelului putere se bazeaz pe rezolvarea urmtorului sistem:n n n ln a + b ln xi = ln y i ; i =1 i =1 n n n 2 ln a ln xi + b ln xi = ln xi ln y i i =1 i =1 i =1

cu necunoscutele ln a i b. Modelul exponenial necesit rezolvarea urmtorului sistem:n n n ln a + ln b xi = ln y i ; i =1 i =1 n n n ln a xi + ln b xi2 = xi ln y i i =1 i =1 i =1

cu necunoscutele ln a i ln b. n cazul modelului polinomial, trebuie rezolvat urmtorul sistem cu k+1 ecuaii i k+1 necunoscute {c0 ,c1,...,ck}:n n n c0 + c1 xi + L + c k xik = y i ; i =1 i =1 i =1 n n n n k +1 2 c0 xi + c1 xi + L c k xi = xi y i ; i =1 i =1 i =1 i =1 L n n n n c0 xik + c1 xik +1 + L + c k xi2 k = xik y i . i =1 i =1 i =1 i =1

Pentru determinarea parametrilor modelului hiperbolic, trebuie rezolvat urmtorul sistem cu dou ecuaii i necunoscutele a i b:153

n n 1 an + b = y i ; i =1 x i i =1 n 1 n n y a + b 1 = i . 2 i =1 xi i =1 x i i =1 x i

Pentru rezolvarea acestor sisteme, programul r4_4, utilizeaz procedurile LUSTAB i LUSISTAB din unitatea MATH, anunate la problema R4.1. Datele de intrare sunt nregistrate n fiierul text 'reg.dat', creat cu ajutorul unui editor de texte, sau este ieirea unui alt program de prelucrare. Valorile sunt nregistrate cte o pereche pe rnd. Programul cere numrul de perechi i tipul modelului matematic al datelor. Pentru fiecare model se afieaz suma ptratelor erorilor sau mesaje adecvate privind inaplicabilitatea metodei pentru datele considerate. Dac datele sunt corecte din punctul de vedere al modelului atunci se afieaz i parametrii acestuia. Programul Pascal este urmtorul: program r4_4; uses math; var a:matrice; b,coef:vector; sx,sy,sxy,slogx,slogy,s2x,s2logx,slogxy:real; suma,ss,sxlogy,s1px,s1px2,sypx,x,y:real; xnegativ:boolean; ynegativ:boolean; xzero:boolean; c:char; putere,s:vector; i,j,k,l,n:integer; begin sx:=0; { suma valorilor x } sy:=0; { suma valorilor y } sxy:=0; { suma valorilor x*y } slogx:=0; { suma valorilor log x } slogy:=0; { suma valorilor log y } s2x:=0; { suma patratelor valorilor x } s2logx:=0; { suma patratelor valorilor log x } slogxy:=0; { suma produselor valorilor logx,logy } sxlogy:=0; { suma produselor x, logy }154

s1px:=0; { suma inverselor } s1px2:=0; { suma patratelor inverselor } sypx:=0; { suma rapoartelor y/x } k:=1; writeln; writeln('Prelucrarea datelor din fsierul reg.dat'); writeln; write('Numr observatii :'); read(n); assign(input,'reg.dat'); reset(input); for i:=1 to n do begin readln(x,y); xnegativ:=x 0) then slogxy:=slogxy+ln(x)*ln(y); end; close(input); writeln('---------------------------------------------'); writeln; writeln(' L liniar H - hiperbolic'); writeln(' P putere E - exponential'); writeln(' A polinomial');155

writeln; assign(input,'con'); reset(input); repeat if eoln then readln; read(c); writeln('S-a selectat ',c); until c in ['l','L','H','h','p','P','e','E','a','A']; close(input); repeat k:=1; suma:=0; if c in ['l','L'] then begin a[1,1]:=n; a[1,2]:=sx; a[2,1]:=sx; { incarca matricea sistemului } a[2,2]:=s2x; b[1]:=sy; b[2]:=sxy; { incarca termenul liber } lustab(2,a,b); { descompunere lu } if succes then begin lusistab(2,a,b,coef) ; { rezolva sistem } assign(input,'reg.dat'); reset(input); for i:=1 to n do begin readln(x,y); suma:=suma+sqr(y-coef[1]-coef[2]*x) end; close(input) end else writeln('Erori mari in date.', 'Sistem ru condiionat'); end; if c in ['h','H'] then if xzero then writeln ('Modelul nu se aplica') else begin a[1,1]:=n; a[1,2]:=s1px; a[2,1]:=s1px; a[2,2]:=s1px2 ; b[1]:=sy; b[2]:=sypx; lustab(2,a,b); if succes then begin lusistab(2,a,b,coef) ;156

assign(input,'reg.dat'); reset(input); for i:=1 to n do begin readln(x,y); suma:=suma+sqr(y-coef[1]-coef[2]/x) end; close(input); end else begin suma:=-1; writeln('Erori mari in date.', 'Sistem ru conditionat'); end; end; if c in ['p','P'] then if xnegativ or ynegativ then writeln('Modelul nu se aplica') else begin a[1,1]:=n; a[1,2]:=slogx; a[2,1]:=slogx; a[2,2]:=s2logx ; b[1]:=slogy; b[2]:=slogxy; lustab(2,a,b); if succes then begin lusistab(2,a,b,coef) ; coef[1]:=exp(coef[1]); assign(input,'reg.dat'); reset(input); for i:=1 to n do begin readln(x,y); suma:=suma+sqr(y-coef[1]*exp(coef[2]*ln(x))) end; close(input); end else begin suma:=-1; writeln('Erori mari n date.', 'Sistem ru condiionat'); end; end; if c in ['e','E'] then if ynegativ then writeln('Modelul nu se aplica') else begin157

a[1,1]:=n; a[1,2]:=sx; a[2,1]:=sx; a[2,2]:=s2x ; b[1]:=slogy; b[2]:=sxlogy; lustab(2,a,b); if succes then begin lusistab(2,a,b,coef) ; coef[1]:=exp(coef[1]); coef[2]:=exp(coef[2]); if coef[2]eps; while (i eps ; i:=i+1 end; end; {----------------------------------------------------} procedure lusistab(n:integer; a:matrice; var b,x:vector); { Apel: LUsistab(n,a,b,x,p); Descriere parametri:165

n - dimensiunea sistemului; a - matricea sistemului; b - termenul liber; x - soluia sistemului; p - permutarea rezultat prin interschimbri. Funcia: Rezolv sistemul LUx=b; Metoda: Se rezolv dou sisteme triunghiulare. } var i,j:integer; y:vector; s:real; begin { Rezolvare sistem inferior triunghiular; } y[1]:=b[1]; for i:=2 to n do begin s:=0; for j:=1 to i-1 do s:=s+a[i,j]*y[j]; y[i]:=b[i]-s end; writeln; { Rezolvare sistem superior triunghiular; } x[n]:=y[n]/a[n,n]; for i:=n-1 downto 1 do begin s:=0; for j:=i+1 to n do s:=s+a[i,j]*x[j]; x[i]:=(y[i]-s)/a[i,i] end end; {-----------------------------------------------------} procedure lltd(n:integer; var a:matrice); { Apel: LLtd(n,a); Descrierea parametrilor: n - dimensiunea matricei; a - matrice patratica cu elemente reale. Funcia:166

Obine n matricea A o descompunerea n produsul unei matrice inferior triunghiulare cu transpusa acesteia, dac matricea A este pozitiv definit. Metoda: Conform algoritmului prezentat la problema R4.2. } var i,j,k:integer; sim:boolean; begin pozdef:= true; i:=1; while (i = eps; if nenul then begin for j:=2 to n do begin a[j,1]:=a[j,1]/a[1,1]; a[1,j]:= a[j,1] end; i:=2; while (i 0; if pozdef then begin a[i,i]:=sqrt(a[i,i]); nenul := a[i,i] >= eps; if nenul then for j:=i+1 to n do begin for k:=1 to i-1 do a[j,i]:=a[j,i]-a[j,k]*a[i,k]; a[j,i]:=a[j,i]/a[i,i]; a[i,j]:=a[j,i] end end; i:=i+1 end end end end;167

{-----------------------------------------------------} procedure llsistem(n:integer;a:matrice; b:vector; var x:vector); { Apel: LLsistem(n,a,b,x); Descrierea parametrilor: n - dimensiunea sistemului; a - matricea ce conine descompunerea LLT b - termenul liber; x - soluia sistemului. Funcia: Rezolv dou sisteme triunghiulare conform celor prezentate la problema R4.2. } var i,j,k:integer; y:vector; begin y[1]:=b[1]/a[1,1]; for i:=2 to n do begin y[i]:=b[i]; for k:=1 to i-1 do y[i]:=y[i]-a[i,k]*y[k]; y[i]:=y[i]/a[i,i] end; x[n]:=y[n]/a[n,n]; for i:=n-1 downto 1 do begin x[i]:=y[i]; for j:=i+1 to n do x[i]:=x[i]-a[i,j]*x[j]; x[i]:=x[i]/a[i,i] end; end; {-----------------------------------------------------} function diag_dom(n:integer; a:matrice):boolean; { Apel : diag_dom(n,a); Descrierea parametrilor: n - dimensiunea matricei; a - matrice patratic cu elemente reale. Funcia: Verific dac o matrice este diagonal dominant } var i,j:integer; v:boolean; s:real;168

begin v:=true; i:=1; while (i = abs (a[i,i]) then v:=false else i:=i+1; end; diag_dom:=v end; {-----------------------------------------------------} function norma(n:integer; x:vector):real; { Apel : norma(n,x) Descrierea parametrilor: n - dimensiunea vectorului; x - vector cu n componente. Functia: Calculeaza norma uniform. } var v, p:real; i:integer; begin v:=abs(x[1]); for i:=2 to n do begin p:=abs(x[i]); if v < p then v:=p end; norma:=v end; {-----------------------------------------------------} procedure Iacobi(n:integer; a:matrice; b:vector; niter:integer; var x:vector); { Apel: Iacobi(n,a,b,niter,x) Descrierea parametrilor: n - dimensiunea sistemului; a - matricea sistemului; b - termenul liber; niter - numrul de iteraii; x - soluia sistemului. Functia: Rezolv un sistem cu n ecuaii liniare i n necunoscute prin metoda Iacobi. Metoda: Algoritmul prezentat la problema R4.3. } var i,j,k:integer; y,e:vector; s:real;169

begin for i:=1 to n do y[i]:=x[i]; k:=1; while ( k eps) do begin for i:=1 to n do begin s:=0; for j:=1 to n do if j i then s :=s+a[i,j]*y[j]; x[i]:=(b[i]-s)/a[i,i] end; vdif(n,x,y,e); for i:=1 to n do y[i]:=x[i]; k:=k+1 end end; {-----------------------------------------------------} procedure Seidel(n:integer; a:matrice; b:vector; niter:integer;var x:vector); { Apel : Seidel(n,a,b,niter,x) Descrierea parametrilor: n - dimensiunea sistemului liniar; a - matricea sistemului de ecuaii; b - termenul liber al sistemului; niter - numarul de iteraii ; x - soluia sistemului. Funcia: Rezolv un sistem liniar cu n ecuaii i n necunoscute prin metoda Gauss-Seidel. Metoda: Algoritmul prezentat la problema R4.3. } var y,e:vector;i,j,k:integer; begin for i:=1 to n do y[i]:=x[i]; k:=1; while (k eps) do begin for i:=1 to n do begin x[i]:=b[i]; for j:=1 to n do if i j then x[i]:=x[i]-a[i,j]*x[j]; x[i]:=x[i]/a[i,i]; end; vdif(n,x,y,e); for i:=1 to n do y[i]:=x[i]; k:=k+1 end end; begin Writeln; Writeln('Unitul Math - GA2003'); Writeln end.170

4.3. Probleme propuse 1. O bibliotec de grafic bidimensional, trebuie s ofere programatorului posibilitatea lucrului n coordonate utilizator (numere reale). Aceasta trebuie s conin subprograme pentru: realizarea transformrilor geometrice (translaie absolut i relativ, rotaie absolut i relativ, simetrie etc.); desenarea primitivelor grafice (linie, cerc, dreptunghi, elipsa etc.); realizarea transformrii imaginii din spaiul de coordonate utilizator n spaiul de coordonate ecran. operaia de decupare (clipping). S se realizeze o unitate numit Desenare.tpu care s utilizeze unitatea graph i care s ofere ct mai multe din facilitile anunate mai sus. 2. Se consider declaraiile: unit MatProg10; interface const max_lin=10; max_col=10; type matrice= array[1..max_lin,1..max_col] of real; vector_linie= array[1..max_col] of real; vector_coloana=array[1..max_lin] of real; procedure copy_lin_vector (a:matrice; i:integer; var x:vector_linie); procedure copy_col_vector (a:matrice; i:integer; var x:vector_coloana); procedure copy_diag_vector(a:matrice; var x:vector_coloana); procedure add_number(var a:matrice; x:real); procedure subtract_number(var a:matrice; x:real); procedure divide_by_number(var a:matrice; x:real); procedure replace_diag_vector(var a:matrice; x:vector_coloana); procedure mul_linie_add(var a:matrice; i:integer; x:real; j:integer); procedure mul_col_add(var a:matrice; i:integer; x:real; j:integer); procedure interschimba_lin(var a:matrice; i,j:integer); procedure interschimba_col(var a:matrice; i,j:integer); procedure sum_lin_vector(a:matrice; var x:vector_coloana); procedure sum_col_vector(a:matrice; var x:vector_linie); procedure generare(var a:matrice); procedure tiparire(a:matrice); a) S se implementeze unitatea conform urmtoarelor specificaii:171

Procedura copy_lin_vector copiaz linia i a matricei a ntr-un vector linie. Procedura copy_col_vector copiaz coloana i a matricei a ntr-un vector coloan. Procedura copy_diag scoate ntr-un vector elementele de pe diagonala matricei a. Procedura add_number adun un scalar la toate elementele matricei a. Procedura subtract_number scade un scalar din toate elementele matricei a. Procedura divide_by_number mparte toate elementele matricei a la un numr real nenul. Procedura replace_diag_vector nlocuiete elementele de pe diagonala matricei a cu cele specificate ntr-un vector coloan. Procedura mul_linie_add adun la linia j, linia i, ale crei elemente se nmulesc cu un numr real. Procedura mul_col_add adun la coloana j, coloana i, ale crie elemente se nmulesc cu un numr real. Procedura interschimba_lin realizeaz interschimbarea liniilor i i j. Procedura interschimba_col realizeaz interschimbarea coloanelor i i j. Procedura sum_lin_vector calculeaz ntr-un vector coloan suma elementelor de pe liniile matricei a. Procedura sum_col_vector calculeaz ntr-un vector linie suma elementelor de pe coloanele matricei a. Procedura generare realizeaz ncrcarea unei matrice a cu valori numerice. Procedura tiparire afieaz la mediul standard de ieire, valorile elementelor matricei a. b) S se utilizeze unitatea pentru implementarea unor algoritmi pentru calculul rangului unei matrice; 3. Elaborai o unitate de translatare Pascal pentru definirea tipului complex i a operaiilor cu numere complexe. Se cer utilizarea formei algebrice i a formei trigonometrice. 4. Elaborai o unitate pentru lucrul cu numere mari. Trebuie implementate operaii precum: adunare, scdere, mprire ntreag, determinarea restului mpririi a dou numere ntregi, calculul rdcinii ptrate.172

5. Introducere n programarea orientat obiect folosind limbajul C++5.1. Fundamente La prima vedere orice program poate fi perceput ca o colecie de date i de operaii care se execut asupra datelor. n programarea procedural aceste dou elemente sunt tratate separat, reprezentarea datelor se realizeaz cu ajutorul tipurilor de date, iar reprezentarea operaiilor se face prin funcii i proceduri. Folosirea funciilor nu este suficient dac se dorete o descriere i implementare eficient a unor algoritmi ce necesit structuri de date complexe n rezolvarea problemelor. n plus, dac se dorete reutilizarea unor programe scrise anterior n rezolvarea unor noi probleme va fi necesar un efort considerabil din partrea programatorului s adapteze codul surs reutilizat la noile nevoi, iar aceasta va duce la apariia a numeroase erori. Din acest motiv este mult ngreunat i lucrul n echip, dac un programator trebuie s implementeze o funcie, acesta va trebui s studieze i celelalte module ale programului. Un limbaj de programare potrivit acestor sarcini ar trebui s permit att ncapsularea structurilor de date ct i a funciilor care opereaz cu aceste structuri ca o singur entitate, s permit ascunderea detaliilor de implementare a operaiilor i s permit reutilizarea i extinderea unor module existente (chiar i a celor compilate fr recompilare). S-a impus astfel, nevoia unui model de programare capabil s depeasc limitrile programrii structurate i care s permit realizarea unei abstractizri adecvate a datelor i a operaiilor n aa fel nct s permit o tratare unitar a acestora. Aa s-a nscut clasa limbajelor de programare orientate pe obiecte din care face parte i limbajul C++. Modelul de programare orientat pe obiecte rezolv aceste probleme prin urmtoarele principii importante: abstractizare, ncapsulare, modularizare, motenire i polimorfism. Abstractizarea Abstractizarea este un model n care un obiect este privit prin prisma metodelor (operaiilor) sale, ignorndu-se pentru moment detaliile de implementare a acestora. O bun abstractizare va defini n mod clar graniele conceptuale ale obiectului, va scoate n eviden doar173

aspectele semnificative ale obiectului, acelea care fac ca acesta s se diferenieze de alte obiecte i va estompa celelalte caracteristici. Aadar, n procesul de abstractizare atenia este ndreptat spre aspectul exterior al unui obiect, spre modul su de comportare i nu spre felul n care aceast comportare este implementat. Comportarea unui obiect se caracterizeaz printr-un numr de servicii sau resurse pe care acesta le pune la dispoziia altor obiecte. Mulimea operaiilor unui obiect mpreun cu regulile lor de apelare constituie interfaa obiectului. Programatorii utilizeaz abstractizarea pentru a simplifica analiza, proiectarea i implementarea programelor complexe. n C++ instrumentul de baz pentru abstractizare este clasa. ncapsularea ncapsularea este conceptul complementar abstractizrii. Dac rezultatul operaiei de abstractizare pentru un anumit obiect este identificarea interfeei, atunci ncapsularea trebuie s defineasc reprezentarea (structura) intern a obiectului i s selecteze o implementare a interfeei acestuia. Prin urmare, ncapsularea este procesul n care are loc separarea interfeei de implementare i ascunderea implementrii fa de exterior. Separarea interfeei de reprezentarea unui obiect i de implementarea metodelor sale permite modificarea structurii obiectului i a metodelor fr a afecta n nici un fel programul care folosete obiectul, ntruct acesta depinde doar de interfa. ncapsularea permite modificarea programelor ntr-o manier eficient, cu un efort limitat i bine localizat. Modularizarea Clasele obinute n urma abstractizrii i ncapsulrii trebuie grupate i apoi stocate ntr-o form fizic, denumit modul. Modulele pot fi privite ca fiind containerele fizice n care declarm clasele i obiectele rezultate n urma proiectrii la nivel logic. Modulele formeaz aadar arhitectura fizic a programului. Modularizarea const n divizarea programului ntr-un numr de module care vor fi compilate separat, dar care sunt conectate ntre ele. Scopul descompunerii n module este reducerea costurilor prin posibilitatea de a proiecta i revizui pri ale programului ntr-un mod independent. Concret, n C++ modulele nu sunt altceva dect fiierele ce pot fi compilate separat. n practic se obinuiete ca interfaa unui modul174

s fie plasat ntr-un fiier header (cu extensia ".h"), n timp ce implementarea acestuia se va regsi ntr-un fiier surs (cu extensia ".cpp"). Dependenele dintre module vor fi exprimate utliznd directivele "#include". Referitor la modularizare, cititorul poate observa asemnri i deosebiri ale modularizrii la nivelul C, C++, n raport cu modularizarea permis de implementarea Borland a limbajului Pascal. Motenirea Nu de puine ori, scriind programe n maniera clasic, eram pui n situaia de a adapta sau rescrie funcii scrise anterior. Aceast etap de implementare consuma mai mult timp dect era necesar i, n plus, exista riscul apariiei a numeroase erori. O variant mult mbuntit de reutilizare a codului este motenirea. Motenirea este unul dintre cele mai importante concepte ale limbajelor de programare pe obiecte. Aceasta permite extinderea obiectelor existente i construirea de noi obiecte ntr-un mod simplu. Astfel, o clas poate moteni toate caracteristicile uneia sau a mai multor clase create anterior la care poate aduga trsturi noi i, n anumite condiii, poate redefini unele din metodele motenite. Polimorfismul Polimorfismul este o facilitate a programrii orientate obiect care ofer instanelor unor clase posibilitatea de a reaciona ntr-un mod specific la un mesaj (la un apel de funcie). Spre exemplu, ntr-o ierarhie de clase obinut prin motenire, care reprezint forme geometrice (puncte, linii, dreptunghiuri, cercuri) fiecare obiect are o funcie Draw(). Apelul acestei funcii avnd o referin la un obiect grafic generic trebuie s se comporte corespunztor obiectului referit. Clasele Conceptul fundamental din programarea orientat pe obiecte l reprezint noiunea de clas ca tip de date definit de utilizator. Cuvntul cheie class ne permite s intrm n universul programrii orientate pe obiecte, cu ajutorul lui putem defini tipuri abstracte de date. Variabilele declarate pe baza unui tip abstract se numesc obiecte. Putem spune c: Clasa = Date + Operaii. Spre deosebire de structurile cunoscute din limbajul C, clasele conin nu numai date membre ci i funcii membre, constructori i cel mult un destructor. n general o clas se definete astfel:175

class nume{ private: protected: public: }; Pentru exemplificare vom defini o serie de clase pentru reprezentarea figurilor geometrice n plan. Se tie c figurile geometrice se contruiesc pornind de la unele forme simple cum sunt punctul, linia, etc. Urmeaz un exemplu de declaraie de clas care introduce un tip nou de date numit Punct. Urmtoarea declaraie se va scrie ntr-un fiier header cu un numele Point.h. class Point { protected: int x, y; //date membre public: Point(); //constructor Point(int, int); //consructor ~Point(); //destructor void Print(); //funcie membra void Read(); //funcie membra }; Operaii cu fluxuri standard n limbajul C toate operaiile de intrare-ieire se realizeaz prin utilizarea funciilor din biblioteca standard stdio. C++ vine cu o nou bibliotec de I/O numit iostream. Biblioteca nu conine o colecie de funcii ci o colecie de obiecte care permit accesul la ecran pentru afiare i la tastatur pentru citirea datelor introduse de utilizator. Aceste obiecte au definite cte o metod pentru lucrul cu fiecare tip de date simple (int, long, float, double, char), eliminnd astfel176

necesitatea precizrii tipului i a formatului datelor care urmeaz a fi scrise sau citite. Cnd un program C++ care include headerul iostream.h este lansat n execuie, atunci sunt create i iniializate automat urmtoarele patru obiecte: cin gestioneaz intrarea standard (tastatura); cout gestioneaz ieirea standard (ecranul); cerr gestioneaz ieirea ctre dispozitivul standard de eroare (ecranul), neutiliznd bufere; clog gestioneaz ieirea ctre dispozitivul standard de eroare (ecranul), utiliznd bufere. Cnd este vorba se operaii de intrare/ieire trebuie s avem n vedere o surs emitent a unui flux de date i o destinaie care recepioneaz aceste date. n afar de aceastea avem nevoie i de un mijloc de comunicare ntre surs i destinaie. Aici intervin operatorii. S vedem, n continuare, cum se face afiarea i citirea tipurilor de date standard n limbajul C++ folosind obiectele de mai sus. n limbajul C Int x = 33; float f = 1.5; Printf("x = %d f = %f", x, f); Printf("\n"); Printf("%c", 'C'); Printf("%s", "Limbajul C\n"); Int x; scanf("%d", &x); Float f; scanf("%f" &f); Char ch; scanf("%c", &ch); Char sir[25]; scanf("%s", sir); n limbajul C++ int x = 33; float f = 1.5; cout