LAB 2&3 - Matematica Discreta (Me)

8/12/2019 LAB 2&3 - Matematica Discreta (Me)

1/8

Universitatea Tehnic a Moldovei

Catedra Automatica si Tehnologii Informationale

RAPORTlucrarea de laborator #2TEMA: ALGORITMUL DE CUTARE N ADNCIME SI LARGIME

V. II

A ndeplinit: st. gr. C-1!

"olotchi #adu

A verificat: $. Marusic

Chi%inu !&1'

SCOPUL LUCRRII:


2/8

Studierea algoritmilor de cutare n graf i a diferitor forme de pstrare i prelucrare a datelor.

Elaborarea procedurii de cutare n adncime si largime.

SARCINA DE BAZ:

1. Elaborai procedura cutrii n adncime ntr!un graf arbitrar"

#. Elaborai un program cu urmtoarele posibiliti$ introducerea grafului n calculator% parcurgerea grafului n adncime% &i'uali'area re'ultatelor la displa( i imprimant.

1. Elaborai procedura care &a reali'a algoritmul de parcurgere a grafului n lrgime"

#. )olosind procedurile din lucrrile precedente% elaborai programul care &a permite$

introducerea grafului n calculator" parcurgerea grafului n lrgime" e*tragerea datelor la displa( i printer.

CONSIDERAII TEORETICE:

Structuri de date: liste

)iecare tip de list definete o mulime de iruri finite de elemente de tipul declarat. +umrul de elementecare se numete lungimea listei poate &aria pentru diferite liste de acelai tip. ,ista care nu conine nici unelement se &a numi &id. Pentru list sunt definite noiunile nceputul% sfritul listei i respecti& primul i

ultimul element% de asemenea elementul curent ca i predecesorul i succesorul elementului curent. Elementcurent se numete acel unic element care este accesibil la momentul dat.

Structuri de date :fire de ateptare

)irele de ateptare -FA% rnd% coad% ir de ateptare se &or folosi pentru a reali'a algoritmul de prelucrare aelementelor listei n conformitate cu care elementele &or fi eliminate din list n ordinea n care au fostincluse n ea -primul sosit ! primul ser&it.

Operaiile de ba' cu firele de ateptare$

)ormarea unui )A &id" /erificare dac )A nu este &id"

Alegerea primului element cu eliminarea lui din )A" 0ntroducerea unei &alori noi n calitate de ultim element al )A.

Structuri de date: stive

Sti&a se utili'ea' pentru a reali'a algoritmul de prelucrare a elementelor dup principiul ultimul sosit !primul prelucrat -,0)O.

Operaiile de ba' cu sti&ele sunt urmtoarele$

)ormarea unei sti&e &ide" /erificare la &id" Alegerea elementului din topul sti&ei cu sau fr eliminare" 0ntroducerea unui element nou n topul sti&ei.


3/8

Structuri de date -arbori

Se &a defini o mulime de structuri fiecare din care &a consta dintr!un obiect de ba' numit vrf saurdcina arborelui dat i o list de elemente din mulimea definit% care -elementele se &or numisubarboriai arborelui dat. Arborele pentru care lista subarborilor este &id se &a numi arbore trivial% iar rdcina lui !

frunz.

Rdcina arborelui se &a numi tatl &rfurilor care ser&esc drept rdcini pentru subarbori" aceste &rfuri se&or mai numi copiii rdcinii arborelui$ rdcina primului subarbore se &a numi fiul cel mai mare% iar

rdcina fiecrui subarbore urmtor n list se &a numi frate.Operaiile de ba' pentru arbori &or fi$

)ormarea unui arbore tri&ial" Alegerea sau nlocuirea rdcinii arborelui" Alegerea sau nlocuirea listei rdcinilor subarborilor" Operaiile de ba' care sunt &alabile pentru liste.

Algoritmul d !"ut#r $% l"rgim

Parcurgerea grafului n lrgime% ca i parcurgerea n adncime% &a garanta &i'itarea fiecrui &rf al grafului

e*act o singur dat% ns principiul &a fi altul. 2up &i'itarea &rfului iniial% de la care &a ncepe cutarea

n lrgime% &or fi &i'itate toate &rfurile adiacente cu &rful dat% apoi toate &rfurile adiacente cu aceste

ultime &rfuri .a.m.d. pn &or fi &i'itate toate &rfurile grafului. E&ident% este necesar ca graful s fie

cone*. Aceast modalitate de parcurgere a grafului -n lrgime sau postordine% care mai este adesea numit

parcurgere n ordine ori'ontal% reali'ea' parcurgerea &rfurilor de la stnga la dreapta% ni&el dup ni&el.

Algoritmul de mai 3os reali'ea' parcurgerea n lrgime cu a3utorul a dou fire de ateptare O1i O2.Se vor forma dou fire de ateptare vide O1i O2;

Introduce rdcina n FA O1;

WHILE cel puin unul din firele de ateptare O1sau O2nu va fi vid D

IF O1nu este vid !HE"

#E$I"

fiepv%rful din topul FA O1;

vi&itea& v%rfulpelimin%ndu'l din O1;

vi&itea& pe toi fiii luipn FA O2( ncep%nd cu cel mai mare;

E"D

ELSE

n calitate de O1se va lua FA O2( care nu este vid(

iar n calitate de O2se va lua FA vid O1;

/om nota c procedura parcurgerii grafului n lrgime permite s reali'm arborele de cutare i n acelai

timp s construim acest arbore. 4u alte cu&inte% se &a re'ol&a problema determinrii unei re'ol&ri sub

forma &ectorului -a1, a2,... de lungime necunoscut% dac este cunoscut c e*ist o re'ol&are finit a

problemei.


4/8

Algoritmul pentru ca'ul general este analogic cu cel pentru un graf n form de arbore cu o mic modificare

care const n aceea c fiecare &rf &i'itat &a fi marcat pentru a e*clude ciclarea algoritmului.

C"ut#r $% #d&%!im

,a cutarea n adncime -parcurgerea unui graf n sens direct% n preordine &rfurile grafului &or fi

&i'itate n conformitate cu urmtoarea procedur recursi&$

mai nti va fi vizitat rdcina arborelui q, aoi, dac rdcina arborelui nu este frunz - entru fiecare

fiu al rdcinii q ne vom adresa recursiv rocedurii de arcur!ere n adncime entru a vizita vrfurile

tuturor subarborilor cu rdcina ordonate ca fii ai lui q"

5n ca'ul utili'rii unei sti&e pentru pstrarea drumului curent pe arbore% drum care ncepe din rdcina

arborelui i se termin cu &rful &i'itat n momentul dat% poate fi reali'at un algoritm nerecursi& de forma$

Viziteaz rdcina ar)orelui i introdu'o n stiva vid S;

WHILE stiva Snu este vid D

BEGIN

fiep' v%rful din topul stivei S;

IF fiii v%rfuluipnc nu au fost vi&itai

!HE" vi&itea& fiul mai mare al lui pi introduce'l n S

ELSE BEGIN

elimin v%rfulpdin stiva S

IFpare frai !HE" vi&itea& pe fratele luipi introduce'l n stiva S

E"DE"D

Acest algoritm poate fi modificat pentru a putea fi utili'at la parcurgerea tuturor &rfurilor unui graf arbitrar.

5n algoritmul de mai 3os se &a presupune c este stabilit o relaie de ordine pe mulimea tuturor &rfurilor

grafului% iar mulimea &rfurilor adiacente cu un &rf arbitrar al grafului este de asemenea ordonat$

WHILE va e*ista cel puin un v%rf care nu a fost vi&itat D

#E$I"

fiep' primul din v%rfurile nevi&itate;

vi&itea& v%rfulpi introduce'l n stiva vid S;

WHILE stiva Snu este vid D

#E$I"

fiep' v%rful din topul stivei S;

IF mv%rfuri ale luipsunt v%rfuri adiacente nevi&itate

!HE" #E$I"

fie zprimul v%rf nevi&itat din v%rfurile adiacente cup;

parcur+e muc,ia (p,z)( vi&itea& v%rful zi introduce'l n stiva S;

E"D

ELSE elimin v%rfulpdin stiva S

E"D

E"D


5/8

5n ca'ul n care se &a lucra cu un graf cone* arbitrar cu relaia de ordine lips% nu &a mai a&ea importan

ordinea de parcurgere a &rfurilor. Propunem un algoritm care utili'ea' mai larg posibilitile sti&ei% cea ce

face programul mai efecti& n sensul diminurii timpului de calcul necesar. 2e e*emplu% acest algoritm n

&arianta recursi& este pe larg utili'at n programele de selectare global n subdirectori -ca'ul programelor

anti&irus.

Introdu n stiv v%rful iniial i marc,ea&'l;

WHILE stiva nu este vid D

#E$I"

e*tra+e un v%rf din stiv;

IF e*ist v%rfuri nemarcate adiacente cu v%rful e*tras

!HE" marc,ea&'le i introduce'le n stiv;

E"D

Li'ti%gul Progr#mului:

6include 7conio.89

6include 7stdio.89

6include 7stdlib.89

::!!!!!!!!!!!!!!!!!!!!!!!!!!!!

&oid Pre't-

; clrscr-"

::!!!!!!!!!!!!!!!!!!!!!!!!!!!

&oid main-

;int i%3%?%l%n%s%*%(%8"c8ar c8"

::!!!!!!!!!!!!!!!!!!!!!!!!!!!

Pre't-"

,1$static int a@BC@#BC%b@BC"

clrscr-"


6/8

for-iHB"i7n"iII

;

printf-rF#iJ%iI1"

scanf-Fi%Ga@iC@BC"

for-3H1"37nI1"3II

if-a@iC@3!1CKHB scanf-Fi%Ga@iC@3C"

else brea?">::!!!!!!!!!!!!!!!!!!!!!!!!!!!!

for-iHB"i7n"iII b@iCHiI1"

for-iHB"i7n"iII

for-3HB"37n"3II

if-a@iC@3CKHB

if-b@a@iC@3C!1CKHBGGB7a@iC@3CGGa@iC@3C7Hn b@a@iC@3C!1CHB"

else goto l#" :: ErorK

else brea?"

for-iHB%*HB"*7n"*II

if-b@*CKHB ;b@BCH*I1" iII">

if-i91 goto l#" :: ErorK

*H(HB"

printf-nnr"

printf-Parcurgerea in largime $nr"

printf-n Fd%%b@BC"

for-iH1"i7n"iII

; if-a@b@*C!1C@(CHHB ;*II" (HB" i!!">else ;b@iCHa@b@*C!1C@(C" (II"

printf- Fd%%b@iC"

if-iF1LHHB printf-n"

>

>

goto lM"

l#$printf-nnttt"

printf-EroareK"

goto l"

::!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

lM$printf-nnnr"

printf-Parcurgerea in adimcime$n"

iHb@BC!1"3HsH8HB"

printf-n Fd%%b@BC"

N8ile-87n!1

;?Hi"

if-a@?C@3CKHB ; printf- Fi%%a@?C@3C"

iHa@?C@3C!1"

>


7/8

l1$if-a@?C@3CHHB

; if-sHHBlH?I1"

if-sHH1lH*I1"

for-*HB"*7n"*II

for-(HB"(7nI1"(II

; if-a@*C@(CHHlGGa@*C@(I1CKHB

; printf- Fi%%a@*C@(I1C"iHa@*C@(I1C!1"

sHB"

goto lL" >

if-a@*C@(CHHlGGa@*C@(I1CHHB

; sH1"goto l1">

>

>

lL$8II"

if-8F1LHHB printf-n"

>

::!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

l$


8/8

!Concluzie:Efecuand aceasta lucrare de laborator% am in&atat sa efectuam metodele de repre'entare alegrafului atit in adincime cit si in largime% precum si metodele lui de stocare in memoria calculatorului.4a si la prima lucrare% pentru introducerea datelor am folosit lista de adiacenta% ea fiind cea mai simplametoda de introducere a grafului de la tastatura% care si piermite utili'atorului sa aleaga cu usurinta&irfurile necesare%de asemenea aceasta metoda utili'ea'a si cel mai putin din memoria calculatorului.

LAB 2&3 - Matematica Discreta (Me)

Documents

Transcript of LAB 2&3 - Matematica Discreta (Me)