Introducere in Stiinta Calculatoarelor 2013 | Page 88

6.2.3. Exemple de algoritmi
În continuare, se prezintă câteva exemple de algoritmi, cu descrierea lor
folosind instrucţiunile prezentate pentru controlul fluxului de operaţiuni
iar pentru comunicaţia cu omul (adică pentru afişare) se folosesc
exprimări în cuvinte încadrate de { şi } (acolade). Acest paragraf are ca
scop exemplificarea unor algoritmi concreţi dintre cei mai utilizaţi în
prelucrări uzuale, pentru fiecare exemplu prelucrările fiind grupate întrun subprogram cu nume sugestiv ce poate apelat în alte programe.
Ambele exemple sunt aplicaţii ale metodei „Divide et impera”.
Căutare (logaritmică) binară
Cea mai uzuală prelucrare efectuată cu un sistem de calcul este căutarea
unei piese de date într-o mulţime oarecare – de exemplu date aflate pe
unul din discurile calculatorului sau date aflate în Internet. După cum
s-a arătat, cea mai eficientă căutare are loc atunci când datele sunt
organizate arborescent. O metodă de căutare eficientă – similară celei
în arbore, se poate însă executa şi pe date ordonate secvenţial (după un
criteriu de ordine – alfabetic, numeric), adică date ordonate într-o listă.
Fie exemplul următor: se dă o listă (un tabel) cu date despre studenţi
(număr legitimaţie, nume, prenume, adresă, etc.) ordonate crescător
după numărul de legitimaţie; se doresc informaţii despre un student cu
număr de legitimaţie cunoscut (denumit Tinta). Trebuie remarcat că
înşiruirea de numere de legitimaţie în listă nu este continuă – unii
studenţi au rămas repetenţi, alţii s-au retras, deci secvenţa de numere
are „goluri”.
Metoda de lucru constă în compararea numărului Tinta cu numărul de
la jumătatea listei (element pivot), apoi selectează pentru căutare în
continuare jumătatea superioară sau inferioară – funcţie de rezultatul
comparaţiei. Căutarea se repetă prin înjumătăţire succesivă până la
găsirea liniei numărului Tinta (şi afişarea informaţiilor) sau se constată
inexistenţa lui în listă.
Pentru descrierea algoritmului se consideră Lista (ca depozitar al
informaţiilor despre studenţi) apoi Tinta (ca variabilă ce conţine
numărul de legitimaţie căutat) şi elementul Pivot (valoare aflată la
88