Limbajul Pasacal

Limbajul Pasacal

Limbajele de programare reprezinta unul din principalele mijloace de comunicare om-masina, evolutia lor fiind nemijlocit legata de cea a calculatoarelor electronice, a caror era incepe in 1944. Primele calculatoare puteau fi programate numai in limbaj masina, dar, chiar la inceputul anilor '50, se inregistreaza trecerea la programarea simbolica, prin aparitia limbajelor de asamblare caracterizate prin folosirea codurilor mnemonice pentru instructiuni si a adresarii simbolice a operanzilor. Dupa aparitia primului limbaj de nivel inalt, limbajul FORTRAN (1954), se observa o proliferare accelerata a limbajelor de programare. Intr-o lista considerata exhaustiva la data respectiva (1969), J.E. Sammet identifica 120 de limbaje de programare cu o larga utilizare; trei ani mai tarziu, acelasi autor extindea aceasta lista la 170 [Dodescu et al., 1987]. In primii ani ai deceniului opt, un sondaj efectuat in S.U.A. identifica, la nivelul unui singur domeniu de activitate - sistemele informatice ale armatei americane - utilizarea a peste 450 de limbaje de programare sau dialecte ale unor limbaje.

Din acest adevarat 'turn al lui Babel', prin perspectiva prezentei lucrari, un interes aparte prezinta limbajele procedurale, destinate descrierii algoritmilor de rezolvare a problemelor, sub forma unor succesiuni de instructiuni. Ele mai sunt numite limbaje algoritmice sau limbaje universale, nefiind limitate la o clasa particulara de probleme. Dintre cele mai cunoscute limbaje de programare incluse uzual in aceasta clasa pot fi mentionate: ADA, ALGOL, BASIC, C, COBOL, FORTRAN, PASCAL , PL/1 etc.

Aparitia limbajului Pascal este un rezultat al conceptelor dezvoltate ca urmare a crizei programarii ce caracteriza domeniul programarii calculatoarelor la sfarsitul anilor '60. In aceasta perioada, raspandirea pe plan mondial a prelucrarii automate a datelor a cunoscut o extindere remarcabila, trecandu-se la abordarea si rezolvarea unor probleme din ce in ce mai complexe. Programele mari asociate acestor probleme s-au complicat in asa masura incat au devenit foarte greu accesibile, chiar si pentru autorii lor. Intelegerea, depanarea si dezvoltarea unor astfel de programe prezinta dificultati majore. Limitarile limbajelor de programare cu larga utilizare in epoca (FORTRAN, COBOL etc.), dublata de inexistenta unor principii clare, care sa impuna o disciplina a programarii, au favorizat in mare masura programarea empirica. Ca raspuns la cerinta de elaborare a unei metodologii generale de dezvoltare sistematica a programelor s-a cristalizat metoda proiectarii si programarii structurate.

Un program structurat este constituit din unitati functionale bine conturate, ierarhizate conform naturii intrinseci a problemei. In interiorul unor astfel de unitati, structura se manifesta atat la nivelul actiunilor (instructiunilor), cat si al datelor.

Programarea structurata este o metoda independenta de limbajul de programare, actionand la nivelul stilului de lucru. Totusi, practica a demonstrat ca limbajul de programare poate inlesni in mod hotarator realizarea desideratelor evidentiate. Limbajul Pascal reprezinta un exemplu edificator in acest sens. El a aparut intr-o forma preliminara in 1968, autorul sau fiind profesorul elvetian Niklaus Wirth. Numele limbajului a fost ales ca un omagiu adus marelui matematician, fizician, filosof si scriitor francez Blaise Pascal (1623-1662), primul care, in 1642, a inventat o masina de calcul. Dupa o faza de dezvoltare extensiva, un prim compilator devine operational in 1970, limbajul fiind publicat in 1971. Interesul trezit de aparitia sa a condus la necesitatea unor consolidari ale limbajului, finalizate prin publicarea in 1973 a unui raport revizuit, in care se realizeaza o definire a formei de referinta numita Pascal Standard, redactata ulterior conform normelor ISO si devenita baza comuna pentru diverse implementari.

Limbajul Pascal include conceptele programarii structurate in ambele laturi ale efortului de abstractizare presupus de realizarea unui program - organizarea datelor si conceperea actiunilor. Printre principalele caracteristici ale lui pot fi mentionate:

. Include o serie de instructiuni care reprezinta chiar structurile de control impuse de tehnica programarii structurate (IF-THEN-ELSE, CASE, REPEAT, WHILE, FOR).

. Are facilitati puternice si deosebit de flexibile pentru reprezentarea datelor. Notiunea de tip de date a fost extinsa dincolo de cercul restrans al datelor intregi, reale, siruri de caractere si tablouri (masive). S-au introdus structuri de date complexe, ca articolul (inregistrarea), multimea, fisierul si posibilitati de a descrie altele noi, combinandu-le pe cele existente. La acestea se adauga facili-tatea de a defini si manipula structuri dinamice (liste liniare, arbori etc.). In anumite implementari ale limbajului a fost introdus tipul obiect, care permite reunirea in aceeasi constructie a datelor si metodelor care le prelucreaza (proceduri si functii), creand cadrul trecerii la programarea orientata obiect (POO).

. Ofera posibilitati de modularizare a programe-lor, prin structurarea lor in module carora le pot fi asociate constructii ale limbajului (proceduri si functii).

. Fundamenteaza constructiile pe conceptul de bloc, care permite, pe de o parte, definirea de date proprii (variabile locale) si, pe de alta parte, accesul la datele din blocurile de pe nivelurile superioare (variabile globale).

. Poseda o biblioteca bogata de functii si proceduri standard, cu elemente specifice diverselor implementari ale limbajului si permite, totodata, construirea de biblioteci ale utilizatorului.

Aceste caracteristici au facut ca, desi conceput initial pentru a servi ca suport de studiu al progra-marii structurate, limbajul sa fie folosit intens si de catre programatorii profesionisti. Ca efect, s-a ajuns rapid la o crestere spectaculoasa a productivi-tatii muncii de programare, ducand la raspandirea utilizarii limbajului.

Limbajul Pascal beneficiaza de implementari pe toate tipurile de sisteme de calcul. Multe dintre aceste implementari marcheaza si dezvoltari ale limbajului insusi, adica in raport cu care Pascal Standard apare ca un subset. Dintre variantele utilizate de informaticienii romani pot fi mentionate: implementarea pe calculatoarele din generatia a treia din familia FELIX, din 1978; Pascal Oregon pentru minicalculatoarele din familiile Independent si Coral; implementarile realizate de firma Borland International pentru microcalculatoarele IBM PC si compatibile.

Firma Borland a realizat, incepand cu 1983, medii integrate de dezvoltare (IDE - Integrated Development Environment) cu denumirile generice Turbo Pascal , Borland Pascal si Delphi. Turbo Pascal , ajuns la versiunea 7.0, a marcat introducerea progresiva a unor noi facilitati, dintre care cele mai semnificative sunt: realizarea segmentarii programelor folosind tehnica overlay, incepand cu versiunea 5.0 (1988); introducerea conceptelor POO, incepand cu versiunea 5.5 (1989); folosirea mouse-ului, ferestrelor de editare multiple, asamblorului integrat si sistemului Turbo Vision, pentru dezvoltarea de aplicatii orientate obiect, in versiunea 6.0 (1990).

Versiunile din categoria Turbo Pascal sunt destinate utilizarii sub DOS. Pentru dezvoltarea de aplicatii Windows a fost lansata implementarea Borland Pascal 7.0 pentru Windows, cu posibilitati superioare de utilizare a POO. Ultima realizare a firmei Borland o reprezinta Delphi, care implementeaza facilitati de POO si programare vizuala. Evolutia acestei implementari a cunoscut, de asemenea, doua etape: pentru sisteme pe 16 biti, specifice platformelor Windows 3.x, in versiunea Delphi 1.0; pentru sisteme pe 32 de biti (Windows 95, Windows NT), incepand cu Delphi 2.0.

Daca in cazul implementarilor pe 16 biti apare limitarea importanta a dimensiunii segmentelor de date si de cod la 64 KB (spatiul maxim de adrese care poate fi gestionat cu un cuvant de 16 biti), trecerea la cod pe 32 de biti face ca limitarile sa fie impuse numai de sistemul de operare (2 GB la Windows 95).

Grafuri neorientate

Notiuni introductive

Definitie:

Se numeste graf neorientat, o pereche ordonata de multimi notata G=(X,U), unde X= este o multime finite si nevida de elemnte numite noduri sau varfuri, iar U= este o multime de perechi neordonate de elemente din X numite muchii.

Asadar un neorientat poate fi reprezentat sub forma unei figure geometrice alcatuite din puncte(noduri,varfuri) si linii drepte sau curbe care unesc aceste puncte (muchii,arce).

Exemplu:

G=(X,U) X= U=

Pentru o muchie u_k=(x,y), vom spune ca :

varfurile x si y sunt adiacente si se numesc extremitatile muchiei u_k ;

muchia u_k si varful x sunt incidente in graf(la fel, muchia u_k si varful b);

muchia (x,y) este totuna cu (y,x) (nu exista o orientare a muchiei);

Doua muchii care au o extremitate comuna se numesc incidente.

Definitie:

Gradul unui varf x, notat d(x), reprezinta numarul muchiilor care trec prin nodul x (incidente cu nodul x).

Exemplu: d(1)=3, d(2)=2, d(4)=0, d(5)=1.

Un varf care are gradul 0 se numeste varf izolat(de exemplu varful 4).

Un varf care are gradul 1 se numeste varf terminal(de exemplu varful 5).

Propozitie:

Fie G=(X,U) un graf neorientat cu n noduri si m muchii, suma gradelor tuturor nodurilor este egala cu 2m.

Intr-un graf neorientat numarul nodurilor de grad impar este un numar par.

Se numeste graf partial al grafului G=(X,U) un graf neorientat G^'=(X,V), unde V X. Altfel spus, un graf G^' a lui G, este chiar G sau se obtine din G pastrand toate varfurile si suprimand niste muchii.

Se numeste subgraf al grafului G=(X,U) ungraf neorientat H=(Y,V), unde Y X iar V contine toate muchiile din U care au ambele extremitati in multimea Y.

Reprezentarea grafurilor neorientate

Cele mai cunoscute forme de reprezentare ale unui astfel de graf sunt: matricea de adiacenta, listele vecinilor si vectorul muchiilor.

Matricea de adiacenta

Este o matrice patratica cu n linii si n coloane, in care elementele a[i,j] se definesc astfel: a[i,j]=1 daca exista (i,j) in U, cu x diferit de y si 0 daca nu exista (i,j) in U.

Pentru graful G=(X,U) din figura de mai jos, matricea de adiacenta este:

linia

0 1 1 1 1

1 0 1 0 2

A= 1 1 0 1 3

1 0 1 0 4

coloana 1 2 3 4
a[i,j]=a[j,i] oricare ar fi i,j I

Proprietatile matricei de adiacenta:

Este o matrice simetrica;

Pe diagonala principala are toate elemntele egale cu 0;

Suma elementelor pe linia sau coloana i este egala cu gradul nodului i;

Daca elementele pe linia/coloana i sunt toate egale cu 0 atunci nodul este izolat;

Daca toate elementele din matrice,mai putin cele de pe diagonala principala, sunt 1 inseamna ca graful este complet.

Listele vecinilor

Pentru fiecare nod al grafului se retin nodurile adiacente cu el.

Pentru reprezentarea listei de adiacenta se poate folosi alocare dinamica.

Exemplu pentru matricea de adiacenta de mai sus:

nodul lista vecinilor

3, 4

3

2, 4

3

Vectorul muchiilor

Fiecare muchie a grafului poate fi privita ca o inregistrare cu doua componente: cele doua varfuri care constitue extremitatile muchiei. Notand aceste extremitati cu nod1 si nod2, putem defini tipul de date tmuchie, astfel:

type tmuchie=record

nod1,nod2:integer;

end;

Graful in ansamblul sau, este o multime de muchii, adica o multime de elemente de tipul tmuchie.In consecinta definim graful ca un "vector de muchii", adica un vector cu elementele de tipul tmuchie:

var v:array[1..25] of tmuchie;

Graf complet si graf bipartit.

Se numeste graf complet cu n varfuri, notat K_n, un graf G=(X,U) cu proprietatea ca intre oricare doua varfuri exista o muchie.

Exemplu:

Un graf complet cu n varfuri are n*(n-1)/2 muchii.

Un graf neorientat G=(X,U) se numeste bipartit daca exista 2 multimi de noduri A si B X astfel incat A B=X si A B= ; iar orice muchie din U are o extremitate in multimea A si una in multimea B.

Exemplu:

Fie G=(X,U) unde X=, U=

Cu multimile A= si B=

Se obesrva ca: A B=X, A B= , iar fiecare muchie are o extremitate in A si una in B.
Se numeste graf bibartit complet, un graf bipartit cu proprietatea ca pentru orice varf x din A si orice varf y din B, exista muchia(x,y) (unde A si B sunt cele doua submultimi care partitioneaza multimea varfurilorX).

Exemplu:

Notiunile de lant si ciclu

Se numeste lant in graful G, o succesiune de varfuri L=(x₁,x₂,...,x_p) ,cu x_i IX, in care ( ) 2 noduri consecutive din succesiune sunt adiacente, adica exista muchiile (x₁,x₂),(x₂,x₃),..,(x_p-1,x_p)IU.

Varfurile x₁ si x_p se numesc extremitatile lantului, iar numarul de muchii care intra in componenta sa reprezinta lungimea lantului.

Un lant in care ( ) 2 elemente sunt diferite se numeste lant elementar. Altfel lantul este neelementar.

Exemplu:

Lant elementar:1,2,3,4,5; 6,7,3,9,4,8.

Lant neelementar: 1,2,3,2;

Un graf G este conex, daca oricare ar fi doua varfuri ale sale , exista un lant care le leaga.

Se numeste ciclu intr-un graf, un lant in care extremitatile coincid si muchiile sunt diferite intre ele.

Exemplu: c₁=(3,4,5,3,7,6,1,2,3), c₂=(1,2,3,7,6,1), c₃=(3,5,4,9,3)

Daca intr-un ciclu, toate varfurile cu exceptia primului si a ultimului sunt distincte doua cate doua, atunci ciclul se numeste elementar. In caz contrar el este neelementar.

Ciclurile c₂ si c₃ din exemplul anterior sunt elementare,iar c₁ este neelementar(in c₁, varful 3 apare si ca varf "intermediar",adica traseul descris mai trece odata prin varful 3 pe langa faptul ca porneste din el si se intoarce tot in el.).

Grafuri hamiltoniene si euleriene.

Se numeste ciclu hamiltonian intr-un graf, un ciclu elementar care contine toate varfurile grafului.

Un graf care contine un ciclu hamiltonian se numeste graf hamiltonian.

Un lant elementar care contine toate varfurile grafului se numeste lant hamiltonian.

Un graf hamiltonian are cel putin trei varfuri.

Graful complet cu n varfuri este un graf hamiltonian.

Teorema:

Fie G=(X,U), cu n>=3 varfuri, daca oricare ar fi x un nod al grafului si d(x)>=n/2, atunci graful este hamiltonian.

Se numeste ciclu eulerian intr-un graf, un ciclu care contine toate muchiile grafului.

Un graf care contine un ciclu eulerian se numeste graf eulerian.

Un lant eulerian este un lant care contine toate muchiile grafului.

Teorema:

Un graf fara varfuri izolate este eulerian, daca si numai daca este conex si gradele tuturor varfurilor sunt numere pare.

Parcurgerea grafurilor neorientate

Prin parcurgerea grafurilor neorientate se intelege vizitarea varfurilor intr-o anumita ordine, ordine data de un anumit criteriu.

Exista doua metode de parcurgere:

Parcurgerea in latime BF(Breadth First);

Parcurgerea in adancime DF(Depth First);

Algoritmul de parcurgere in latime BF

Fiind dat un graf neorientat G=(X,U) si un nod xIX, sa se parcurga toate varfurile grafului incepand din varful x.

Metoda consta in:

-se viziteaza varful de pornire, dupa care se viziteaza toate varfurile adiacente cu acesta care nu au fost vizitate inca,in continuare se alege primul varf adiacent cu varful de pornire si se viziteaza toate varfurile adiacente cu acesta nevizitate inca si asa mai departe pentru celelalte varfuri cat timp este posibil.Exemplu:

Presupunem ca varful de pornire este 1,atunci parcurgerea BF este:1,2,5,6,3,4,7.

Pentu 3 varf de pornire:3,2,4,1,5,6,7.

Pentru implementare vom folosi un vector care are proprietatile unei cozi, fie c=(c₁,c₂,.,c_k). Capetele de intoducere si extragere vor fi identificate prin pozitiile p si respectiv u.

Notam cu n numarul de noduri din graf. Este necesar ca elemntele matricei de adiacenta a cu n linii*n coloane sa fie cunoscute.

Mai avem nevoie de un vector viz cu n elemente, in care elementele viz[k] (k=1,2,..,n) au semnificatia: viz[i]=0, daca varful i nu a fost vizitat sau viz[i]=0 daca a fost vizitat. Mai intai initializam tot vectorul viz cu 0.

Initial in coada se gaseste varful de pornire: p=1, u=1, c[p]:=x, viz[x]:=1.

Cat timp mai sunt elemente in coada("while p<=u"):

Extragem din coada varful aflat in capatul de extragere u, si-l memoram intr-o variabila z;

Pe linia z in a cautam vecinii lui z si ii introducem in coada.

Algoritmul de parcurgere in adancime DF

Metoda consta in:

-alegem varful de pornire, pentru acesta se alege primul vecin al sau nevizitat inca,pentru acest vecin cautam primul vecin al sau nevizitat si asa in continuare. In cazul in care un varf nu mai are vecini nevizitati atunci ne intoarcem la nodul anterior, iar pentru acel nod cautam urmatorul vecin nevizitat al sau.

Pentru graful de mai sus parcurgerea in adancime plecand de la varful 1 este: 1,2,3,4,6,7,5.

Pentru a implementa vom folosi o stiva si metoda backtracking.

Conexitatea in grafurile neorientate

Prin parcurgerea in latime acelui graf am subliniat o proprietate importanta a grafului:faptul ca in urma parcurgerii au fost vizitate toate varfurile.

Luand oricare doua varfuri,putem gasi cel putin un traseu care porneste dintr-un varf si ajunge in celalalt. Luand oricare doua varfuri, ele pot fi legate printr-un lant. Dar nu toate grafurile sunt conexe. In schimb putem desprinde din el "portiuni" care, fiecare luata separat, este un graf conex.

Exemplu:

Se numeste componenta conexa a grafului G=(X,U), un subgraf G₁=(X₁,U₁) a lui G, conex, cu proprietatea ca nu exista nici un lant care sa lege un varf din X₁ cu un varf din X-X₁.

In explicarea modului de functionare a acestei metode de parcurgere se foloseste un sir de intregi, VIZITAT, de lungime n cu ajutorul caruia se marcheaza nodurile deja "vizitate" pentru a evita trecerea de mai multe ori prin acelasi nod.Cu alte cuvinte VIZITAT[j] = 1 daca nodul j a fost deja atins si VIZITAT[j] = 0 in caz contrar.Vom spune despre un nod i ca a fost explorat daca are toate nodurile adiacente vizitate.

Procedura recursiva care asigura parcurgerea unui graf in adancime incepand cu un anumit varf i:

Procedura Parcurgere_in_adancime(i)

pentru toate varfurile k adiacente cu varful i executa

daca varful k este neparcurs

atunci se parcurge varful k

apel parcurgere_in_adancime(k)

Iesirea din recursivitate se produce in momentul in care nu se mai gasesc varfuri neparcurse adiacente cu varfurile parcurse deja. Este posibil ca dupa un apel al procedurii incepand cu un anumit varf i sa ramana in graf varfuri neparcurse.In aceasta situatie apelul procedurii se repeta pentru un alt varf initial (dintre varfurile neparcurse) pana la parcurgerea tuturor nodurilor grafului. Programul apelant trebuie sa asigure parcurgerea varfului utilizat in apel.Conditiile interne care apar in problemele particulare de backtracking pot impune o parcurgere integrala sau numai partiala a grafului.Procedura backtracking(i) este pentru cazul parcurgerii integrale a unui graf in adancime:

Procedura Backtracking(i)

pentru toate varfurile k adiacente cu varful i executa

daca varful k este neparcurs si sunt indeplinite conditiile de continuare

atunci se parcurge varful k

se utilizeaza varful k in solutie

daca s-a ajuns la o solutie se afiseaza

apel Backtracking(k)

Folosind aceasta tehnica de traversare ne propunem sa raspundem la intrebarea:

Fiind dat un graf neorientat G=(V,E), este acesta un graf conex?

Conform acestei metode explorarea unui nod este suspendata ori de cate ori un nou varf este vizitat.Pentru graful G daca pornim din varful 1, vizitarea nodurilor se va face in ordinea: 1,2,4,8,5,6,3,7.

Urmatoarea functie returneaza true daca graful este conex si false in caz contrar folosind tehnica parcurgerii in adancime:

Function Conex: boolean;

Procedura adancime(s)

VIZITAT[s]:=1;

pentru fiecare nod w adiacent cu s executa

daca VIZITAT[w] = 0 atunci apel adancime(w)

sfarsit daca;

sfarsit pentru;

sfarsit procedura;

pentru toate nodurile w executa

VIZITAT[w]:=0;

sfarsit pentru;

apel adancime(1);

Conex:=true;

pentru toate nodurile w executa

daca VIZITAT[w] = 0 atunci

conex:=false;

sfarsit daca;

sfarsit pentru;

Sfarsit functie;

Aplicatie practica

Enuntul problemei

Sa se relizeze o aplicatie in limbajul Pascal care sa evidentieze grafic modul de parcurgere in latime si in adincime a unui graf neorienta. Datele de intrare ale programului sunt:

numarul de noduri ale grafului

numarul nodului de start in parcurgerea grafului

matricea de adiacenta a grafului

Aceste date sunt citite din fisierul PARC_GRF,TXT.

Descrierea problemei

Variabile Globale

n - numarul de noduri ale grafului

nstart - numarul nodul de start in parcurgerea grafului

m - reprezinta matricea de adiacenta a grafului

nod - nodul curent

tata - numarul tattalui nodului curent

s[] - este un vector cu rol de stiva si stocheaza nr. Nodului curent

Functti si Proceduri

InitializareModGrafic() - efectueaza operatia d initializare a modului grafic.

ReadData() - citeste din fisierul PARC_GRF.TXT datele de intrare.

Parcurgere() - efectueaza o parcurgere a grafului cu scopul determinarii numarului de nivele si de initializare a vectorului s[}

Conect(q,w:byte) - testeaza daca varful q are o muchie comuna cu varful w si o deseneaza

GNod(q:byte) deseneaza nodul q

MarkNod(q:byte) - marcheaza nodul vizitat

pa() - efectueaza parcurgerea in adancime a grafului

pl() - efectueaza parcurgerea in latime a grafului

primapagina - implementeaza pagina de start a proiectului

meniu - implementeaza meniul aplicatiei. Meniul permite selectia tipului de parcurgere sau optiunea de iesire din program.

Codul sursa

program Parcurgere_Arbore;

uses Crt,Graph;

type

matrice=array[1..16,1..16] of byte;

vector=array[1..16] of byte;

var

m,mtr :matrice;

s,v,p,d :vector;

ti,j,n,k :byte;

i:integer;

nivele,nstart, npen,pos :byte;

nod,tata, nr:byte;

as,ev :boolean;

opt,ch :char;

procedure InitializareModGrafic;

var driver,modg :integer;

begin

driver:=detect;

initgraph(driver,modg,'..bgi');

end;

procedure ReadData;

var

i,j :byte;

f :text;

begin

assign(f,'PARC_GRF.txt');

reset(f);

read(f,n);

read(f,nstart);

for i:=1 to n do

for j:=1 to n do

read(f,m[i,j]);

close(f);

end;

procedure Parcurgere;

var i,aux,k,k1 :byte;

b :boolean;

s :vector;

begin

for i:=1 to n do p[i]:=0;

k:=1; s[k]:=nstart;

k1:=1; d[k1]:=nstart;

p[s[k]]:=p[s[1]]+1;

repeat

for i:=1 to n do

begin

if m[s[1],i]=1 then

begin

inc(k); s[k]:=i;

m[s[1],i]:=0; m[i,s[1]]:=0;

inc(k1); d[k1]:=s[k];

p[s[k]]:=p[s[1]]+1;

end;

end;

for i:=1 to k-1 do

s[i]:=s[i+1];

dec(k);

until k=0;

repeat

b:=true;

for i:=1 to n-1 do

if p[i]>p[i+1] then

begin

aux:=p[i];

p[i]:=p[i+1];

p[i+1]:=aux;

b:=false;

end;

until b;

nivele:=0;

for i:=1 to n do

if p[i]>nivele then nivele:=p[i];

end;

procedure Conect(q,w:byte);

var kx,ky,kk :integer;

aux,i :byte;

x1,y1,x2,y2 :integer;

begin

npen:=0; pos:=0;

for i:=1 to n do

if d[i]=q then begin kk:=i; i:=n; end;

for i:=1 to n do

begin

if p[i]=p[kk] then inc(npen);

if (i<=kk)and(p[i]=p[kk]) then inc(pos);

end;

y1:=(350 div nivele)*p[kk];

x1:=285-((npen*70)div 2)+pos*70;

npen:=0; pos:=0;

for i:=1 to n do

if d[i]=w then begin kk:=i; i:=n; end;

for i:=1 to n do

begin

if p[i]=p[kk] then inc(npen);

if (i<=kk)and(p[i]=p[kk]) then inc(pos);

end;

y2:=(350 div nivele)*p[kk];

x2:=285-((npen*70)div 2)+pos*70;

setcolor(3); line(x1,y1,x2,y2);

end;

procedure GNod(q:byte);

var kx,ky,kk :integer;

i :byte;

s :string;

begin

npen:=0; pos:=0;

for i:=1 to n do

if d[i]=q then begin kk:=i; i:=n; end;

for i:=1 to n do

begin

if p[i]=p[kk] then inc(npen);

if (i<=kk)and(p[i]=p[kk]) then inc(pos);

end;

ky:=(350 div nivele)*p[kk];

kx:=285-((npen*70)div 2)+pos*70;

str(q,s);

setcolor(q mod 9+1);

setfillstyle(10,q mod 9+1); fillellipse(kx,ky,15,15);

setfillstyle(11,q mod 9+1); fillellipse(kx-2,ky-2,13,13);

setfillstyle(9,q mod 9+1); fillellipse(kx-2,ky-2,11,11);

setfillstyle(1,q mod 9+1); fillellipse(kx-2,ky-2,9,9);

setcolor(q mod 9+1); circle(kx,ky,15);

setcolor(7); circle(kx,ky,16);

settextstyle(1,0,0);

setusercharsize(1,2,1,2);

settextjustify(1,1);

setcolor(15);

outtextxy(kx,ky-3,s);

settextstyle(11,0,0);

end;

procedure MarkNod(q:byte);

var kx,ky,kk :integer;

i :byte;

s :string;

begin

npen:=0; pos:=0;

for i:=1 to n do

if d[i]=q then begin kk:=i; i:=n; end;

for i:=1 to n do

begin

if p[i]=p[kk] then inc(npen);

if (i<=kk)and(p[i]=p[kk]) then inc(pos);

end;

ky:=(350 div nivele)*p[kk];

kx:=285-((npen*70)div 2)+pos*70;

SetLineStyle(0,0,1);

Circle(kx,ky,20);

end;

procedure ParcLatime;

var i,aux,k,k1 :byte;

b :boolean;

v :vector;

st :string;

begin

k:=1; s[k]:=nstart; k1:=1;

MarkNod(s[k]);

Str(s[k],st);

Outtextxy(k1*40,457,st);

Delay(500);

repeat

for i:=1 to n do

begin

if m[s[1],i]=1 then

begin

inc(k); s[k]:=i; inc(k1);

m[s[1],i]:=0; m[i,s[1]]:=0;

MarkNod(s[k]);

Str(s[k],st);

Outtextxy(k1*40,457,st);

Delay(500);

end;

end;

for i:=1 to k-1 do

s[i]:=s[i+1];

dec(k);

until k=0;

end;

procedure ParcAdincime;

var i,aux,k,k1 :byte;

b :boolean;

v :vector;

st :string;

begin

k:=1; s[k]:=nstart; k1:=1;

MarkNod(s[k]);

Str(s[k],st);

Outtextxy(+k1*40,457,st);

Delay(500);

repeat

b:=true;

for i:=1 to n do

begin

if m[s[k],i]=1 then

begin

b:=false;

m[s[k],i]:=0; m[i,s[k]]:=0;

inc(k); s[k]:=i; inc(k1);

i:=n;

MarkNod(s[k]);

Str(s[k],st);

Outtextxy(k1*40,457,st);

Delay(500);

end;

end;

if b then dec(k);

until k=0;

end;

procedure pl;

begin

SetFillStyle(6,1);

Bar(0,0,639,479);

SetColor(11);

Rectangle(0+5,0+5,639-5,479-5);

ReadData; mtr:=m;

Parcurgere; m:=mtr;

for i:=1 to n do

for j:=1 to n do

if m[i,j]=1 then Conect(i,j);

for i:=1 to n do GNod(i);

SetTextStyle(7,0,2);

SetTextJustify(0,1);

OutTextXY(10,430,'Parcurgere in latime: ');

ParcLatime;

ReadKey;

ClearDevice;

SetColor(15);

Rectangle(0,0,639,479);

end;

procedure pa;

begin

SetFillStyle(6,1);

Bar(0,0,639,479);

SetColor(11);

Rectangle(0+5,0+5,639-5,479-5);

ReadData; mtr:=m;

Parcurgere; m:=mtr;

for i:=1 to n do

for j:=1 to n do

if m[i,j]=1 then Conect(i,j);

for i:=1 to n do GNod(i);

SetTextStyle(7,0,2);

SetTextJustify(0,1);

OutTextXY(10,430,'Parcurgere in adincime: ');

ParcAdincime;

ReadKey;

ClearDevice;

SetColor(15);

Rectangle(0,0,639,479);

end;

procedure primapagina;

begin

cleardevice;

Rectangle(0,0,636,476);

Rectangle(3,3,639,479);

setcolor(14);

settextstyle(1,0,2);

outtextxy(90,20,' Liceul de Informatica - Slatina');

settextstyle(10,0,3);

setcolor(9);

for i:=0 to 2 do begin

outtextxy(135+i,100+i,'PROIECT DE ATESTAT');

outtextxy(100+i,140+i,'= parcurgerea grafurilor =');

delay(100);

end;

settextstyle(3,0,3);

for i:=0 to 194 do begin

setcolor(12);

outtextxy(i-100,360,'Indrumator :');

outtextxy(640-i,360,'Executant :');

setcolor(0);

outtextxy(i-100,360,'Indrumator :');

outtextxy(640-i,360,'Executant :');

i:=i+2;

end;

setcolor(12);

outtextxy(80,360,'Indrumator :');

outtextxy(430,360,'Executant :');

setcolor(15);

Rectangle(0,0,636,476);

Rectangle(3,3,639,479);

for i:=292 DOWNto 80 do begin

setcolor(12);

outtextxy(i,400,'OPRISAN OLTITA');

outtextxy(530-i,400,'MUSTATA CRISTIAN');

setcolor(0);

outtextxy(i,400,'OPRISAN OLTITA');

outtextxy(530-i,400,'MUSTATA CRISTIAN');

i:=i-2;

end;

setcolor(12);

outtextxy(80,400,'OPRISAN OLTITA');

outtextxy(430,400,'MUSTATA CRISTIAN');

settextstyle(0,0,0);

setcolor(14);

outtextxy(300,460,'2005');

setcolor(15);

Rectangle(0,0,636,476);

Rectangle(3,3,639,479);

readkey;

cleardevice;

end;

procedure desenmenu(o:integer);

begin

setcolor(0);

Rectangle(178,128,462,162);

Rectangle(178,178,462,212);

Rectangle(178,228,462,262);

settextstyle(1,0,2);

settextjustify(0,2);

case o of

1:begin setcolor(12);Rectangle(178,128,462,162);end;

2:begin setcolor(12);Rectangle(178,178,462,212);end;

3:begin setcolor(12);Rectangle(178,228,462,262);end;

end;

end;

procedure meniu;

begin

SetFillStyle(6,1);

Bar(0,0,639,479);

SetColor(11);

Rectangle(0+5,0+5,639-5,479-5);

setcolor(9);

settextstyle(10,0,3);

settextjustify(0,2);

outtextxy(260,60,'Meniu');

setcolor(15);

Rectangle(180,130,460,160);

Rectangle(180,180,460,210);

Rectangle(180,230,460,260);

settextstyle(1,0,2);

settextjustify(0,2);

outtextxy(185,130,' Parcurgere in adincime');

outtextxy(185,180,' Parcurgere in latime');

outtextxy(185,230,' Exit');

setcolor(0);

Rectangle(178,128,462,162);

Rectangle(178,178,462,212);

Rectangle(178,228,462,262);

nr:=1;

desenmenu(1);

repeat

opt:=readkey;

case opt of

#80:

begin

if (nr=3) then nr:=1 else nr:=nr+1;

desenmenu(nr);

end;

#72:

begin

if (nr=1) then nr:=3 else nr:=nr-1;

desenmenu(nr);

end;

#13:

begin

case nr of

1:begin cleardevice;pa;end;

2:begin cleardevice;pl;end;

3:begin closegraph;halt(1);end;

end;

SetFillStyle(6,1);

Bar(0,0,639,479);

SetColor(11);

Rectangle(0+5,0+5,639-5,479-5);

setcolor(9);

settextstyle(10,0,3);

settextjustify(0,2);

outtextxy(260,60,'Meniu');

setcolor(15);

Rectangle(180,130,460,160);

Rectangle(180,180,460,210);

Rectangle(180,230,460,260);

settextstyle(1,0,2);

settextjustify(0,2);

outtextxy(185,130,' Parcurgere in adincime');

outtextxy(185,180,' Parcurgere in latime');

outtextxy(185,230,' Exit');

setcolor(0);

Rectangle(178,128,462,162);

Rectangle(178,178,462,212);

Rectangle(178,228,462,262);

desenmenu(nr);

end;

end;

until (opt=#27)

end;

Begin

ClrScr;

InitializareModGrafic;

primapagina;delay(500);

SetColor(15);

Rectangle(0,0,639,479);

meniu;

CloseGraph;

End.

Bibliografie

1. V.Cristea, E.Kalisz, I.Atanasiu, V.Iorga. Tehnici de programare. Ed.Teora, Bucuresti, 1995.

2.  V.Dadarlat, I.Ignat, M.Topan, L.Petrescu. Programarea calculatoarelor. Structuri de date si algoritmi. Litografia U.T.C.N., 1995.

I.Ignat, V,Dadarlat, M.Topan, L.Petrescu.. Turbo Pascal 7.0.

Fundamente si aplicatii. Ed.Albastra, Cluj-Napoca, 1996.     

4.  I.Ignat,  V.Dadarlat, I.Rus, A.Kacso. Programarea sistematica in Turbo Pascal 6.0. Ed. Cartii de Stiinta, Cluj-Napoca, 1992.

5. L.Livovschi, H.Georgescu. Analiza si sinteza algoritmilor. Ed. Enciclopedica, Bucuresti, 1986.

6. L.Negrescu. Limbajele C si C++ pentru incepatori, Vol. 1 si 2. Ed. Microinformatica, Cluj_Napoca, 1994 (reeditare 2000).

7. L.D.Serbanati, V.Cristea, F.Moldoveanu, V.Iorga. Programarea sistematica in limbajele Pascal si Fortran. Ed.Tehnica, Bucuresti, 1984.

8. N.Wirth. Algorithms + Data Structures = Programs.Prentice Hall, 1978.

9. Iosif Ignat Programarea calculatoarelor - Indrumator de lucrari de laborator  Editura UT Press 2001