Pentru a descarca referate trebuie sa fii membru eCursuri.ro
Intra in contul tau sau inregistreaza-te GRATUIT (dreapta sus)
68 de pagini de probleme rezolvate si teorie in Pascal
Culegerea de probleme de fata se doreste a fi un ghid sio colectie de probleme pentru învatarea programarii. Diversitatea problemelor propuse si gradul diferit de dificultate fac culegerea utila nu numai studentilor, ci si elevilor de liceu. Initial ea a fost conceputa ca ghid pentru lucrarile de laborator ale studentilor anilor întâi si doi de la sectia de Informatica a Facultatii de Matematica si Informatica.
Problemele sunt grupate în 16 capitole, în functie de specificul si gradul lor de complexitate. Succesiunea capitolelor din culegere vizeaza o abordare graduala a problematicii, atât din punctul de vedere al complexitatii algoritmilor, specificati în limbaj Pseudocod, cât si al învatarii unui limbaj de programare, în particular limbajul Pascal. Fiecare capitol contine cel putin doua exemple de probleme rezolvate, pentru care sunt precizati atât algoritmii de rezolvare, cât si programele sursa Pascal. Intentia autorilor este de a sugera un anumit stil de rezolvare a problemelor cu calculatorul, acordându-se o importanta deosebita etapelor de analiza a problemei si de proiectare a algoritmilor, etape în care limbajul de programare nu este implicat. Din acest punct de vedere, problemele propuse sunt generale, implementarea solutiilor putând fi facuta si în alte limbaje de programare.
Problemele de acelasi tip sunt grupate în acelasi capitol, iar un capitol acopera toata gama de probleme pentru tema abordata. Astfel, capitolul I contine probleme elementare, a caror rezolvare nu cere folosirea vectorilor sau a matricelor. Capitolul doi contine probleme referitoare la vectori, în timp ce capitolul trei contine probleme a caror rezolvare cere folosirea vectorilor. Capitolul patru contine probleme cu matrice. Capitolul cinci cere folosirea subalgoritmilor. Capitolul sase contine probleme a caror rezolvare cere folosirea matricelor. Urmeaza un capitol de exemple si probleme pentru programarea în limbaj masina. Capitolul opt contine probleme referitoare la tipurile multime si enumerare din Pascal. Capitolul noua contine probleme referitoare la siruri de caractere. Capitolul zece se refera la recursivitate. Urmeaza un capitol de probleme privind folosirea fisierelor. Capitolul 12 contine probleme care cer folosirea tipului referinta în Pascal. Urmatorul capitol contine probleme de grafica cu calculatorul. Capitolul 14 contine mai multe probleme date la diferite concursuri de programare. Tipurile abstracte de date sunt obiectul capitolului 15. În sfârsit, ultimul capitol contine probleme despre grafe.
Desi la selectarea problemelor au contribuit toti autorii, fiecare capitol a fost elaborat de unul sau doi autori, dupa cum urmeaza:
Cap.1-Prof. S.Groze si Prof. M.Frentiu;
Cap.2-Prof. M.Frentiu;
Cap.3-Lect. Robu J. si Prof. M.Frentiu;
Cap.4-Asist. S. Motogna;
Cap.5-Asist. E.Iacob;
Cap.6-Conf. Kasa Z. si Asist. S.Motogna;
Cap.7-Conf. F.Boian;
Cap.8-Lect. V.Ciobanu;
Cap.9-Asist. S.Iurian;
Cap.10-Asist. S.Iurian;
Cap.11-Asist. H.Pop;
Cap.12-Lect. V.Prejmereanu;
Cap.13-Lect. V.Prejmereanu;
Cap.14-Asist. S.Motogna;
Cap.15-Conf. B.P?rv si Prof. M.Frentiu;
Cap.16-Conf. T.Toadere.
Eventualele erori nu se pot imputa numai celor de mai sus, toti autorii participând la corectarea finala a acestei culegeri.
Speram ca prezentul material sa-si atinga scopul propus, cel de dezvoltare la cititori a gustului de programare într-un limbaj evoluat, în particular în limbajul Pascal.
Constienti ca exista posibilitati de îmbunatatire a continutului prezentei lucrari, autorii multumesc anticipat pe aceasta cale tuturor celor care vor face observatii si propuneri de îmbunatatire, de care se va tine seama la o noua editare a culegerii de probleme.
CAPITOLUL 1
PROBLEME SIMPLE
1.1.GHID DE LUCRU
Rezolvarea unei probleme cu ajutorul calculatorului presupune parcurgerea urmatoarelor faze:
precizarea completa a problemei de rezolvat;
proiectarea algoritmului de rezolvare a problemei;
programarea propriu zisa (implementarea);
testarea programului obtinut;
exploatarea si întretinerea programului.
Aceste faze constituie ciclul de viata al programului.
De foarte multe ori, atunci când beneficiarul discuta cu executantul despre problema care trebuie rezolvata, acesta da un enunt vag, incomplet, daca nu chiar inexact sau contradictoriu, pentru problema de rezolvat. Urmeaza mai multe discutii, uneori întinse în timp, în urma carora se ajunge la un enunt relativ complet si exact al problemei. Întrucât problemele propuse sunt luate din domeniul matematicii sarcina noastra va fi mult mai usoara.
Dupa enuntarea problemei urmeaza modelarea matematica si cautarea unei metode de rezolvare a ei. Uneori sunt posibile mai multe moduri de rezolvare, caz în care se va alege metoda considerata cea mai potrivita scopului urmarit. Modelarea matematica si alegerea unei metode de rezolvare se îmbina aproape întotdeauna cu conceperea algoritmului, fiind greu sa se separe una de cealalta. Activitatile de mai sus constituie ceea ce numim proiectarea programului.
Pe toata durata proiectarii trebuie mentionate în scris toate deciziile luate, întrucât este posibil ca ulterior sa fie necesara o reproiectare si deci, sa se revina asupra acestor decizii. Documentatia realizata este necesara în primul rând pentru urmatoarea faza a ciclului de viata al programului, implementarea. De asemenea, în faza de întretinere a programului este posibila modificarea unor module, modificare în care sunt necesare sa fie cunoscute si aceste decizii. E bine ca proiectarea sa fie astfel facuta încât sa permita o întretinere cât mai usoara. Faza urmatoare, implementarea sau codificarea, consta în traducerea algoritmului într un limbaj de programare. Evident, prima decizie ce trebuie luata consta în alegerea limbajului de programare în care va fi scris programul. În cele ce urmeaza vom folosi în acest scop limbajul Pascal. De multe ori se vor folosi mai multe limbaje pentru aceasta activitate. De exemplu, pot exista unele module a caror scriere se poate face numai în limbajul de asamblare. Urmeaza testarea programului elaborat, care uneori pune în evidenta erori grave de programare, erori care au dus în unele situatii la refacerea (partiala sau integrala) a activitatilor anterioare. Sigur ca este de dorit sa nu se ajunga la astfel de situatii si, daca proiectarea si implementarea au fost facute corect, în faza de testare nu ar trebui sa întâlnim erori.
Urmatoarea faza din viata programului consta în exploatarea propriu-zisa a acestuia, faza în care executia se face cu date reale. Aceasta activitate se întinde în timp pe mai multi ani si cere adeseori schimbari în program, motiv pentru care este cunoscuta sub numele de întretinerea programului. Este faza cea mai costisitoare si cea mai importanta din viata unui produsul real. Toata activitatea de realizare a programului trebuie sa tina seama de acest fapt si programul sa fie astfel conceput încât sa se permita modificari în ceea ce face programul cu un numar minim de modificari în textul acestuia. Documentarea programului presupune elaborarea unor materiale scrise în care se precizeaza toate informatiile utile despre programul realizat. Pentru proiectarea algoritmilor vom folosi limbajul Pseudocod. Avantajele folosirii acestui limbaj pentru proiectarea algoritmilor constau în faptul ca permit programatorului sa-si îndrepte complet atentia asupra logicii rezolvarii problemei si sa uite de restrictiile impuse de limbajul de programare si calculatorul folosit. În aceasta faza este necesara o analiza atenta a problemei în vederea gasirii unui algoritm corect proiectat.
De asemenea, proiectarea algoritmului permite evitarea duplicarii unui grup de instructiuni în mai multe parti ale programului. Identificarea unui astfel de grup permite definirea lui ca un singur subalgoritm si folosirea acestui subalgoritm ori de câte ori este necesar.
În descrierea unui algoritm deosebim urmatoarele activitati importante:
specificarea problemei;
descrierea metodei alese pentru rezolvarea problemei;
precizarea denumirilor si semnificatiilor variabilelor folosite;
descrierea algoritmului propriu-zis.
Astfel, daca ni se cere sa calculam radicalul de ordinul 2 din x, în partea de specificare a problemei vom mentiona:
Se da un numar real nenegativ, notat prin x.
Se cere sa gasim un alt numar pozitiv r astfel încât r2=x.
Pentru un informatician este clar ca un astfel de numar nu se poate gasi în general prin nici un procedeu finit. Este însa posibil sa gasim o aproximare oricât de buna a lui r. Deci specificarea facuta nu este corecta, neputând gasi un algoritm care sa rezolve problema în forma enuntata. Vom modifica aceasta specificatie, cerând sa se calculeze aproximativ r cu o eroare ce nu depaseste un numar real eps oricât de mic.
Pentru a descarca referate trebuie sa fii membru eCursuri.ro
Intra in contul tau sau inregistreaza-te GRATUIT (dreapta sus)
