Soluzione esame Giugno 2007
Il testo dell'esame non lo trovo... ma più o meno il succo è il seguente:
Leggere da un file di testo n parole (con n intero letto come primo elemento del file) e calcolarne le coppie inversione:
una coppia inversione è costituita dalle parole word_i e word_j in cui i<j ma lessicograficamente word_j < word_i, cioè due parole che non sono "ordinate".
Un algoritmo stupido non fa altro che controllare per ogni parola quante delle parole che sono dopo non sono in ordine lessicografico rispetto a questa, per n parole avremmo quindi n(n-1)/2 confronti, complessità O(n^2).
Utilizzando invece il mergesort, osserviamo che nell'operazione di merge ogni volta che la parola S2[j]<S1[i] e copiamo nel vettore ordinato S2[j], questa costituisce coppia inversione con tutte le parole S1[k] con i<k<=dim1. Inserendo quindi un contatore che modifichiamo in maniera opportuna quando ciò accade, otteniamo una complessità O(n log n).
SOLUZIONE GaS
/****************************************************************************/
/* LIBRARIES */
/****************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/****************************************************************************/
/* MACRO */
/****************************************************************************/
#define COMPARE(a,b) ( ( strcmp((char *)a , (char *)b) ) > 0 )
/****************************************************************************/
/* FORWARD DECLARATIONS */
/****************************************************************************/
void merge(void **s1,void **s2, int dim1,int dim2, int *contatore);
void mergesort(void **v,int dim, int *contatore);
/****************************************************************************/
/* MAIN */
/****************************************************************************/
int main(){
char *buff, /* n buffer di 255 caratteri */
**sp; /* puntatore alle stringhe */
int n, /* numero di stringhe del file */
m, /* indica le posizioni stringhe in buff */
i,j, /* variabili di scorrimento */
contatore_1 = 0, /* contatore "coppie inversione" n^2 */
contatore_2 = 0; /* contatore "coppie inversione" n log n */
FILE *f; /* puntatore a file */
/* === LETTURA DA FILE ================================================ */
f = fopen("input.txt","rt");
fscanf(f,"%d",&n);
buff = (char *) malloc (n*255*sizeof(char));
sp = (char **) malloc (n*sizeof(char));
m=0;
i=0;
/* legge una riga e la memorizza nel buffer buff[m] */
while ( fscanf(f,"%s",&buff[m])!=EOF ){
sp[i] = &buff[m]; /* s[i] punta alla parola i */
m += strlen(sp[i])+1; /* m indica la posizione lenght[parola(i)]+1 */
i++;
}
fclose(f);
/* =========================================== FINE LETTURA DA FILE === */
printf("Parole nell'ordine di lettura:\n");
for(m=0,i=0;i<n;i++){
printf("%s ",&buff[m]); /* printf("%s ",sp[i]); */
m+=strlen(&buff[m])+1;
}printf("\n");
/* Calcolo "coppie inversione" con n^2 confronti (n*(n-1)/2) */
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(COMPARE(sp[i],sp[j]))
contatore_1++;
/* Calcolo "coppie inversione" n log n confronti */
mergesort(sp,n,&contatore_2);
printf("Parole in ordine lessicografico:\n");
for(i=0;i<n;i++)
printf("%s ",sp[i]);
printf("\n");
printf("numero di coppie inversione n^2 = %d\n",contatore_1);
printf("numero di coppie inversione n log n = %d\n",contatore_2);
return 0;
}
/****************************************************************************/
/* MERGESORT */
/****************************************************************************/
void merge(void **s1,void **s2, int dim1,int dim2, int *contatore){
int k=0,i=0,j=0;
void **S = (void **) malloc ( (dim1+dim2)*sizeof(void *) );
while ( k < dim1+dim2 ){
if ( i >= dim1 ){ S[k++] = s2[j++]; continue; }
if ( j >= dim2 ){ S[k++] = s1[i++]; continue; }
if (!(COMPARE (s1[i],s2[j])))
S[k++] = s1[i++];
else{
/* quando prendiamo un elemento dalla stringa s2 *
* questo costituirà "coppia inversione" con tutti *
* gli elementi di s1 non ancora presenti in S */
(*contatore)+= dim1-i; /* oppure j+dim1-k; */
S[k++] = s2[j++];
}
}
for (k=0;k<(dim1+dim2);k++)
s1[k] = S[k];
free(S);
}
void mergesort(void **v,int dim, int *contatore)
{
void **s1,**s2;
if (dim>1){
s1 = &v[0];
s2 = &v[dim/2];
mergesort(s1,dim/2,contatore);
mergesort(s2,dim-(dim/2),contatore);
merge(s1,s2,dim/2,dim-(dim/2),contatore);
}
}
Torna ad Laboratorio di Algoritmi e Strutture Dati
Non ci sono commenti in questa pagina. [Scrivi commento]