Teză clasa a X-a, an școlar 2013-2014, semestrul II - Stiva, coada, lista
Notă: Se vor rezolva, la alegere, două din cele trei probleme. Fiecare problemă este punctată cu 4 puncte, se acordă 2 puncte din oficiu
1. În fişierul numere.in pe prima linie se află un număr natural n, iar pe a doua linie se află un şir de n numere naturale separate prin câte un spaţiu. Utilizând o stivă de lungime maximă 1000 şi utilizând operaţiile PUSH şi POP specifice stivei, introduceţi în stivă şi extrageţi din stivă şirul de numere din fişier după regulile următoare (considerăm că tocmai am citit din fişier numărul x):
a. Dacă stiva e vidă, introducem pe x în stivă
b. dacă numărul din vârful stivei este mai mic decât x, atunci extragem din stivă toate numere până ce stiva se goleşte sau până ce în vârful stivei rămâne un număr mai mare sau egal decât x. introducem apoi pe x în stivă.
c. Dacă numărul din vârful stivei este mai mare decât x, introducem pe x în stivă
Să se citească succesiv cele n numere din fişier şi să se introducă în stivă respectând regulile de mai sus. Să se afişeze apoi câte numere au mai rămas în stivă.
De exemplu, pentru n=10 şi şirul 6, 4, 2, 5, 5, 1, 7, 4, 2, 3 atunci se procedează astfel: se introduc pe rând 6, 4, 2, apoi se extrag 2 şi 4, se introduc 5, 5, 1, se extrag 1, 5, 5, 6, se introduce 7, apoi se introduc 4, 2, se extrage 2 şi se depune 3. În stivă rămân deci 2 numere: 7 şi 3.
2. Se citeşte din fişierul numere.in un şir de n numere naturale distincte cuprinse între 1 şi n. Avem la dispoziţie stiva st şi coada q. Elementele din şir se pot depune şi extrage în/din stivă sau se pot depune direct în stivă. Acestea sunt singurele operaţii permise. Se cere să se verifice dacă numerele de la 1 la n se pot afla în final în ordine crescătoare în coadă.
Exemplu 1:
şir.in
6
4 2 1 3 6 5
Răspuns: Se pot pune. 4 şi 2 se pun în stivă, apoi 1 în coadă, 2 din stivă în coadă, 3 din şir în coadă, 4 din stivă în coadă, 6 în stivă, 5 în coadă, 6 din stivă în coadă.
Exemplul 2:
şir.in
6
2 3 1 6 4 5
Răspuns: nu se poate.
3. Considerăm o listă inițial vidă. Asupra listei presupunem că se pot efectua operațiile:
a. (S, x) – adaugă la capătul din stânga a listei valoarea x
b. (D, x) – adaugă la capătul din dreapta a listei valoarea x
c. E – elimină valoarea cea mai din stânga din listă
d. F – elimină valoarea cea mai din dreapta din listă
e. M – întrebare: care este valoarea minimă din listă?
Considerând că în fișierul operatii.in se găsesc n astfel de operații, se cere să se afișeze în fișierul operații.out răspunsul la fiecare operație de tip M din fișierul de intrare. (Fișierul de intrare îl veți considera corect construit, în sensul că nu se va cere efectuarea de operații de eliminare din listă vidă sau nu se va cere determinarea valorii minime din lista vidă)
Exemplu:
| operatii.in 9 S 3 D 4 S 1 M E M D 3 E M |
operatii.out 1 3 3 |
Explicații Ce se află în listă: 3 3 4 1 3 4 - 3 4 - 3 4 3 4 3 - |
Despre autor
Dan Pracsiu deţinător www.dponline.ro
Profesor, Liceul Teoretic "Emil Racoviță" Vaslui
Membru în Comisia Naţională a Olimpiadelor de Informatică
Pasiuni: istoria, călătoriile, fotografia, muzica clasică
