2014 – 5

di

Siano A e B due insiemi di uguale cardinalità N (cioè con uguale numero di elementi) contenenti ciascuno N numeri interi diversi tra loro.
I numeri dei due insiemi A e B vengono memorizzati, ordinati per valori crescenti, nei due vettori v e w.

Si dica che insieme calcola nel vettore z il seguente codice:

int i,j,k,
    v[N],w[N],z[2*N];

i=j=k=0;
while(i < N && j < N)
{
   if(v[i] == w[j]) 
   {
      i++;
      j++;
   }
   else if(v[i] < w[j])
      z[k++]=v[i++];
   else
      z[k++]=w[j++];
}
while(i < N)
   z[k++]=v[i++];
while(j < N)
   z[k++]=w[j++];
  1. A ∪ B
  2. A ∩ B
  3. A ∪ B – A ∩ B
  4. A ∩  B – A ∪ B

Soluzione: c (A ∪ B – A ∩ B)

Si tratta di una rielaborazione dell'algoritmo di fusione ordinata di 2 due sequenze ordinate.

Se i 2 valori confrontati sono uguali allora vengono saltati entrambi.