Parcurgerea sirurilor - Vizitam fiecare element!

Parcurgerea unui sir inseamna sa vizitam fiecare element, unul cate unul, pentru a-l procesa (afisa, modifica, verifica, etc.). Este operatia fundamentala pe care o facem cu orice sir de date - fara parcurgere, elementele stau acolo fara sa le putem folosi.

Gandeste-te la parcurgere ca la verificarea prezentei la clasa. Profesorul striga fiecare nume din catalog, unul cate unul, de la primul pana la ultimul. Nu sare peste nimeni si nu se opreste la jumatate - trece prin toata lista. La fel face si calculatorul cand parcurge un sir: viziteaza fiecare element, de la primul pana la ultimul, si face ceva cu el (il afiseaza, il verifica, il modifica).

In viata reala, parcurgerea apare peste tot. Cand citesti o carte, parcurgi paginile una cate una. Cand un casier scaneaza produsele din cosul tau, le parcurge pe rand. Cand un profesor corecteaza lucrarile, le ia una cate una si le noteaza. Cand asculti o lista de melodii, le auzi pe rand, de la prima la ultima. In toate aceste cazuri, elementele sunt procesate secvential - unul dupa altul, in ordine.

Parcurgerea este atat de importanta incat aproape orice algoritm care lucreaza cu siruri incepe cu ea. Vrei sa afli suma elementelor? Parcurgi sirul si aduni. Vrei sa gasesti cel mai mare element? Parcurgi sirul si compari. Vrei sa numeri cate elemente au o anumita proprietate? Parcurgi sirul si verifici fiecare element. Fara parcurgere, nu poti face nimic util cu un sir.

Cea mai comuna parcurgere este de la primul element pana la ultimul. Folosim structura FOR cu contorul i care ia valori de la 1 pana la n (numarul de elemente). La fiecare pas, accesam elementul v[i] si facem ceva cu el.

Sa urmarim executia pas cu pas. Cand i=1, se afiseaza v[1] (primul element). Cand i=2, se afiseaza v[2] (al doilea element). Si tot asa pana cand i=n, cand se afiseaza ultimul element. Dupa acest pas, contorul ar creste la n+1, dar depaseste limita, deci bucla se opreste. Simplu si elegant!

Aceasta parcurgere se numeste parcurgere directa sau parcurgere crescatoare , deoarece contorul creste de la o valoare mica la una mare. Este tipul de parcurgere pe care il vei folosi cel mai des - peste 90% din algoritmi cu siruri folosesc parcurgerea de la 1 la n. Motivul este simplu: de cele mai multe ori, vrem sa procesam toate elementele in ordinea in care au fost introduse.

Un detaliu important: in parcurgerea directa, contorul i joaca rol de index (pozitie). El nu contine valoarea elementului, ci pozitia la care se afla elementul. Valoarea propriu-zisa o obtinem prin v[i] . Nu confunda niciodata i (pozitia) cu v[i] (valoarea de pe acea pozitie).

Uneori avem nevoie sa parcurgem sirul invers, de la ultimul element la primul. Pentru aceasta, contorul incepe de la n si scade pana la 1, folosind pasul -1 :

Observa cele trei componente ale buclei: valoarea de start este n (ultimul element), valoarea de sfarsit este 1 (primul element), iar pasul este -1 (contorul scade cu 1 la fiecare pas). Fara pasul -1, bucla nu ar functiona corect, deoarece contorul ar incerca sa creasca de la n in sus, depasind imediat limita.

Parcurgerea inversa este utila in mai multe situatii practice. De exemplu, cand vrei sa afisezi un cuvant invers (pentru a verifica daca e palindrom), cand vrei sa procesezi cele mai recente date primele (ultimele adaugate, primele procesate), sau cand un algoritm cere sa parcurgi elementele in ordine descrescatoare a pozitiilor.

Un exemplu din viata reala: cand derulezi o lista de mesaje in telefon, cele mai recente apar primele (sus) si cele mai vechi la sfarsit. Aceasta este, conceptual, o parcurgere inversa - ultimul mesaj adaugat este primul afisat. La fel, istoricul browser-ului iti arata site-urile vizitate de la cel mai recent la cel mai vechi.

In timpul parcurgerii, nu suntem limitati doar la afisare. Putem modifica fiecare element al sirului. Aceasta este o operatie foarte puternica: parcurgem sirul si transformam valorile dupa o regula pe care o definim noi.

Sa urmarim traseul algoritmului pas cu pas. Avem sirul initial v = [5, 12, 8]. La pasul i=1, v[1] devine 5*2=10. La pasul i=2, v[2] devine 12*2=24. La pasul i=3, v[3] devine 8*2=16. Dupa parcurgere, sirul este [10, 24, 16]. Observa ca valorile originale s-au pierdut - au fost inlocuite cu valorile noi.

Putem aplica orice transformare dorim. De exemplu, v[i] = v[i] + 10 adauga 10 la fiecare element. Expresia v[i] = v[i] * v[i] inlocuieste fiecare element cu patratul sau. Sau v[i] = v[i] MOD 10 pastreaza doar ultima cifra a fiecarui element (restul impartirii la 10).

Un exemplu practic din viata reala: un magazin face o reducere de 20% la toate produsele. Daca preturile sunt stocate intr-un sir, parcurgem sirul si aplicam reducerea: v[i] = v[i] * 0.8 (pastrezi 80% din pret). La fel, daca un profesor decide sa adauge un punct bonus la toate notele: nota[i] = nota[i] + 1 . Parcurgerea cu modificare este operatia ideala pentru aplicarea unor transformari uniforme.

Unul dintre cele mai frecvente tipuri de probleme cu siruri este numararea elementelor care indeplinesc o anumita conditie. De exemplu: cate elemente sunt pare? Cate sunt negative? Cate sunt mai mari decat 10? Toate aceste probleme se rezolva cu acelasi tipar: parcurgem sirul, verificam conditia si numaram.

Sa analizam algoritmul. Variabila contor este initializata cu 0 inainte de bucla - deoarece la inceput nu am gasit inca niciun element par. La fiecare pas al parcurgerii, verificam daca elementul curent ( v[i] ) este par folosind operatorul MOD. Daca restul impartirii la 2 este 0, elementul este par si crestem contorul cu 1.

Tiparul numarare este foarte versatil. Schimband doar conditia din DACA, poti numara orice: v[i] > 0 (pozitive), v[i] < 0 (negative), v[i] MOD 3 = 0 (multipli de 3), v[i] >= 10 SI v[i] <= 99 (numere cu doua cifre). Structura algoritmului ramane identica - doar conditia se schimba.

Retine regula de aur: contorul de numarare se initializeaza intotdeauna cu 0 inainte de bucla. Daca il initializezi cu 1, vei obtine cu un element in plus fata de raspunsul corect. Daca il initializezi in interiorul buclei, se va reseta la fiecare pas si vei obtine 0 sau 1 la final.

Afisarea selectiva inseamna sa parcurgem sirul, dar sa afisam doar elementele care indeplinesc o anumita conditie. Este ca si cum ai merge prin raft si ai lua doar cartile care te intereseaza, lasandu-le pe celelalte la locul lor.

Diferenta fata de afisarea simpla este prezenta structurii DACA-ATUNCI in interiorul buclei. La fiecare pas, verificam conditia si executam SCRIE doar daca aceasta este adevarata. Elementele care nu indeplinesc conditia sunt pur si simplu ignorate - trecem peste ele fara a face nimic.

Sa facem traseul complet. La i=1: v[1]=-3, conditia -3>0 este FALSA, nu afisam. La i=2: v[2]=5, conditia 5>0 este ADEVARATA, afisam 5. La i=3: v[3]=-1, conditia -1>0 este FALSA, nu afisam. La i=4: v[4]=8, conditia 8>0 este ADEVARATA, afisam 8. La i=5: v[5]=2, conditia 2>0 este ADEVARATA, afisam 2. La i=6: v[6]=-7, conditia -7>0 este FALSA, nu afisam.

Afisarea selectiva poate fi combinata cu afisarea pozitiei. De exemplu, putem afisa nu doar valoarea, ci si unde se afla in sir: SCRIE("Pozitia ", i, ": ", v[i]) . Aceasta este utila cand vrem sa stim nu doar ce elemente indeplinesc conditia, ci si pe ce pozitii se afla ele in sir.

O aplicatie importanta a parcurgerii este cautarea : vrem sa aflam daca un anumit element exista in sir si, daca da, pe ce pozitie se afla. Este ca si cand cauti un numar de telefon in agenda: parcurgi lista de contacte pana gasesti numele pe care il cauti.

Algoritmul functioneaza astfel: citim valoarea pe care o cautam ( x ) si initializam o variabila gasit cu 0 (care inseamna "nu am gasit inca"). Parcurgem sirul element cu element si comparam fiecare v[i] cu x . Daca gasim o potrivire, afisam pozitia si marcam gasit = 1 . La final, daca gasit este inca 0, inseamna ca elementul nu exista in sir.

Aceasta tehnica se numeste cautare secventiala (sau cautare liniara) deoarece parcurgem elementele pe rand, in ordine. Este metoda cea mai simpla de cautare si functioneaza pe orice sir, indiferent daca elementele sunt ordonate sau nu. Dezavantajul este ca, pentru siruri foarte mari, poate fi lenta - trebuie sa verifici fiecare element pana gasesti ce cauti.

Variabila gasit se numeste variabila fanion (flag) deoarece semnaleaza daca un anumit eveniment s-a produs sau nu. Initial este 0 (evenimentul nu s-a produs) si devine 1 cand evenimentul are loc (elementul a fost gasit). Este un tipar foarte folosit in programare pentru a tine minte daca ceva s-a intamplat in timpul unei parcurgeri.

Nu suntem obligati sa vizitam fiecare element. Putem parcurge sirul cu un pas diferit de 1, vizitand doar anumite pozitii. De exemplu, cu pasul 2 vizitam doar pozitiile impare (1, 3, 5, ...) sau doar pozitiile pare (2, 4, 6, ...).

La fel, pentru a afisa doar elementele de pe pozitii pare, pornim de la 2: PENTRU i = 2, n, 2 EXECUTA SCRIE(v[i]) . In acest caz, contorul ia valorile 2, 4, 6, deci se afiseaza 12, 3, 7.

Parcurgerea cu pas diferit este utila in situatii practice. De exemplu, intr-un sir care contine alternativ numele si prenumele unor persoane (v[1]="Pop", v[2]="Maria", v[3]="Ionescu", v[4]="Elena"), putem afisa doar numele de familie (pozitii impare: v[1]="Pop", v[3]="Ionescu") sau doar prenumele (pozitii pare: v[2]="Maria", v[4]="Elena") folosind pasul 2.

Putem combina parcurgerea cu pas cu alte operatii. De exemplu, sa calculam suma elementelor de pe pozitii impare: s=0; PENTRU i=1,n,2 EXECUTA s=s+v[i] . Sau sa numaram cate elemente de pe pozitii pare sunt negative: c=0; PENTRU i=2,n,2 EXECUTA DACA v[i]<0 ATUNCI c=c+1 . Pasul poate fi si 3, 4 sau orice alta valoare - depinde de problema pe care o rezolvi.

In atomul 7 ai invatat variabila fanion (flag): o variabila care incepe cu 0 si devine 1 cand un eveniment s-a produs in timpul parcurgerii. Acum aplicam exact acelasi tipar, dar pentru o intrebare diferita: sunt toti vecinii in ordine crescatoare? Inainte sa continui, asigura-te ca intelegi atomul 7 — tehnica de mai jos este aceeasi idee, aplicata la perechi de elemente, nu la un element izolat.

O tehnica avansata este sa comparam fiecare element cu vecinul sau din sir. Elementele vecine sunt cele aflate pe pozitii consecutive: v[i] si v[i+1]. Aceasta comparatie ne permite sa detectam schimbari, tranzitii sau relatii intre elemente consecutive.

Observa un detaliu foarte important: bucla merge de la 1 la n-1 , nu pana la n. De ce? Deoarece la fiecare pas comparam v[i] cu v[i+1]. Daca i ar ajunge la n, am incerca sa accesam v[n+1], care nu exista! Aceasta ar fi o eroare grava. De aceea, cand comparam elemente vecine, ne oprim cu un pas mai devreme.

Sa vedem si un exemplu unde sirul NU este sortat: v = [3, 8, 5, 12]. La i=1: 3>8? NU. La i=2: 8>5? DA! Marcam sortat=0. La i=3: 5>12? NU. La final, sortat=0, deci sirul nu este sortat crescator. A fost suficient sa gasim o singura pereche de vecini in ordine gresita pentru a concluziona ca sirul nu este sortat.

Compararea vecinilor este fundamentala pentru mai multi algoritmi importanti: verificarea daca un sir este sortat (crescator sau descrescator), numararea perechilor de elemente consecutive egale, gasirea celui mai mare salt intre doua elemente consecutive, si chiar sortarea sirurilor (algoritmul Bubble Sort se bazeaza pe interschimbarea vecinilor care sunt in ordine gresita).

Sa recapitulam toate tipurile de parcurgere si tiparele pe care le-am invatat in aceasta lectie. Fiecare tipar rezolva un tip diferit de problema si le vei folosi frecvent in lectiile urmatoare.

Doua directii de parcurgere:

Cinci tipare fundamentale in timpul parcurgerii:

• Afisarea elementelor: SCRIE(v[i]) - cel mai simplu tipar
• Modificarea elementelor: v[i] = v[i] * 2 - transformam valorile
• Numararea cu conditie: contor = contor + 1 - numaram elementele cu o proprietate
• Afisarea selectiva : DACA conditie ATUNCI SCRIE(v[i]) - afisam doar unele
• Cautarea : verificam daca un element exista si unde se afla

Aceste cinci tipare sunt "caramizile" din care se construiesc algoritmi mai complecsi. In lectiile urmatoare, vei folosi parcurgerea pentru a calcula sume, medii, maxime si minime. Toate aceste operatii se bazeaza pe parcurgerea pe care ai invatat-o astazi.

In programarea reala, parcurgerea este operatia de baza pe care se construieste totul. Un programator profesionist parcurge siruri de zeci de ori pe zi: liste de utilizatori, date dintr-o baza de date, pixeli dintr-o imagine, caractere dintr-un text. Fiecare dintre aceste operatii foloseste exact aceleasi tipare pe care le-ai invatat astazi. Stapaneste parcurgerea si vei putea rezolva orice problema cu siruri!