Programmazione ed
Esercitazioni di Programmazione


Esame pratico di programmazione del 12/02/2008 - Soluzioni

Le soluzioni qui proposte sono solo indicative, vi sono molti modi per poter svolgere lo stesso esercizio!

Sono proposte alcune soluzioni alle tipologie di esercizi assegnati nell'esame pratico del corso di programmazione del 12/02/2008.

Vengono fornite le soluzioni solo per alcuni esercizi, per gli altri la struttura delle funzioni rimane uguale, cambiano i tipi di dato e i nomi delle strutture dati utilizzate.

Esercizio 1 (Tema 144)

/* int conta(ListaCalzetti l); La funzione conta restituisce il numero di paia di calzetti (della stessa lunghezza e dello stesso colore!) presenti nella lista. */

int conta(ListaCalzetti l) {
	int i; 
	int j;
	int coppie = 0;
	/* Array per il conteggio del numero di calzini di ogni tipo (Verdi-Lunghi, Verdi-Corti,...)
	   presenti nella lista. Ogni cella viene inizializzata a 0. */
	int c[2][4] = {{0,0,0,0}, {0,0,0,0}};
	
	if(l == NULL) return coppie;
	
	/* Scorro l'intera lista */
	while(l != NULL) {
		/* Aggiungo ogni calzino nella cella della tabella corrispondente */
		c[l->lunghezza][l->colore]++;
		l = l-> next;
	}
	
	for(i = 0; i < 2; i++) {
		for(j = 0; j < 4; j++) {
			/* Calcolo le coppie, che sono formate da due calzini, non da uno!!! */
			coppie += (c[i][j] / 2);
		}
	}
	
	return coppie;
}


Esercizio 1 (Tema 145)

/* int conta(ListaScarpe l, Modello m, Tipo t); La funzione conta restituisce il numero di paia di scarpe del modello m e del tipo t presenti nella lista. */

/* ATTENZIONE: un paio di scarpe è formato da due scarpe dello stesso numero. 
   Un mocassino da uomo numero 45 e uno 38 non fanno un paio di scarpe.
   Per questo esercizio si propone una soluzione con l'utilizzo di un vettore 
   bidimensionale dinamico in cui via via si aggiungeranno i numeri delle 
   scarpe che si incontrano nella lista. */
int conta(ListaScarpe l, Modello m, Tipo t) {
	int i; 
	int dim = 0;
	int coppie = 0;
	/* Vettore bidimensionale dinamico che contiene i numeri delle scarpe 
	   di tipo t e modello m già incontrati */
	int **numeri = NULL;
	
	if(l == NULL) return coppie;
	
	/* Scorro la lista */
	while(l != NULL) {
		/* Se la scarpa è del modello e del tipo che mi interessa */
		if(l->tipo == t && l->modello == m) {
			/* Scorro l'array dei numeri per vedere se ne ho trovato 
			   un'altra di quel numero in precedenza */
			for(i = 0; i < dim; i++) {
				if(numeri[i][0] == l->numero) {
					/* Se si, aumento il contatore e termino il ciclo for */
					numeri[i][1]++;
					break;
				}
			}
			/* Se i == dim, ho scorso tutto il vettore senza trovare un numero 
			   uguale a quello della scarpa che sto esaminando, devo aggiungerlo */
			if(i == dim) {
				dim++;
				/* Alloco memoria per entrambe le dimensioni dell'array e 
				   inizializzo i campi */
				numeri = (int **)realloc(numeri, dim*sizeof(int));
				numeri[i] = (int*)malloc(sizeof(int));
				numeri[dim-1][0] = l->numero;
				numeri[dim-1][1] = 1;
			}
		}
		l = l-> next;
	}
	
	/* Scorro l'array e conto le coppie effettive */
	for(i = 0; i < dim; i++) {
		printf("[%d -> %d] ", numeri[i][0], numeri[i][1]);
		coppie += (numeri[i][1] / 2);
	}
	
	return coppie;
}


Esercizio 1 (Tema 146 e 147)

/* In questi esercizi si procedeva come nell'esercizio 1 del tema 144. Alla fine, riempito il vettore, si considerava, anziché la metà dei tati trovati, il minimo tra il numero delle pentole/pantaloni e dei coperchi/maglie.
Esempio: se si otttengono 7 coperchi per pirofile di vetro e 3 pirofile, avrò 3 batterie complete. */



Esercizio 2 (Tema 144)

/* void spaiati(ListaCalzetti *l); La procedura spaiati toglie dalla lista *l tutte le coppie di calzetti correttamente abbinabili: all'uscita dela procedura in *l resteranno quindi solo calzetti spaiati! */

/* Procedura asiliaria che ricerca un Calzetto c e lo elimina se lo trova,
   impostando ad uno la variabile found per segnalare il ritrovamento.
   La procedura restituisce una lista, che sarà la lista l meno
   l'eventuale calzetto trovato (può essere la testa). */
ListaCalzetti cancella(ListaCalzetti l, Calzetto c, int *found) {
	ListaCalzetti t;
	/* Se la lista è vuota non modifico niente. */
	if(l == NULL) return l;
	/* Se l'elemento attuale è quello da eliminare */
	if(l->colore == c.colore && l->lunghezza == c.lunghezza) {
		/* La nuova testa di l sarà l'elemento successivo */
		t = l->next;
		/* Si libera la memoria occupata dalla vecchia testa */
		free(l);
		/* Si segnala che si è trovato l'elemento */
		*found = 1;
		/* Si ritorna la nuova testa */
		return t;
	}
	/* Se l non è l'elemento da eliminare, lo cerco nella coda della lista.
	   L'elemento successivo di l diventerà la nuova lista restituita dalla
	   procedura stessa, ed l ne rimarrà la testa. */
	l->next = cancella(l->next, c, found);
	return l;
}

/* Procedura per eliminare le coppie di Calzetti */
void spaiati(ListaCalzetti *l) {
	int found;
	ListaCalzetti temp = (*l);
	ListaCalzetti c;
	ListaCalzetti prev = NULL;
	
	/* Scorro tutta la lista */
	while(temp != NULL) {
		/* Segnalo che ancora non ho trovato corrispondenze
		   eliminate per l'elemento attuale (temp) */
		found = 0;
		/* Elimino il Calzetto *temp dalla coda di temp */
		c = cancella(temp->next, *temp, &found);
		/* Se ho eliminato qualcosa devo eliminare anche temp */
		if(found == 1) {
			/* Se sono sulla testa della lista */
			if(prev == NULL) {
				/* La nuova testa sarà quella restituita dalla procedura cancella:
				   nel caso peggiore ho eliminato il primo e il secondo elemento e 
				   continuo dal terzo */
				(*l) = c;
				free(temp);
				temp = c;
			}
			/* Se non sono sulla testa, allora scollego l'elemento attuale
			   dalla lista, e la coda dell'elemento precedente sarà la coda
			   di prima, privata dell'elemento che fa coppia con temp */
			else {
				prev->next = c;
				free(temp);
				temp = c;
			}
		}
		/* Se non ho trovato un elemento che fa coppia, l'elemente attuale diventa 
		   il precedente e mi sposto avanti nella lista. */
		else {
			prev = temp;
			temp = temp->next;
		}
	}
	return;
}


Esercizio 3 (Tema 144)

/* void statistica(ListaCalzetti l, int tabella[4][2]); All'uscita della procedura statistica, nell'array bidimensionale di interi tabella (dove le righe sono relative al colore e le colonne relative alla lunghezza) dovremo avere i dati corretti relativi ai calzetti presenti nella lista l: nella casella tabella[0][0] dovremo avere il numero totale di calzetti corti e verdi, nella casella tabella[1][1] il numero dei calzetti lunghi e grigi, nella casella tabella[3][0] il numero dei calzetti corti e neri, eccetera. */

void statistica(ListaCalzetti l, int tabella[4][2]) {
	int i;
	int j;
	
	/* Inizializzo a 0 tutte le celle della tabella che mi viene passata.
	   Non ho idea dei dati che può contenere. Se non lo faccio non posso
	   usare l'operatore '++'. */
	for(i = 0; i < 4; i++)
		for(j = 0; j < 2; j++) 
			tabella[i][j] = 0;
			
	while(l != NULL) {
		/* ATTENZIONE: se non diversamente specificato nella definizione
		   i valori dei tipi enum iniziano sempre da 0, non da 1 */
		tabella[l->colore][l->lunghezza]++;
		l = l->next;
	}
	
	/* Alla fine della procedura, se l era vuoto, la mia tabella conterrà,
	correttamente, solo 0. */
	return;	
}