ALGORITMI DE CAUTARE



Algoritmi de cautare


Cautare secventiala


Algoritmul de cautare secventiala rezolva urmatoarea problema: daca x[n] este un vector cu valori oarecare sa se decida daca o valoare oarecare a se afla printre elementele vectorului x. Cautarea se numeste secvential 9; deoarece, pentru aflarea raspunsului, vectorul x este parcurs secvential incepand cu prima componenta pana cand este intalnita prima aparitie a valorii a (cautarea a avut succes) sau pana cand vectorul x a fost epuizat (cautarea nu a avut succes).




Implementare in limbajul C


# include 'stdio.h'

# include 'conio.h'


int x[20],n,i,a;


int CautSecv(int n,int x[],int a)



void main(void)


printf('nafisare vector: ');

for (i=1;i<=n;i++)

printf('%d ',x[i]);

printf('na=');

scanf('%d',&a);

if (CautSecv(n,x,a))

printf('Valoarea se afla printre elementele sirului');

else printf('Valoarea nu se afla printre elementele sirului');

getch();


Cautare secvential 9; rapida


Cautarea secvential 9; poate deveni « rapida » daca modificam putin algoritmul deja prezentat. Modificarea consta in completarea vectorului x pe componenta x[n+1] cu valoarea a pe care dorim sa o cautam in x[n]. Asa cum se poate constata in implementare de mai jos, numarul de comparatii se reduce substantial : adaugarea valorii a pe pozitia x[n+1] a permis eliminarea comparatiei i<=n care depisteaza sfarsitul sirului x.


Implementare in limbajul C


# include 'stdio.h'

# include 'conio.h'


int x[20],n,i,a;


int CautSecv(int n,int x[],int a)



void main(void)


printf('nafisare vector: ');

for (i=1;i<=n;i++)

printf('%d ',x[i]);

printf('na=');

scanf('%d',&a);

if (CautSecv(n,x,a))

printf('Valoarea se afla printre elementele sirului');

else printf('Valoarea nu se afla printre elementele sirului');

getch();


Cautare secvential 9; in tabel ordonat


In situatia in care elementele vectorului sunt ordonate cautarea se poate face mult mai eficient. Astfel, daca sirul este ordonat crescator este suficient sa cautam valoarea a in vectorul x doar cat timp a>x[i], i=1,2,…. Daca exista o valoare i astfel incat a<x[i] nu are rost sa cautam mai departe deoarece sirul fiind ordonat crescator, toate valorile x[j] cu j>i vor fi strict mai mari decat a.


Implementare in limbajul C


# include 'stdio.h'

# include 'conio.h'


int x[20],n,i,a;


int CautSecvTabOrd(int n,int x[],int a)



void main(void)


printf('nafisare vector: ');

for (i=1;i<=n;i++)

printf('%d ',x[i]);

printf('na=');

scanf('%d',&a);

if (CautSecvTabOrd(n,x,a))

printf('Valoarea se afla printre elementele sirului');

else printf('Valoarea nu se afla printre elementele sirului');

getch();


Cautare binara


efectueaza atribuirile inc=1, sf=n, gasit=0

cat timp inc<=sf si gasit = 0 executa

gaseste pozitia m=(inc+sf)/2care marcheaza mijlocul subvectorului cu elementele x[inc], x[inc+1],…, x[sf]

daca x[m] este egal cu a atunci gasit=1, altfel

daca x[m]>aux atunci cautarea se continua in zona cuprinsa intre pozitia inc si m-1, in caz contrar cautarea se continua in zona cuprinsa intre m+1 si sf


Implementare in limbajul C


# include 'stdio.h'

# include 'conio.h'


int x[20],n,i,a;


int CautBin(int x[],int a)


return gasit;



void main(void)


printf('nafisare vector: ');

for (i=1;i<=n;i++)

printf('%d ',x[i]);

printf('na=');

scanf('%d',&a);

if (CautBin(x,a))

printf('Valoarea se afla printre elementele sirului');

else printf('Valoarea nu se afla printre elementele sirului');

getch();













Copyright © Contact | Trimite referat


Ultimele referate adaugate
Mihai Beniuc
   - Mihai beniuc - „poezii"
Mihai Eminescu Mihai Eminescu
   - Mihai eminescu - student la berlin
Mircea Eliade Mircea Eliade
   - Mircea Eliade - Mioara Nazdravana (mioriţa)
Vasile Alecsandri Vasile Alecsandri
   - Chirita in provintie de Vasile Alecsandri -expunerea subiectului
Emil Girlenu Emil Girlenu
   - Dragoste de viata de Jack London
Ion Luca Caragiale Ion Luca Caragiale
   - Triumful talentului… (reproducere) de Ion Luca Caragiale
Mircea Eliade Mircea Eliade
   - Fantasticul in proza lui Mircea Eliade - La tiganci
Mihai Eminescu Mihai Eminescu
   - „Personalitate creatoare” si „figura a spiritului creator” eminescian
George Calinescu George Calinescu
   - Enigma Otiliei de George Calinescu - geneza, subiectul si tema romanului
Liviu Rebreanu Liviu Rebreanu
   - Arta literara in romanul Ion, - Liviu Rebreanu











Scriitori romani