Clasa a IX-a lecția 21

Operatii cu multimi

Recapitulare - Căutare în vector

Se dă un vector v de n elemente și un extra element e. Să se găsească poziția p în v unde apare prima oară elementul e. Dacă elementul e nu apare p va avea valoarea n. O soluție elegantă care nu iese forțat din buclă și care nu folosește stegulețe este:

// avem vectorul v de n elemente si o valoare e de gasit in acest vector
p = 0;
while ( p < n && v[p] != e )
  p++;
// acum p este fie pozitia primei aparitii a lui e, fie n daca e nu exista in v

Diferenta a doua multimi

Diferenta a doua multimi A-B reprezinta elementele din multimea A care nu se gasesc si in multimea B.

#include <stdio.h>
#include <stdlib.h>

int a[10000], int b[10000], c[10000];

int main(){
  FILE*fin, *fout;
  int n1, n2, k, i, j;
  fin = fopen( "diferenta.in", "r" );
  fout = fopen( "diferenta.out", "w" );

  fscanf( fin, "%d", &n1 );
  for (i = 0; i < n1; i ++ )
    fscanf( fin, "%d", &a[i] );
  fscanf(fin, "%d", &n2 );
  for ( i = 0; i < n2; i ++ )
    fscanf( fin, "%d", &b[i] );
    
  k = 0;   //numarul de elemente din A-B
  for ( i = 0; i < n1; i++ ){
    //caut a[i] in b
    j = 0;
    while( j < n2 && a[i] != b[j]  )
      j ++;

    // daca nu l-am gasit in b il pun in c
    if( j == n2 )
      c[k++] = a[i];
  }

  for (i = 0;i < k; i++)
    fprintf( fout, "%d ", c[i] );
   
  return 0;
}

Reuniunea a doua multimi

Reuniunea a doua multimi reprezinta toate elementele din A-B la care adaugam elementele din B

#include <stdio.h>
#include <stdlib.h>

int a[10000], b[10000], c[20000];

int main(){
  FILE *fin, *fout;
  int n1, n2, k ,i , j;
  fin=fopen("reuniune.in", "r");
  fout=fopen("reuniune.out", "w");
   fscanf( fin, "%d", &n1 );
   for( i = 0; i < n1; i++ )
     fscanf( fin, "%d", &a[i] );
   fscanf(fin, "%d", &n2 );
   for ( i = 0; i < n2; i++ )
     fscanf(fin,"%d",&b[i]);
 
 
   k = 0;//numarul de elemente din v3
   for ( i = 0; i < n1; i++ ){

     //caut v1[i] in v2
     j = 0;
     while( j < n2 && a[i] != b[j]  )
        j++;

     // daca nu l-am gasit in v2 il pun in v3
     if (j == n2)
       c[k++] = a[i];
   }

  //adugam elementele din b incepand cu pozitia k la care am ramas  
  for( i = 0;i < n2; i++ )
    c[k++] = b[i];

  //tiparim vectorul solutie
  for ( i = 0;i < k; i++ )
    fprintf(fout,"%d ", c[i]);
  
  fclose( fin );
  fclose( fout );
  return 0;
}

Intersectia a doua multimi

#include <stdio.h>
#include <stdlib.h>

int a[10000];
int b[10000];
int c[10000];

int main(){
   FILE*fin, *fout;
   int n1, n2, k, i, j;
   fin = fopen("intersectie.in","r");
   fout = fopen("intersectie.out","w");
   fscanf( fin, "%d", &n1 );
   for (i = 0; i < n1; i++ )
      fscanf( fin, "%d", &a[i] );
   fscanf(fin, "%d", &n2 );
   for (i=0; i<n2; i++)
    fscanf(fin,"%d",&b[i]);
    //calculam intersectia multimilor:a si b
    //parcurgem multimea a si pentru fiecare element din a verificam daca se gaseste in b
    //si daca nu se gaseste in b il punem in c
    k = 0;//numarul de elemente din c
    for (i=0;i<n1;i++){
     //caut a[i] in b
     j = 0;
     while( j<n2 && a[i]!=b[j]  )
        j++;

    // daca l-am gasit in b il pun in c
    if (j < n2)
      c[k++] = a[i];
    }
    for (i=0;i<k;i++)
      fprintf(fout,"%d ",c[i]);
   return 0;
}

Produsul cartezian a doua multimi

#include <stdio.h>
#include <stdlib.h>

int a[10000];
int b[10000];
int c[10000];

int main(){
   FILE*fin, *fout;
   int n1, n2, i, j;
   fin = fopen("cartezian.in","r");
   fout = fopen("cartezian.out","w");

   fscanf( fin, "%d", &n1 );
   for (i = 0; i < n1; i++ )
      fscanf( fin, "%d", &a[i] );

   fscanf(fin, "%d", &n2 );
   for (i=0; i<n2; i++)
    fscanf(fin,"%d",&b[i]);


  for (i=0;i<n1;i++){
     for(j=0;j<n2;j++)
      fprintf(fout,"(%d,%d)",a[i],b[j]);
    }

   return 0;
}

Căutare binară

Căutarea binară este un mod mai rapid de a căuta pe ce poziție se află un element într-un vector.

Ce complexitate are căutarea clasică a unui element într-un vector? Deoarece elementul se poate afla pe orice poziție în vector, iar noi căutăm liniar elementele, unul după altul, rezultă că, pe medie, vom face n / 2 comparații atunci cînd elementul se află în vector. Aceasta înseamnă o complexitate de O(n). Putem să rezolvăm această problemă mai rapid?

Putem, cu condiția ca vectorul să fie ordonat. Să ne folosim de o analogie: cum căutam un cuvînt în dicționar? Dicționarul are circa 60000 de cuvinte. Dacă am căuta la rînd, liniar, ne-ar lua zile să-l găsim. Și atunci deschidem dicționarul undeva, să spunem la mijloc. Ne uităm la ce literă sîntem, să spunem 'm'. Dacă noi căutăm 'gorilă', știm că 'g' < 'm', deci vom căuta la stînga, eliminînd jumate din dicționar. Vom continua la fel, deschidem undeva la jumate în jumatea rămasă și vedem iarăși la ce literă sîntem. Atunci cînd ajungem la litera 'g' vom continua cu a doua literă. În acest fel vom găsi cuvîntul rapid, probabil în jumate de minut, în loc de zile.

Aceasta este metoda căutării binare. Dacă vectorul nostru este ordonat, putem căuta mai întîi la jumate. Dacă elementul din vector este mai mic decît elementul căutat înseamnă că trebuie să ne uităm în jumătatea dreaptă, altfel ne uităm în cea stîngă. Apoi, în vectorul rămas, vom repeta algoritmul. La fiecare pas vom înjumătăți numărul de numere rămase. Ne oprim atunci cînd subvectorul rămas are fix un element. Dacă este elementul căutat, returnăm poziția sa, altfel el nu există. Iată o implementare posibilă:

Atenție: stinga este prima poziție in vectorul căutat, iar dreapta este prima poziție în afara vectorului căutat. Dacă respectați această convenție evitați bug-urile de final de căutare cînd indicii rămîn pe loc și o condiție incorectă in while poate să ducă la o buclă infinită.

#include <stdio.h>

int main(){
  int n, i, m, val, st, dr, gasit, mij;
    scanf( "%d", &val );
    st = 0;
    dr = n - 1;
    gasit = 0;
    while( st <= dr && !gasit ) {
        mij = ( st + dr ) / 2;
        if( val == v[mij] )
            gasit = 1;
        else if( val < v[mij] )
            dr = mij - 1;
        else
            st = mij + 1;
    }
    printf( "%d ", gasit );
  }

  return 0;
}