Homework di Recupero - Scadenza: 28 Febbraio 2010 7 Marzo 2010, ore 23:59:59 [Pagina di consegna]

Negli esercizi seguenti si faccia riferimento al seguente tipo:

struct genericList {
	void *info;
	struct genericList *next;
};
typedef struct genericList List;

Alcune delle funzioni descritte in seguito hanno delle pre-condizioni (ovvero non sono definite per tutte le configurazioni dell'input). È richiesto che queste siano opportunamente identificate e verificate. In caso non siano soddisfatte, le funzioni dovranno stampare su standard output un opportuno messaggio di errore e restituire un valore speciale che segnali l'anomalia. I valori da restituire sono descritti nel testo dei singoli esercizi.

Esercizio 1 [7 punti]

Nello specifico, sia dato il seguente tipo:

typedef struct {
	int num_occ;
	char *parola;
} InfoParola;

Si scrivano le seguenti funzioni:

1. [3 punti] List *analizzaTesto() che legge da standard input un testo (fino a EOF) corrispondente ad una sequenza di frasi pronunciate correttamente da un bambino di due anni e lo analizza scomponendolo in parole ed analizzando le occorrenze di ciascuna parola. La funzione creerà una lista collegata i cui elementi siano istanze della struttura InfoParola.
   Si assuma che nel testo le parole contengano solo i caratteri 'a'..'z', 'A'..'Z', 'à', 'è', 'ì', 'ò', 'ù', mentre tutti gli altri caratteri (spazi, newline, ecc.) sono considerati separatori.
2. [4 punti] List *parolePiuUsate(List *parole, double soglia) che, data una lista di istanze della struttura InfoParola ed un valore soglia reale tra 0 ed 1, restituisce le parole nella lista parole aventi un numero di occorrenze maggiore o uguale a soglia * Max, dove Max è il numero di occorrenze della parola che occorre di più.
   In caso le precondizioni non siano soddisfatte, la funzione restituisce NULL.

Esercizio 2 [6 punti]

Si ricorda che l'operazione di prodotto tra due numeri in una certa base richiede di conoscere il prodotto di ciascuna coppia di cifre. Nel caso della base 2 tutto si riduce a ricordare l'esiguo numero di 2*2 regole, che sono: 0*0 = 0, 0*1 = 0, 1*0 = 0, 1*1 = 1.

Ad esempio, il prodotto tra A=1011 e B=1101 è il numero 1011*1101 = 10001111, calcolato come segue:

       1011 * 
       1101 = 
     ----------- 
       1011 + 
      0000  + 
     1011   + 
    1011 
---------------- 
   10001111 

Esercizio 3 [12 punti]

Si consideri la seguente struttura dati per la memorizzazione di un singolo elemento (di tipo generico) insieme alla sua priorità

typedef struct {
	void *elem;
	int p;
} GenericPriorityQueueNode;

Si realizzino le seguenti funzioni:

1. [6 punti] int enqueue(List **priorityQueue, void *elem, int priority);
2. [6 punti] GenericPriorityQueueNode *dequeue(List **priorityQueue, int priority).

La funzione enqueue restituisce 0 se l'inserimento va a buon fine, -1 altrimenti. La funzione dequeue restituisce NULL in caso l'estrazione dell'elemento non sia possibile.

Esercizio 4 [20 punti]

I clienti del supermercato hanno associata una priorità (un valore >= 1): minore è il valore, maggiore è la priorità (ad esempio le persone anziane hanno priorità 1). I clienti sono sempre molto gentili alle casse, facendo sempre passare avanti coloro che arrivano in fila con priorità maggiore della loro.

Tuttavia i clienti in arrivo alle casse sono anche molto scaltri, accodandosi sempre alla cassa che prevedono li servirà nel tempo minore, tenendo conto della gentilezza che si attendono dagli altri.

Si noti che il tempo necessario, ad un cliente c in procinto di accodarsi, per essere servito da una cassa, dipende da più fattori:

• l'insieme dei clienti già in fila e le loro priorità (dato che c sa che passerebbe avanti agli eventuali clienti immediatamente avanti a loro con prorità minore, fermandosi dietro al primo cliente a priorità maggiore o uguale);
• il numero dei prodotti contenuti nel carrello dei clienti in fila davanti a c;
• la velocità del cassiere;
• il numero dei prodotti nel carrello di c (che influisce sul tempo necessario a servire c quando sarà il suo turno).

1. [6 punti] Si scriva una funzione int scegliCassa(int k, int tempoCassieri[k], int priorita, int num_prodotti, int *tempoStimato) che legga da standard input una sequenza di righe (separate da '\n' e terminate da EOF) avente la forma:

   j pri prod
   

   che rappresentano la situazione attuale davanti alle k casse e, dati i tempi dei k cassieri, la priorità ed il numero di prodotti di un cliente in procinto di accodarsi alle casse, restituisca l'indice della cassa che si prevede servirà il cliente nel più breve tempo possibile (in caso di parità tra due o più casse, la funzione sceglie quella con l'indice minore). La funzione salverà nella locazione di memoria puntata da tempoStimato il tempo stimato per servire il nuovo cliente.
   In caso le precondizioni non siano rispettate, la funzione restituisce -1.
2. [7 punti] Si scriva una funzione double tempoMedio(int k, int tempoCassieri[k]) che legga da standard input una sequenza di righe (separate da '\n' e terminate da EOF) avente la forma:

   t j pri prod
   

   che rappresentano la sequenza dei clienti che nel tempo (a partire da un certo istante 0) si sono accodati alle casse, e calcoli il tempo medio di servizio dei diversi clienti, tenendo conto del ruolo delle priorità nella gestione delle code (i clienti con priorità maggiore passano avanti a quelli con priorità inferiore). Ogni quadrupla letta rappresenta un singolo cliente insieme alla sua priorità pri, numero di prodotti prod, cassa scelta j e istante di tempo (intero in secondi, dall'istante 0) in cui si è accodato.
   In caso le precondizioni non siano rispettate, la funzione restituisce -1.
3. [7 punti] Si scriva una funzione double *perc_clienti_sfortunati(int k, int tempoCassieri[k], int *arraySize) che legga da standard input una sequenza di righe come descritta al punto 2 e restituisca un array (la cui taglia viene salvata nella locazione puntata da arraySize) il cui generico elemento i-esimo contiene la percentuale (un reale tra 0 e 1) dei clienti a priorità i che hanno atteso un tempo almeno doppio per essere serviti, rispetto al tempo stimato quando si sono acccodati.
   In caso le precondizioni non siano rispettate, la funzione restituisce -1.

Esercizio 5 [8 punti]

È noto che esiste una strategia per questo gioco che permetta ad un giocatore di non perdere mai, qualsivoglia siano le mosse dell'avversario.

Si consideri la seguente struttura:

typedef struct {
	int x;
	int y;
} Cella;

Si scriva una funzione List *giocaTicTacToe(int chiInizia) che permetta di giocare automaticamente al gioco del Tic-Tac-Toe impersonando il giocatore 0, e leggendo le mosse dell'avversario (giocatore 1) da standard input.

In particolare, la funzione legge da standard input righe separate da '\n' codificanti le celle scelte di volta in volta dal giocatore 1, nel formato:

x y

L'argomento chiInizia può valere 0 o 1, ed identifica il giocatore che effettua la prima mossa. L'algoritmo scelto per decidere le mosse del giocatore 0 deve essere tale che il giocatore 0 non perde mai, qualsivoglia siano le mosse del giocatore 1. La funzione deve gestire opportunamente errori nell'input (ad es., numero insufficiente di mosse del giocatore 1, oppure valori non nell'intervallo richiesto o non interi, ecc.), restituendo un puntatore a NULL.

Esercizio 6 [12 punti]

• Lista degli autori (ognuno dei quali con nome e cognome sotto forma di due stringhe);
• Lista degli interpreti (ognuno dei quali con nome e cognome sotto forma di due stringhe);
• Titolo (una stringa);
• Durata in secondi (un intero);
• Anno di incisione (un intero);
• Genere musicale (una stringa);

• Titolo dell'album;
• Lista di brani presenti, con relativo numero di traccia;

1. [3 punti] Scrivere una funzione List *creaDatabase() che legga da standard input una sequenza di blocchi di righe (ogni blocco è separato dal successivo da una o più righe vuote, mentre la sequenza dei blocchi è terminata da EOF) ognuno dei quali codifica le informazioni su un brano nel seguente formato:

   Autore: <cognome1>, <nome1>\n
   Autore: <cognome2>, <nome2>\n
   Interprete: <cognome3>, <nome3>\n
   Interprete: <cognome4>, <nome4>\n
   Titolo: <titolo>\n
   Durata: <durata>\n
   Anno: <anno>\n
   Genere: <genere>\n
   Album: <titolo album>\n
   Numero traccia: <numero traccia nell'album>\n 
   

   (dove le parentesi angolari sono qui utilizzate solo per enfatizzare il significato dei diversi dati, e non sono davvero presenti nel testo.)

   Le singole righe di un blocco possono essere in un ordine qualsiasi, e non c'è garanzia che gli autori o gli interpreti siano dati in righe contigue. Infine, alcune righe possono mancare, nel qual caso il relativo campo della struttura Brano va assegnato a NULL se stringa, o 0 se intero.

   Ad esempio, un blocco può essere il seguente:

   Genere: Musica classica\n
   Autore: van Beethoven,         Ludwig\n
   Titolo: Sonata per pianoforte n. 14\n
   Durata: 323\n
   Anno: 2007\n
   Interprete: Pollini,    Maurizio\n
   Album: Best of Pollini\n
   Numero traccia: 4\n 
   

   La funzione deve creare una lista collegata di elementi di tipo Album, ognuno dei quali a sua volta collegato alla lista dei brani in esso contenuti, con relativo numero di traccia. Tale lista deve essere a disposizione delle funzioni che seguono, anche per pi&uegrave; di una invocazione.

2. [3 punti] Scrivere una funzione char **cercaAlbumPerAutore(char *cognome, char *nome, int *size) che restituisca un array di stringhe (allocato dinamicamente), ognuna delle quali rappresentante il titolo di un album tra i cui autori ci sia il compositore richiesto. La funzione salva nella locazione puntata da size la lunghezza dell'array restituito. In caso non esista alcun album con tale caratteristica, la funzione restituisce NULL.
3. [3 punti] Scrivere una funzione void statisticheInterprete(char *cognome, char *nome, int *annoMin, int *annoMax, int *numGeneri) che restituisca nelle locazioni puntate da annoMin, annoMax, numGeneri rispettivamente il primo e l'ultimo anno in cui il musicista richiesto ha interpretato brani (secondo le informazioni presenti nell'archivio letto) e il numero di generi diversi dei brani che ha interpretato.
   In caso non esista alcun brano dell'interprete richesto, la funzione scrive il valore -1 in *annoMin e *annoMax e 0 in *numGeneri.

4. [3 punti] Scrivere una funzione void statisticheAlbum(char *titoloAlbum, int *durataCompl, int *numBrani, char ***titoliBrani) che restituisca nelle locazioni puntate da durataCompl e numBrani rispettivamente la durata complessiva e il numero dei brani dell'album dal titolo titoloAlbum. La funzione inoltre alloca dinamicamente un array di *numBrani stringhe che codificano i titoli dei brani dell'album richiesto, nell'ordine dei loro numeri di traccia. Il puntatore alla testa dell'array viene salvato nella locazione puntata da titoliBrani.
   In caso l'album richiesto non esista, la funzione scrive il valore -1 in *durataCompl, 0 in *numBrani e NULL in *titoliBrani.

Esercizio 7 [4 punti]

Si scriva una funzione char *fixText() che legga da standard input un testo (fino ad EOF) e lo restituisca in una stringa allocata dinamicamente modificato come segue:
• L'iniziale della prima parola, e le iniziali di tutte le parole che seguono un '.', un '?' o un '!' (anche se separato da spazi) vengono rese maiuscole;
• Viene aggiunto uno spazio dopo ogni carattere ',', ';', ':', '.', '?', '!', se non già presente;
• Viene rimosso l'eventuale spazio dopo ogni carattere '\'' (apostrofo);
• Ogni sequenza di due o più spazi viene sostituita da uno spazio singolo.

Ad esempio, se da standard input viene immesso:

questa è una   frase;ora siamo dopo\n
il punto    e virgola!\n 
questa frase  segue un punto.

la funzione restituisce la stringa:

"Questa è una frase; ora siamo dopo\nil punto e virgola! \nQuesta frase segue un punto. "

Esercizio 8 [6 punti]

Sia data una matrice M[n][m] a n righe e m colonne di double (positivi o nulli) tutti distinti, rappresentante un territorio accidentato, in cui il valore di ogni cella rappresenta l'altitudine (sul livello del mare) della zona rappresentata.

Un amante di trekking molto metodico ma poco fantasioso usa il seguente algoritmo per le sue escursioni:

1. Parte da una delle celle della matrice ed alterna fasi di salita a fasi di discesa, iniziando con una fase di salita.
2. In una fase di salita, ad ogni passo si muove, dalla cella attuale, alla cella vicina più elevata, tra le al più  9  8 possibili (salita più ripida). In caso la cella attuale abbia l'altitudine più elevata rispetto a tutte le celle vicine (vetta raggiunta), inizia una fase di discesa.
3. Durante una fase di discesa, si sposta sempre sulla cella vicina a più elevata altitudine (ma più bassa dell'attuale, discesa più dolce). La fase di discesa termina quando non esiste alcuna cella vicina più bassa dell'attuale. A questo punto inizia una nuova fase di salita.
4. Per evitare cicli infiniti, il nostro amico non torna mai in una cella già visitata.

Si scriva una funzione void escursione(int n, int m, int double M[n][m], int startX, int startY, int *endX, int *endY) che, presi in input una matrice M insieme al suo numero di righe n e colonne m, calcoli la cella in cui arriverà il nostro amante di trekking, se partendo dalla cella (startX, startY) seguisse pedissequamente l'algoritmo dato. La funzione salverà nelle locazioni di memoria puntate da endX ed endY le coordinate (riga e colonna) della cella di arrivo.

Nel caso le precondizioni non siano soddisfatte, la funzione scrive -1 in *endX e *endY.