Leggendo un precedente thread ho visto che si parlava di fondere due array di interi in un terzo che risultasse ordinato. Siccome quando ho tempo libero mi diverte tentare di risolvere questo tipo di "enigmi", ho preso spunto da alcuni interventi e ho provato a delineare due soluzioni, in merito alle quali mi piacerebbe sentire qualche commento
costruttivo.
In entrambi i casi ho eliminato due condizioni: 1) gli array originali sono ordinati e 2) negli array compaiono solo valori positivi.
Dunque, fondo due array di interi non ordinati che possono essere sia positivi, sia negativi. Vai col codice!!!
La prima versione non è molto onesta, infatti anziché fondere gli array non ordinati, prima ordina gli array e poi li fonde, aggirando l'ostacolo più che superarlo.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define Q_EL 10 /* Q_EL = quantita' di elementi */
void popola_array( int *a, int *b, size_t q );
int fondi_array_non_preordinati( int *a, int *b, int *e, size_t q );
void fondi_array_preordinati( int *a, int *b, int *e, size_t q );
void visualizza_array( int *a, int *b, int *e, size_t q );
int main() {
int e[2*Q_EL] = {0}; /* e = esito */
int a[Q_EL], b[Q_EL];
popola_array( a, b, Q_EL );
if( fondi_array_non_preordinati(a,b,e,Q_EL) == 0 )
visualizza_array( a, b, e, Q_EL );
else printf( "Si e' verificato un errore.\n\n" );
printf( " Premi \"invio\" per terminare il programma... " );
getchar();
printf( "%s", "\n\n" );
return 0;
}
/* inserisce valori casuali negli array */
void popola_array( int *a, int *b, size_t q ) {
int i;
srand( time(NULL) );
for( i=0; i<q; ++i ) {
a[i] = rand()%19-9; /* valori da -9 a +9 */
b[i] = rand()%19-9; /* valori da -9 a +9 */
}
}
/* usata da qsort() in fondi_array_non_preordinati() */
int confronta_int( const void *p1, const void *p2 ) {
int a=*((int*)p1), b=*((int*)p2);
return a==b ? 0 : (a<b?-1:1);
}
int fondi_array_non_preordinati( int *a, int *b, int *e, size_t q ) {
int *ac = NULL; /* ac = copia di a */
int *bc = NULL; /* bc = copia di b */
int errore = 1; /* presuppone un errore */
ac = malloc( q*sizeof(*ac) );
if( ac ) {
memcpy( ac, a, q*sizeof(*ac) );
bc = malloc( q*sizeof(*bc) );
if( bc ) {
memcpy( bc, b, q*sizeof(*bc) );
qsort( ac, q, sizeof(*ac), confronta_int );
qsort( bc, q, sizeof(*bc), confronta_int );
fondi_array_preordinati( ac, bc, e, q );
errore = 0; /* tutto bene! */
free( bc ); bc = NULL;
}
free( ac ); ac = NULL;
}
return errore;
}
void fondi_array_preordinati( int *a, int *b, int *e, size_t q ) {
int i=0, j=0, c=0; /* contatori */
while( i<q && j<q )
e[c++] = b[j]<a[i] ? b[j++] : a[i++];
while( i<q )
e[c++] = a[i++];
while( j<q )
e[c++] = b[j++];
}
void visualizza_array( int *a, int *b, int *e, size_t q ) {
size_t i;
printf( "\n\n%s", " Array a[]: " );
for( i=0; i<q; ++i ) printf( " %2d", a[i] );
printf( "\n\n%s", " Array b[]: " );
for( i=0; i<q; ++i ) printf( " %2d", b[i] );
printf( "\n\n%s", " Array e[]: " );
for( i=0; i<2*q; ++i ) printf( " %2d", e[i] );
printf( "%s", "\n\n" );
}
La seconda versione prende spunto dal suggerimento di
ettorec, che propone un'idea alla quale non avrei mai pensato.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define Q_EL 10 /* Q_EL = quantita' di elementi */
void popola_array( int *a, int *b, size_t q );
int fondi_array_non_preordinati( int *a, int *b, int *e, size_t q );
void visualizza_array( int *a, int *b, int *e, size_t q );
int main() {
int e[2*Q_EL] = {0}; /* e = esito */
int a[Q_EL], b[Q_EL];
popola_array( a, b, Q_EL );
if( fondi_array_non_preordinati(a,b,e,Q_EL) == 0 )
visualizza_array( a, b, e, Q_EL );
else printf( "Si e' verificato un errore.\n\n" );
printf( " Premi \"invio\" per terminare il programma... " );
getchar();
printf( "%s", "\n\n" );
return 0;
}
/* inserisce valori casuali negli array */
void popola_array( int *a, int *b, size_t q ) {
int i;
srand( time(NULL) );
for( i=0; i<q; ++i ) {
a[i] = rand()%19-9; /* valori da -9 a +9 */
b[i] = rand()%19-9; /* valori da -9 a +9 */
}
}
/* funzione ausiliaria usata da trova_limiti() */
int trova_minimo( int *a, size_t q ) {
int minimo;
size_t i;
for( minimo=*a, i=1; i<q; ++i )
minimo = a[i]<minimo ? a[i]: minimo;
return minimo;
}
/* funzione ausiliaria usata da trova_limiti() */
int trova_massimo( int *a, size_t q ) {
int massimo;
size_t i;
for( massimo=*a, i=1; i<q; ++i )
massimo = a[i]>massimo ? a[i]: massimo;
return massimo;
}
/* funzione ausiliaria usata da fondi_array_non_preordinati() */
void trova_limiti( int *a, int *b, int q, int *min, int *max, size_t *gamma ) {
int t1, t2;
t1 = trova_minimo( a, q );
t2 = trova_minimo( b, q );
*min = t1<t2 ? t1 : t2;
t1 = trova_massimo( a, q );
t2 = trova_massimo( b, q );
*max = t1>t2 ? t1 : t2;
*gamma = 1 + *max - *min;
}
int fondi_array_non_preordinati( int *a, int *b, int *e, size_t q ) {
int errore = 1; /* presuppone un errore */
int min, max;
int *aux = NULL;
size_t i,j, gamma;
trova_limiti( a, b, q, &min, &max, &gamma );
aux = malloc( gamma*sizeof(*aux) );
if( aux ) {
memset( aux, 0, gamma*sizeof(*aux) );
for( i=0; i<q; ++i ) {
aux[a[i]-min]++;
aux[b[i]-min]++;
}
for( i=0, j=0; i<gamma; ++i )
for( ; aux[i]; --aux[i] )
e[j++] = (int)i+min;
free( aux ); aux = NULL;
errore = 0; /* tutto bene! */
}
return errore;
}
void visualizza_array( int *a, int *b, int *e, size_t q ) {
size_t i;
printf( "\n\n%s", " Array a[]: " );
for( i=0; i<q; ++i ) printf( " %2d", a[i] );
printf( "\n\n%s", " Array b[]: " );
for( i=0; i<q; ++i ) printf( " %2d", b[i] );
printf( "\n\n%s", " Array e[]: " );
for( i=0; i<2*q; ++i ) printf( " %2d", e[i] );
printf( "%s", "\n\n" );
}
Altro che
Settimana enigmistica!