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 secventiala 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 secventiala rapida
Cautarea secventiala 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 secventiala 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();
Politica de confidentialitate |
.com | Copyright ©
2024 - Toate drepturile rezervate. Toate documentele au caracter informativ cu scop educational. |
Personaje din literatura |
Baltagul – caracterizarea personajelor |
Caracterizare Alexandru Lapusneanul |
Caracterizarea lui Gavilescu |
Caracterizarea personajelor negative din basmul |
Tehnica si mecanica |
Cuplaje - definitii. notatii. exemple. repere istorice. |
Actionare macara |
Reprezentarea si cotarea filetelor |
Geografie |
Turismul pe terra |
Vulcanii Și mediul |
Padurile pe terra si industrializarea lemnului |
Termeni si conditii |
Contact |
Creeaza si tu |