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 */ 
     

Partitionarea unui vector


În multe aplicații se cere ca elementele unui vector să fie rearanjate astfel încât elementele care au o anumită proprietate să apară înaintea celor care nu au proprietatea respectivă.
De exemplu să se rearanjeze elementele unui vector cu numere întregi astfel încît valorile pare să apară înaintea celor impare. Desigur există multe soluții pentru rezolvarea acestui gen de probleme. Oferim în continuare o soluție de complexitate O(n) (liniară) care nu folosește memorie suplimentară.

j=0; //prima pozitie disponibila pentru elementele pare
pentru(i=0; i<n; i++)
   if(a[i]%2==0)  //elementul trebuie sa apara in prima parte a vectorului
   {
         aux=a[j]; a[j]=a[i]; a[i]=aux; j++;
    }

Practic, prin interschimbarea elementului a[i] cu elementul a[j], elementele pare ajung în prima parte a vectorului, iar cele impare în a doua parte a vectorului, adică vectorul este partiționat .

Vectori de frecventa


O utilizare interesantă a vectorilor este pentru a determina frecvența de apariție a unor valori dintr-un domeniu dat printre datele de intrare ale unei aplicații.
Să considerăm, de exemplu, că se dă un fișier text care conține maxim 1 milion de valori din mulțimea 0..9 (cifre zecimale), valorile fiind separate prin câte un spațiu  și se cere să determinăm pentru fiecare cifră zecimală numărul de apariții (frecvența) în fișierul text.
Desigur că utilizarea unui vector cu 1 milion de elemente (chiar dacă le declarăm de tip char sau unsigned char) este prohibită din cauza consumului execesiv de memorie și lipsită de sens. De fapt este vorba doar de 10 valori distincte (cifrele zecimale) care contează. O soluție eficientă, care conduce la un algoritm liniar de rezolvare, este să asociem primii zece indici din tablou celor zece valori distincte posibile. În acest fel semnificația elementelor tabloului devine:
  • a[0] - frecventa de aparitie a valorii 0 in fisier
  • a[1] - frecventa de aparitie a valorii 1 in fisier
  • .....
  • a[9] - frecventa de aparitie a valorii 9 in fisier
După construirea vectorului de frecvențe este suficient să listăm valorile și a[i] pentru i=0,1,...9 și problema este rezolvată.
Programul C++ complet este:

#include<iostream.h>
#include<fstream.h>
int main()
{
     unsigned char x,i;
     long unsigned a[10]={0};  //tabloul frecventelor initializat cu 0
     ifstream f("date.in");
     while(!f.eof())
     {
         f>>x; a[x]++;  //creste frecventa valorii x
     }
     f.close();
     for(i=0; i<10; i++)
         cout<<i<<"  apare de "<<a[i]<<"  ori in fisier"<<endl;
     return 0;
}

Vectorul de frecvență este numit uneori și vector de marcare deoarece poate fi folosit pentru a determina valorile distincte care apar (sau care nu apar) printre datele de intrare ale unei aplicații.
Exemplu: Se consideră un fișier text care conține maxim 100000 de numere naturale <=6000. Să se afișeze valorile din mulțimea 0..100 care nu apar în fișier
Deși numărul valorilor din fișier este foarte mare și valorile posibile sunt cuprinse între limitele 0 și 60000 (deci 60001 valori distincte posibile), singurele valori care contează pentru rezolvarea problemei sunt 0, 1...100, adică 101 valori distincte. Asociem fiecărei valori din mulțimea 0..100 un element în tabloul cu următoarea semnificație:
  • a[i]=0 - dacă valoarea lipsește din fișier
  • a[i]=1 - dacă valoarea apare cel puțin o dată în fișier
pentru fiecare i=0, 1, ...100.
Listând valorile pentru care a[i]=0 după citirea tuturor valorilor din fișier obținem valorile din mulțimea 0,1...100 care lipsesc din fișier. În rezolvarea acestei probleme vectorul a devenit un vector de marcare (marchează starea binară a unui element, de exemplu cu semnificația apare/nu apare).
Programul C++ complet este:
#include<iostream.h>
#include<fstream.h>
int main()
{
    unsigned x; unsigned char i;
    unsigned char a[101]={0};   //vectorul de marcare initializat cu 0
    ifstream f("date.in");
    while(!f.eof())
   {
       f>>x; 
       if(x<=100) //selectam numai valorile care intereseaza
           a[x]=1;  //marcam valoarea x ca fiind gasita in fisier
   }
   f.close();
   for(i=0; i<=100; i++)
      if(a[i]==0)    //valoarea i nu apare in fisier
          cout<<i<<"   ";
   return 0;
}
Folosirea unui vector de frecvență sau marcare asociat este eficientă numai în cazul în care valorile care interesează sunt întregi și numărul valorilor distincte posibile este cel mult 10000. Uzual folosirea acestui tip de vectori duce la optimizarea consumului de memorie și la obținerea unor algoritmi de rezolvare eficienți.

Sortarea vectorilor


Prin sortarea elementelor unui  vector se înțelege rearanjarea elementelor acestuia fie în ordine crescătoare, fie în ordine descrescătoare. Problema sortării este extrem de importantă în realizarea aplicațiilor practice, din acest motiv există numeroase lucrări de specialitate care studiază algoritmii de sortare și eficiența lor.
Un algoritm de sortare simplu, care are complexitatea O(n*n), este algoritmul de sortare prin selecție directă.  Conform acestui algoritm, se compară toate perechile de valori din vector de forma (a[i], a[j]) cu proprietatea j>i și, dacă este cazul, se interschimbă cele două valori.
Programul următor realizează sortarea crescătoare a unui vector de numere întregi:

#include<iostream.h>
int main()
{
   int a[200], n, i, j, aux;
   cout<<"n="; cin>>n;
   for(i=0; i<n; i++) cin>>a[i];
   //algoritmul de sortare
   for(i=0; i<n-1; i++ )       //selecteaza prima valoare din pereche
      for(j=i+1; j<n; j++)    //selecteaza a doua valoare din pereche cu j>i
        if(a[i]>a[j])              //ordinea nu este respectata
        {  aux=a[i]; a[i]=a[j]; a[j]=aux;  }     //se interschimba valorile
   //afiseaza vectorul sortat
   for(i=0; i<n; i++) cout<<a[i]<<"  ";
   return 0;
}

Algoritmul execută exact n*(n-1)/2 comparații și face maxim n*(n-1)/2 interschimbări, deci complexitatea este O(n*n).

Determinarea platoului maxim dintr-un vector


Prin platou într-un vector se înțelege o secvență de elemente consecutive în vector care au o anumită proprietate, de exemplu o secvență de elemente consecutive egale sau care au aceeași paritate sau care au același semn algebric etc. Platoul maxim este secvența cu număr maxim de elemente. 
Exemplu: secvența de valori
3, 3, 2, 2, 2, 2, 1, 5, 5, 5, 5, 5, 7, 7, 0, 0, 4, 4, 4
conține următoarele platouri de elemente egale:
3, 3
2, 2, 2, 2
1
5, 5, 5, 5, 5
7, 7
0, 0
4, 4, 4
iar platoul maxim este 5, 5, 5, 5, 5 și este complet determinat prin poziția din care începe și lungime (numărul de elemente din platou).
În continuare este prezentat un algoritm liniar care determină platoul maxim cu elemente egale dintr-un vector cu maxim 1000 de valori întregi.

#include<iostream.h>
int main()
{
    int a[1000], n, i, l, lmax, p, pmax;
    cout<<"numarul de elemente din vector, n="; cin>>n;
    for(i=0; i<n; i++)
    {
         cout<<"a["<<i<<"]="; cin>>a[i];
     }
    l=lmax=1; 
    /* prima secventa incepe cu primul element si are momentan lungimea 1 
        care este si lungimea maxima curenta */
    p=pmax=0;
    /* prima secventa incepe din pozitia 0 */
    for(i=1; i<n; i++)
        if(a[i]==a[i-1])  //a[i] face parte din platoul curent
        {
              l++;   //creste lungimea platoului curent
        }
        else  //platoul anterior s-a incheiat
        {
              if(l>lmax)   //platoul anterior este mai lung
              {
                   lmax=l; pmax=p;     //actualizam platoul maxim
               }
               p=i; l=1;   //a[i] face parte dintr-un nou platou
         }
    if(l>lmax)  //pentru ultimul platou, care se incheie cu a[n-1]
    {
          lmax=l; pmax=p;
    }
    cout<<"Platoul maxim are "<<lmax<<" elemente si incepe in pozitia "<<pmax+1;
    return 0;
}