Tehnici de Program Are An1 - Sem2

download Tehnici de Program Are An1 - Sem2

of 224

  • date post

    19-Jun-2015
  • Category

    Documents

  • view

    6.010
  • download

    3

Embed Size (px)

Transcript of Tehnici de Program Are An1 - Sem2

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