Fusione senza ripetizioni

1992 – Maturità scientifica PNI

Si desidera fondere due sequenze A e B di numeri interi, non ordinate e con eventuali valori ripetuti, in un’unica sequenza C nella quale compaiono, in ordine crescente e senza ripetizioni, i valori presenti in A e in B.

Il candidato formulate le ipotesi aggiuntive che ritiene necessarie, proponga ed illustri una procedura per risolvere il problema e la codifichi in un linguaggio di sua conoscenza.

Ipotesi aggiuntive

1. A e B sono due vettori di numeri casuali
2. il numero finale di elementi è 1000
3. per brevità si utilizza il metodo qsort() in <stdlib.h>

#include 
#include 
#define MAX 1000
 
void genera(int *, int);
void vedi(int *, int);
int  confronta(const void *, const void *);
int  fusione(int *, int, int *, int, int *, int *);
void noripetizioni(int *, int *);
/* -------------------------------------------------------------------------- */
int main()
{  
    int A[MAX];
    int n1=MAX/2;
    genera(A, n1);                         vedi(A, n1);
    
    int B[MAX];
    int n2=MAX/2;
    genera(B, n2);                         vedi(B, n1);    
                                                                 
    qsort(A, n1, sizeof(int), confronta);  vedi(A, n1);    // ELABORAZIONE     
    qsort(B, n2, sizeof(int), confronta);  vedi(B, n2);  
 
    int C[MAX];
    int n3;
    fusione(A, n1, B, n2, C, &n3);         vedi(C, n3);
    noripetizioni(C, &n3);                 vedi(C, n3);
 
    return 0;
}
/* -------------------------------------------------------------------------- */
void genera(int *v, int n)
{
    for(int i=0; i < n; i++)
       v[i]=rand()%MAX;
}
void vedi(int *v, int n)
{
     for(int i=0; i < n; i++)
         printf("%d ", v[i]);
     getchar();
}
int confronta(const void *a, const void *b)
{
     int x=*(int *)a;
     int y=*(int *)b;
     
     return x-y;
}
int fusione(int *v1, int n1, int *v2, int n2, int *v3, int *n3)
{
    int i1=0, i2=0, i3=0;   
    *n3=n1+n2;
    
    while(i1 < n1 && i2 < n2)
    {
       if(v1[i1] <= v2[i2])
       {
          v3[i3]=v1[i1];
          i1++;
       }
       else
       {
          v3[i3]=v2[i2];
          i2++;
       }
       i3++;
    }
    while(i1 < n1)
    {
       v3[i3]=v1[i1];
       i1++;
       i3++;
    }
    while(i2 < n2)
    {
       v3[i3]=v2[i2];
       i2++;
       i3++;
    }
}
void noripetizioni(int *v, int *n)
{
    int primo=0;
    for(int i=1; i < *n; i++)
    {
        if(v[i] > v[primo])
        {
            primo++;
            v[primo]=v[i];
        }
    }
    *n=primo+1;
}

Le funzioni fusione() e noripetizioni() possono essere unite in fusione_noripetizioni().
Ipotesi aggiuntiva: v1 e v2 non sono vuoti.

int fusione_noripetizioni(int *v1, int n1, int *v2, int n2, int *v3, int *n3)
{
    int i1=0, i2=0, i3=0;   
 
    if(v1[i1] <= v2[i2])
    {
       v3[i3]=v1[i1];
       i1++;
    }
    else
    {
       v3[i3]=v2[i2];
       i2++;
    }
 
    while(i1 < n1 && i2 < n2)
    {
       if(v1[i1] <= v2[i2])
       {
          if(v1[i1] > v3[i3])
          {
              i3++;
              v3[i3]=v1[i1];
          }
          i1++;
       }
       else
       {
          if(v2[i2] > v3[i3])
          {
              i3++;
              v3[i3]=v2[i2];
          }
          i2++;
       }
    }
    while(i1 < n1)
    {
       if(v1[i1] > v3[i3])
       {
          i3++;
          v3[i3]=v1[i1];
       }
       i1++;
    }
    while(i2 < n2)
    {
       if(v2[i2] > v3[i3])
       {
          i3++;
          v3[i3]=v2[i2];
       }
       i2++;
    }
    *n3=i3+1;
}