Structura de tip coada
Aplicaţii la structura coadă
1. Secvenţă de numere distincte
În fişierul numere.in pe prima linie se află un număr natural n (1 < n < 10000), iar pe a doua linie un şir de n numere naturale cuprinse între 1 şi 9999. Să se determine lungimea maximă a unei secvenţe de numere distincte din şir. Secvenţa este formată din elemente aşezate pe poziţii consecutive în şir. De exemplu, pentru n=19 şi şirul 7, 1, 3, 1, 2, 6, 9, 8, 1, 3, 5, 2, 11, 31, 12, 24, 25, 56, 25, lungimea maximă este 13 (începe cu numărul 6 şi se termină cu numărul 56).
Rezolvare:
Folosim o coadă de lungime n şi un vector viz de lungime 10000. Vom depune succesiv în coadă numerele din şir. Fiecare element i depus va avea viz[i]=1. Cand întâlnim un element x deja depus în coadă, actualizăm (dacă este cazul) lungimea maximă şi extragem din coadă toate numerele până la x inclusiv, având grijă să le marcăm pe acestea ca nevizitate (ele nu mai sunt în coadă).
#include<fstream.h>
#define Dim 10000
int q[Dim],viz[Dim] ;
int main()
{
int n, x, i, lungmax, lung, pr, ul ;
ifstream f("numere.in") ;
f>>n ;
lung = lungmax = 0 ;
pr = 0 ; ul = -1 ;
for (i=1 ; i<=n ; i++)
{
f>>x ;
if (viz[x] == 1) // x este deja in coada, deci scot tot pana la x inclusiv
{
if (lungmax < lung) lungmax = lung ;
while (q[pr] != x)
{
viz[q[pr]] = 0 ;
pr++ ;
lung-- ;
}
// am ajuns la x, il scot si pe el din coada:
viz[x] = 0 ;
pr++ ;
lung-- ;
}
// adaug pe x in coada:
viz[x] = 1 ;
q[++ul] = x ;
lung++ ;
}
if (lung > lungmax) lungmax = lung ;
cout<<"\n Lungimea maxima este : "<<lungmax ;
f.close() ;
return 0 ;
}
2) Se consideră un număr natural n. Asupra lui n se pot efectua una din următoarele operaţii:
a. dacă n este par, n se înjumătăţeşte (n = n div 2)
b. dacă n este impar, se multiplică cu 3 şi se adună 1 (n = 3*n+1)
Pornind de la n se poate ajunge la 1 aplicând operaţiile a şi b într-un număr finit de paşi (este demonstrat acest lucru pentru orice n reprezentabil pe 32 de biţi). Se cere să se depună toate valorile obţinute într-o coadă şi să se determine valoarea maximă la care ajunge n.
De exemplu, pentru n=7, în coadă depunem valorile:
7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
Valoarea maximă este 52.
3) Să se prelucreze datele celor n angajaţi ai unei firme (nume, profesia, salariu). Datele se citesc din fişier şi sunt înregistrate în ordinea angajării (pentru fiecare persoană datele sunt scrise pe o linie).
a) Sa se afişeze datele după ce acestea au fost memorate intr-o structura de tip date.
b) Cel mai vechi angajat se pensionează. Să se afişeze şi să modifice datele din structura şi apoi din fişier
c) Cel mai vechi angajat primeşte o primă de 2000 000 de lei. Să se afişeze şi să se modifice datele din structură şi apoi din fişier
4) Să se memoreze n numere întregi într-o structură de tip coada. Să se şteargă elementele neprime din vârful cozii până se întâlneşte un număr prim.
5) La o intrare într-o sală de spectacole sunt 2 rânduri de persoane păstrate în două structuri de tip coada. Pentru că există doar un singur angajat care verifică biletele, pe poartă poate să intre la un moment dat o singură persoană. Ştiind că angajatul este corect şi permite să intre alternativ câte o persoană din fiecare rând, se cere să se afişeze ordinea de intrare a persoanelor în sala de spectacol.
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ă
Grama Razvan 15-4-2013 14:25:50
bun articol . scurt si la obiect . bravo !