REZOLVAREA UNOR PROBLEME REMARCABILE IN TURBO PASCAL

Liceul teoretic 'Alexandru Ioan Cuza'

Alexandria

PRODUS SOFT PENTRU SUSTINEREA ATESTATULULI LA IMFORMATICA

REZOLVAREA UNOR PROBLEME REMARCABILE IN TURBO PASCAL

PASCAL este unul dintre limbajele de programare de referinta in stiinta calculatoarelor, fiind cel care a definit programarea calculatoarelor. Pascal a fost dezvoltat de elvetianul Niklaus Wirth in 1970 pentru a pune in practica programare structurat, aceasta fiind mai usor de compilat. Unul din marile sale avantaje este asemanarea cu limbajul natural limba engleza, ceea ce il face limbajul ideal pentru cei care sunt la primul contact cu programarea. Pascal este bazat pe limbajul Algol si a fost denumit astfel in onoarea matematicianului Blaise Pascal, creditat pentru construirea primelor masini de calcul numeric. Wirth a mai dezvoltat limbajele Modula-2 si Oberon, similare cu Pascal, care suporta si programarea orientat pe obiecte.

Cele mai populare implementari a acestui limbaj au fost Turbo Pascal si Borland Pascal, ambele ale firmei Borland cu versiuni pentru Macintosh si DOS, care i-au adaugat limbajului obiecte si au fost continuate cu versiuni destinate programarii vizuale pentru Microsoft Windowslimbajul Delphi limbaj de programare|Delphi si Linux Kylix.

In prezent exista si alte implementari mai mult sau mai putin populare, dar gratuite, printre care se remarca Free Pascal si GNU Pascal.

Un limbaj de programare este un limbaj artificial care prin exprimari simbolice descrie operatiile de prelucrare automata a datelor, necesare pentru rezolvarea unei anumite probleme a utilizatorului.

Calculatorul manipuleaza informatia sub forma binara. El nu intelege decat comenzi date in binar. Codul in care sunt scrise aceste comenzi este codul binar, iar limbajul este limbajul masina. Se numeste asa pentru ca este un limbaj al masinii, al procesorului. Este specific fiecarui tip de masina deoarece setul de instructiuni pe care le intelege calculatorul trebuie sa se regaseasca sub forma de circuite electronice in procesor. Pentru om este foarte greu sa urmareasca un program scris in limbajul masina, program care este un sir de cifre binare din aceasta cauza au fost create limbajele de programare de nivel inalt. Ele sunt mai apropiate de limbajul uman si sunt in general portabile, adica, cu foarte mici modificari, un program scris intr-un astfel de limbaj va putea fi executat pe orice tip de calculator. O instructiune dintr-un limbaj de nivel inalt codifica un grup de instructiuni masina. Limbajele de programare de nivel inalt se mai numesc si limbaje algoritmice deoarece descriu algoritmul de rezolvare a problemei sub forma unei secvente de instructiuni care se vor executa in ordinea in care au fost scrise. Limbajul Pascal este un limbaj de nuvel inalt.

Limbajele de nivel inalt nu sunt intelese de calculator deoarece acesta nu intelege decat instructiunile binare ale limbajului masinii. Instructiunile din limbajele de nivel inalt trebiue traduse in cod masina. Aceasta operatie se realizeaza cu ajutorul unor programe traducatoare. Acestea sunt de doua tipuri:

compilatoare, care traduc intreg programul pentru a-l putea transforma intr-un program care sa fie executat ori de cate ori este nevoie.

interpretoare, care traduc si executa pe rand fiecare instructiune.

Pentru a obtine un program executabil trebiue parcurs urmatorul drum:

Editarea programului. Cu ajutorul unui editor de texte se scrie programul de la tastatura pe un support de informatie, in limbajul de program ales. Operatia se numeste editarea programului, iar programul obtinut este program sursa. Programul sursa este ca un document pe care omul il intelege. Pentru calculator el este insa un text sscris intr-un limbaj necunocut.

Traducerea programului. In aceasta faza fiecare instructiune din programul sursa este tradusa intr-o secventa de instructiuni in cod masina care pot fi executate de calculator, obtinandu-se modulele obiect. Operatia se executa sub controlul unui program numit compilator. Fiecare limbaj de programare are propriul program traducator. Exista astfel compilator Pascal, compilator C etc. Operatia se numeste compilare si programul obtinut se numeste program obiect. Daca programul compilator detecteaza o eroare sintactica el va afisa un mesaj de eroare pe ecran. In acest caz, autorul programului poate sa modifica fisierul sursa folosind programul editor, dupa care va compila din nou programul. Operatiile de modificare cu editorul si de tastare cu compilatorul se vor executa pana cand compilatorul nu va mai detecta erori. Atunci cand compilatorul nu mai gaseste erori in programul sursa, inseamna ca traducerea s-a facut corect si rezultatul traducerii poate fi depus intr-un fisier. Programul obiect obtinut nu este un program executabil deoarece modulele obiect sunt asemanatoare pieselor "puzzle": sunt fragmente care necesita sa fie ansamblate pentru a forma o imagine unitara.

Editarea legaturilor. Modulele obiect sunt legate unele de altele astfel incat sa se obtina un program executabil. Operatia se numeste editare de legaturi (link edit) si este executata de catre un program numit editor de legaturi (linkage editor). Pentru a obtine programul executabil pot fi legate module obiect care exista deja in bibliotecile sistemului.

Incarcarea si lansarea in executie. Programul executabil poate fi incarcat in memoria interna si lansat in executie pentru a produce efectele pentru care a fost creat. In timpul executarii programului pot sa apara erori semantice. Aceste erori vor duce la oprirea programului. In acest caz, autorul programului va depista eroarea si va modifica fisierul sursa cu programul editor, dupa care va compila din nou programul si va edita legaturile.

Testarea si depanarea programului. Programul executabil poate fi testat. Testarea se face prin executarea repetata a programului cu seturi de date de intrare diferite. In timpul testarii se poate afla daca exista erori de conceptie sau erori logice sau daca rezultatele obtinute nu au aspectul grafic dorit. Pentru remedierea acestor erori trebuie corectat programul sursa cu ajutorul editorului, compiat din nou cu ajutorul compilatorului, editate legaturile si reluat testul.

Operatia de corectare a eorilor se numeste depanarea programului. Ea se poate desfasura sub controlul unui program specializat numit depanator de programe care ajuta la detectarea instructiunii eronate. Operatia de depanare se executa mai usor daca limbajul este dotat si cu inerpretor. In acest caz se va executa repetat programul obiect fara sa se mai reia de fiecare data si operatia de editare a legaturilor.

Toate aceste operatii pot fi asigurate de diferite programe: editor de texte, compilator, editor de legaturi, program depanator. Atunci cand se realizeaza un program executabil, se parcurg operatiile de editare, compilare, lansare in executie si testare de mai multe ori. Aceasta inseamna ca trebuie incarcate in memorie si lansate in executie de mai multe ori programele editor, interpretor si depanator sau editor, compilator, editor de legaturi si depanator. Pentru a usura munca programatorului, aeste programe pot fi organizate intr-un pachet de programe care asigura prin intermediul unei interfete toate aceste operatii:

editarea programului sursa

compilarea programului sursa

editarea legaturilor programului obiect

lansarea in executie a programului executabil

depanarea interactive a programului

memorarea programului executabil pe un support de informatie.

Aceasta intefata se numeste mediu de programare. Aceeasi interfata poate sa contina ambele forme ale limbajului: forma cu compilator si forma cu interpretor (cum este si cazul mediului de programare Turbo Pascal).

Tehnica de elaborare a algoritmilor GREEDY

Sa consideram o multime A cu n elemente. Se cere o submultime a sa cu m <= n elemente (in cazul m=n este importanta ordinea alegerii elementelor), astfel incat sa fie indeplinite anumite conditii (acestea difera de la o problema la alta).

EX : Se considera o multime de n numere reale. Se cere o submultime a sa, astfel incat suma elementelor sale sa fie maxima.

Pentru rezolvare, vom alege un prim element al multimii de numere reale. Daca este posibil, acesta va fi adaugat solutiei, initial vide. Posibilitatea ca acesta sa fie adaugat este data de semnul numarului (acesta trebuie sa fie mai mare decat zero).

Se alege un al doilea numar, cu care se procedeaza in mod asemanator.

Algoritmul se incheie cand au fost alese si, eventual, adaugate toate elementele multimii.

Pentru a rezolva o problema cu GREEDY, solutia se construieste dupa algoritmul de mai jos :

Pentru fiecare element care urmeaza sa fie adaugat solutie finale se efectueaza o alegere a sa din elementele multimii A (dupa un mecanism specific fiecarei probleme in parte), iar daca este posibil, acesta este adaugat. Algoritmul se termina fie cand a fost gasita solutia ceruta, fie cand s-a constatat inexistenta acesteita.

Intuitiv, alegem un element, al doilea, al treilea...pana cand obtinem ce dorim sau pana cand au fost testate toate elementele multimii. De aici provine numele metodei ( greedy = lacom).

EXEMPLU :

O persoana are un rucsac cu ajutorul caruia poate transporta o greutate maxima G. Persoana are la dispozitie n obiecte si cunoaste ptnetru fieare obiect greutatea si castigul care se obtine in urma transportului sau la destinatie. Se cere sa se precizeze ce obiecte trebuie sa transporte persoana respectiva in asa fel incat castigul sa fie maxim.

Algoritmul este urmatorul :

Se calculeaza, pentru fiecare obiect in parte, eficienta de transport rezultata prin impartirea castigului la greutate ( de fapt, aceasta reprezinta castigul obtinut prin transportul unitatii de greutate) ;

Obiectele se sorteaza in ordine descrescatoare a eficientei de transport si se preiau in calcul in aceasta ordine ;

Castigul initial va fi 0 iar gerutatea ramasa de incarcat va fi G ;

Atata timp cat nu a fost completata greutatea maxima a rucsacului si nu au fost luate in considerare toate obiectele, se procedeaza astfel :

dintre obiectele ineincarcate se selecteaza acela cu cea mai ridicata eficienta de transport si avem doua posibilitati :

acesta incape in totalitate in rucsac, deci se scade din greutatea ramasa de incarcat greutatea obiectului, la castig se cumuleaza castigul datorat transportului acestui obiect, se tipareste 1, in sensul ca intregul obiect a fost incarcat ;

obiectul nu incape in totalitate in rucsac, caz in care se calculeaza ce parte din el poate fi transportata, se cumuleaza castigul obtinut cu transportul acestei parti din obiect, se tipareste procentul care s-a incarcat din obiect, iar greutatea ramasa de incarcat devine 0.

Dam un exemplu numeric. Greutatea care poate fi transportata cu ajutorul rucsacului este 3. avem la dispozitie 3 obiecte. Greutatea si castigul pentru fiecare obiect sunt prezentate mai jos :

Eficienta unui transport este 1 in cazul primului obiect, 4 pentru al doilea si 2 pentru al treilea. In concluzie, obiectul 2 se incarca in intregime in rucsac, obtinand un castig de 4 si ramane o capacitate de transport de 2 unitati de greutate. Se incarca 2/3 din obiectul 3 ( care este al doilea in ordinea descrescatoare a eficientei de transport) pentru care se obtine castigul 4. castigul total obtinut este 8.

Program rucsac ;

Type vector=array [1..9] of real ;

Var c, g, ef: vector:

n, i, man1: integer;

gv, man, castig: real;

inv: Boolean;

ordine: array [1..9] of integer;

begin

write('Greutatea ce poate fi transportata = '); readln(gv);

write('Numarul de obiecte = '); readln (n);

for i:= 1 to n do

begin

write('c[',I,']='); readln(c[i]);

write('g[',I,']='); readln(g[i]);

ordine[i]:=I;

ef[i]:=c[i]/g[i];

end;

repeat

inv:=false;

for i:=1 to n-1 do if ef[i]<ef[i+1]

then

begin

man:=ef[i]; ef[i]:=ef[i+1]; ef[i+1]:man;

man:=c[i]; c[i]:=c[i+1]; c[i+1]:=man;

man:=g[i]; g[i]:=g[i+1]; g[i+1]:=man;

inv:=true;

man1:=ordine[i]; ordine[i]:=ordine[i+1]; ordine[i+1]:=man1;

end

until not inv;

castig

i

while (gv>0) and (i<=n) do

begin

if gv>g[i] then

begin

writeln('Obiectul ', ordine[i], ' ',1);

gv:=gv-g[i];

castig:=castig + c[i];

end;

else

begin

writeln('Obiectul ', ordine[i], ' ', gv/g[i]:1:2);

castig:=castig + c[i]*gv/g[i];

gv:=0;

end;

i:=i+1;

end;

writeln('Castig total = ', castig:2:3);

end