Cautarea Binara a unui Element intr-un Vector

GRUPA VI: ECHIPA TIMBIRA Membrii: Pop Paula Varga AndradaVoas BiancaPrunean Raazvan

MEMBRII ECHIPEI Si Rolul Lor: Varga

andrada :DOcumentare si conceperea machetei PPT

Voas Bianca: Editarea documentelor PPT

Prunean Razvan: Grafica PPT si pagina WIKI

Pop Paula: Coordonatorul echipei

Presupunem ca sirul este memorat intr-un vector ( x[1], x[2],..., x[n]) , unde n este nr de elemente. Descompunem programul in 3 subprograme de acelasi tip:o problema reprezentata de o singura valoare, si anume aceea din mijloc: x[mij], unde mij este pozitia de mijloc, mij = (p+q)/2Doua probleme reprezentate de subvectorul stang , respectiv drept:( x[1],x[2],.....,x[mij-1] ) si ( x[mij+1], x[2],...., x[n] ),  Implementarea propriu-zisa va analiza problemele in aceasta ordine. Se observa ca am sugerat aplicarea unui algoritm Divide et Impera in care prima problema este elementara, iar urmatoarele doua sunt de acelasi tip cu cea initiala. Deoarece problema noastra este o problema de cautare putem descrie complet algoritmul astfel:Daca valoarea cautata se afla pe pozitia de mijloc (a=x[mij]) , atunci algoritmul se incheie;Daca valoarea cautata este mai mica decat elementul de pe pozitia de mijloc (a<x[mij]) , atunci cautarea continua in subvectorul stang (x[1],x[2],..., x[mij-1]) , deoarece toate elementele mai mici decat cel din mijloc se gasesc in stanga acestuia (vectorul este sortat crescator! );Daca valoarea cautata este mai mare decat elementul de pe pozitia de mijloc (a>x[mij]) , atunci cautarea continua in subvectorul drept (x[mij+1], x[2],....,x[n]) ;Cautarile in fiecare din cei doi subvectori se fac prin acelasi procedeu de descompunere a problemei, pana cand gasim valoarea cautata pe o pozitie de mijloc, sau pana cand ajungem la un subvector care nu contine nici un element.

Sa analizam problema elementara : x[mij]=a, adica x[5]=8, moment in care algoritmul se incheie deoarece valoarea cautata a fost gasita. Presupunem acuma ca valoarea cautata ar fi a=7. Algoritmul ar fi identic cu cel de mai sus pana la obtinerea subprogramului date de elementul x[5] si subvectorii (x21) si x(22) . Mai departe insa, problema elementara "x[mij]" nu mai furnizeaza solutia. Intrucat a<x[mij] (7<8) , trebuie continuat cu descompunerea subvectorului x(21) .

Avem: p=q=4, mij[(p+q)/2]=[(4+4)/2]= 4 ; primul subvector ar fi

cuprins intre pozitiile p=4 si q=mij-1=3, iar al doilea intre pozitiile p=mij+1=5 si q=4. Acesti noi subvectori nu se mai pot descompune in continuare, pentru ca ... nu sunt "valizi". V-ati dat seama ca am ajuns la subvectori care nu contin nici un element, si credem ca se observa cu usurinta conditia care defineste aceasta situatie: q<p !

Rezolvare Consideram o functie recursiva

{div_imp(p,q:integer):boolean;} care returneaza : false daca valoarea a nu exista in subvectorul (x[p], ... , x[q]), respectiv true daca aceasta exista in subvector.

La un anumit pas al algoritmului recursiv, cautam valoarea a intr-un subvector (x[p], ... , x[q]) cuprins intre pozitiile p si q .

  Daca subvectorul nu contine nici un element ( q<p, asa

cum am aratat mai sus). atunci abandonam cautarea, functia returnand valoarea false :

if q<p then div_imp:=false ; In caz contrar: determinam pozitia de miljoc : {mij:=(p+q)

div 2;} . Apoi analizam cele trei subprobleme, in ordine:

1. verificam daca valoarea a coincide cu x[mij] ; in caz afirmativ, cautarea se opreste : {if x[mij]=a then div_imp:=true}

2. in caz contrar: a) daca a este mai mic decat x[mij], atunci

valoarea a trebuie cautata in subvectorul din stanga (x[p], ... ,x[mij-1]) ; avand in vedere ca algoritmul va fi acelasi cu singura deosebire ca in loc de q vom avea mij-1 , rezulta ca este suficient sa apelam div_imp(p,mij-1);

b) daca a este mai mare decat x[mij], atunci valoarea a trebuie cautata in subvectorul din dreapta (x[mij+1], ... , x[q]) ; pentru aceasta apelam div_imp(mij+1,q) ;

if x<x[mij] then div_imp:=div_imp(p,mij-1) else div_imp:=div_imp(mij+1,q) ;  

Cautarea binara intr-un sir Sa se verifice daca o valoare a exista intr-un sir de nr ordonat crescator. Se va folsi un algoritm bazat pe

Metoda Divide et Impera.   program RIV_15; uses crt; type vector=array [1..20] of integer; var x:vector; n,a,i:integer; function div_imp (p,q:integer): boolean; {cauta o valoare v in subvectorul cuprins intre pozitiile p si q din vectorul x} var mij:integer; begin if q<p then {daca subvectorul nu contine nici un element} div_imp:=false {valoarea v nu exista in subvectorul x[p], ... , x[q] } else begin mij:=(p+q) div 2; {determina pozitia de mijloc} if x[mij]=a then div_imp:=true {valoarea v a fost gasita chiar pe pozitia de mijloc} else {daca v este mai mic decat elem. din mijloc, cautam in subvectorul x[p], ... , x[mij-1] } {in caz contrat, cautam in subvectorul x[mij+1], ... , x[q] } if a<x[mij] then div_imp:=div_imp (p,mij-1) else div_imp:=div_imp(mij+1,q); end; end; begin clrscr; write('n='); readln(n); {citeste numarul n si elementele vectorului x} write ('x[1]='); readln (x[1]); for i:= 2 to n do repeat write('x[',i,']='): readln (x[i]); until x[i]>x[i-1]; write ('a='); readln(a); {citeste valoarea a} writeln(div_imp(1,n) ); {cauta valoarea a in vectorul dat} readln; end.

1. Programul urmator afiseaza valoarea . . . . const v:array[1..7] of integer=(2,4,1,3,11,5,1,3); function impar(m,n:integer) : integer; beginif n=m then impar:= v[n] mod 2 else impar:= impar(n,(n+m) div 2) +

impar ( (n+m) div 2+1,m); end;   begin writeln(impar (0,7) ); end.   Raspuns : 7

  2. Ce valoare afiseaza programul urmator? var v:array[1..50] of integer; i:integer; function m(a,b:byte):longint; begin if a>b then m:=0 else if a=b then m:=v[a] else m:=m(a, (a+b) div 2) + m ( (a+b) div

2+1,b); end;   begin for i:=1 to 10 do v[i]:=i; writeln(m (3,8) ); end.   a) 3 b) 33 c) 0 d) 8 e) 24