luni, 24 septembrie 2012

Prelucrari elementare IV


Algoritmul de căutare binară. Se consideră un vector oarecare A cu n elemente şi o valoare x. Se cere să se verifice dacă x apare printre elementele vectorului sau nu. Dacă lucrăm cu un vector oarecare, se vor compara pe rând elementele acestuia cu valoarea căutată x. Sunt necesare cel mult n comparaţii în caz de succes (x apare în vector) şi exact n comparaţii în caz de eşec (x nu apare în vector). În cazul în care vectorul este ordonat crescător sau descrescător se poate folosi un algoritm de căutare mult mai eficient având complexitatea log2n. Acest algoritm se numeşte “algoritmul de căutare binară” şi poate fi descris astfel : iniţial se consideră tot vectorul A şi se compară x cu elementul din mijlocul acestuia (fie el a[mij]). Dacă x=a[mij], algoritmul se încheie cu succes; dacă x, vectorul fiind ordonat, căutarea va continua în prima jumătate, iar dacă x>a[mij] căutarea va continua în a doua jumătate. Procedeul se repetă până când fie găsim valoarea x, fie nu mai avem secvenţă validă de căutare, adică elemente neverificate. Secvenţa curentă în care se face căutarea elementului x este identificată prin indicele elementului din extrema stângă, respectiv indicele elementului din extrema dreaptă. Secvenţa de program este următoarea :
f=-1;   /* x nu a fost găsit în vectorul A */
st=0; dr=n-1;    /* secvenţa iniţială de căutare este întregul vector A */
while(st<=dr)     
 /* secvenţa curentă de căutare conţine cel puţin un element */
{      mij=(st+dr)/2;   
       /* indicele elementului din mijlocul secvenţei de căutare */
   if(a[mij]==x)
   {  f=mij;     /* memorăm poziţia în care apare */
             break;     /* căutare încheiată cu succes */
   }
   if(x<
-->a[mij])
      dr=mij-1;    /* căutarea continuă în prima jumătate */
   else
      st=mij+1;    /* căutarea continuă în a doua jumătate */
}    


Interclasarea vectorilor. Se consideră doi vectori, A cu m elemente şi B cu n elemente, ambii ordonaţi crescător sau descrescător. A interclasa  cei doi vectori înseamnă a obţine un vector C cu m+n elemente, care conţine toate elementele din A şi din B, ordonate în acelaşi mod. Metoda de creare a vectorului rezultat C este foarte simplă: se compară elementul curent din A cu elementul curent din B, în C se introduce spre exemplu cel mai mic dintre ele (la ordonare crescătoare). Dacă elementul introdus a fost din vectorul A atunci se avansează la următorul element din A, altfel se avansează la următorul element din vectorul B. În momentul în care elementele unui vector sunt epuizate, elementele rămase în celălalt vector  sunt copiate direct în vectorul C. Acest algoritm se simplifică dacă folosim două “santinele” care vor face ca cei doi vectori să se epuizeze simultan. O santinelă este un element care nu influenţează valoarea unui rezultat, scopul utilizării lui fiind numai obţinerea unui algoritm mai simplu şi mai eficient. În cazul algoritmului de interclasare, vom adăuga la sfârşitul vectorului A o santinelă mai mare decât cel mai mare element din B, iar la sfârşitul vectorului B o santinelă mai mare decât cel mai mare element din A. În acest caz, dacă presupunem că toate elementele utile din vectorul A au fost deja introduse în vectorul rezultat C, atunci, toate elementele utile din B care nu au fost încă verificate sunt mai mici decât santinela rămasă în A şi vor fi copiate automat, fără nici-o verificare suplimentară, în vectorul rezultat C.  Secvenţa care realizează interclasarea cu santinele este:
a[m]=b[n]+1; 
 /* santinela din A mai mare decât cel mai mare element din B */
b[n]=a[m]+1;  
/* santinela din B mai mare decât cel mai mare element din A */
i=0;                        /* indicele elementului curent din A */
j=0;                        /* indicele elementului curent din B */
-->for(k=0; k< -->m+n; k++)    /* k este indicele elementului curent din C */
   if(a[i]<
-->b[j])   /* pentru ordonare crescătoare */
        c[k]=a[i++];            /* avansez în vectorul A */
   else
    c[k]=b[j++];           /* avansez în vectorul B */