Pagina principala | Inscriere | Autentificare | Probleme | Clasament pe runde | Clasament | Anunturi | Echipa | Regulament | Linkuri


Vizualizare solutie

Titlul problemei: secvreg
Numarul problemei: 2
Runda: Runda 2 - Concurs
Solutie: Numim coada cu dubla prioritate (dequeue) o structura de date care

suporta urmatoarele operatii:

- inserare element la sfaristul cozii

- inserare element la inceputul cozii

- extragere element de la sfarsitul cozii

- extragere element de la inceputul cozii

- accesarea elementului de la inceputul cozii

- accesarea elementului de la sfarsitul cozii.

Vom utiliza doua cozi cu dubla prioritate:

1. Coada a cu elemente de tip caracter in care inseram succesiv caracterele

din sirul initial si ulterior cele specificate in operatiile din fisierul de intrare.

2. Coada b cu elemente de tip intreg;

b[i]=lungimea secventei regulate care incepe cu pozitia i;

Implementam cozile a si b ca doi vectori.

Pentru a putea realiza operatii si la inceputul si la sfarsitul vectorilor,

am dublat spatiul de memorie necesar pentru fiecare dintre cei doi vectori

si am inceput inserarea elementelor de la mijloc.

Initial inseram in ordine toate caracterele sirului citit in coada a.

Pentru a pastra ordinea, fiecare noua caracter va fi inserat la sfarsitul cozii

Cand la inseram o paranteza deschisa la sfarsitul cozii, iar pe ultima pozitie

in coada este paranteza deschisa corespunzatoare, deducem ca se formeaza

o secventa regulata cu lungimea 2 mai mare decat cea deja existenta pe aceasta pozitie.

Prin urmare retinem in vectorul b aceasta lungime si eliminam din coada a cele doua paranteze

(practic fiecare secventa regulata formata este eliminata din a, dar in b retinem lungimile secventelor formate).

Cand inseram la inceputul cozii a o paranteza deschisa iar la inceputul cozii a era paranteza inchisa corespunzatoare,

se formeaza o secventa regulata cu 2 mai mare si executam aceleasi operatii ca in cazul precedent.

Pentru evaluare au fost utilizate 10 teste (numerotate de la 0 la 9) si s-au acordat 10 puncte pentru fiecare test.

Inapoi

© 2002 - 2004 Vālsan Mihai Liviu
Puteti trimite intrebari, comentarii, sau sugestii la adresa liviuvalsan@yahoo.com