Fondamenti di Programmazione     a.a. 2011-2012
Prova scritta - 25 gennaio 2012
Avvertenze: non usare variabili globali; definire tutte le funzione ausiliarie usate; è consentito usare le funzioni della libreria standard; se una soluzione non è scritta in modo chiaro ed ordinato non sarà presa in considerazione.
Per chi fa solamente una parte: i punteggi degli esercizi sono da intendersi raddoppiati.
Per chi fa entrambe le parti: per raggiungere la sufficienza deve ottenere almeno 8 punti sulla Prima Parte e almeno 8 punti sulla Seconda Parte.

PRIMA PARTE
Esercizio 1 (max 7 punti)
Data una sequenza di numeri x1,x2,...,xk diremo che è d-uniforme se ogni xi si discosta dalla media al più d. Scrivere una funzione int qunif(float A[], int n, float d) che ritorna la lunghezza del più lungo sottovettore del vettore A che è d-uniforme. Ad esempio, se A = {3.0, 3.1, 2.5, 2.4, 2.6, 3.0, 3.1} (n = 7) e d = 0.1, la funzione ritorna 3 (la lunghezza del sottovettore dall'indice 2 all'indice 4).
Esercizio 2 (max 7 punti)
Scrivere una funzione int blkcnt(char *s, char start, char end) che ritorna il numero di sottostringhe della stringa s che iniziano con il carattere start, terminano con il carattere end e non contengono come caratteri intermedi né startend. Si assume che start != end. Ad esempio, se s = "((a))()b(((bbb)", start = '(' e end = ')', la funzione ritorna 3, se invece start = 'a' e end = 'b', ritorna 1.
Esercizio 3 (max 10 punti)
Scrivere una funzione int **zerosum(int n, int M[n][n], int *size) che ritorna, in una matrice allocata dinamicamente, la più grande sottomatrice quadrata della matrice M che ha somma zero e in *size restituisce la dimensione della sottomatrice. Se nessuna sottomatrice quadrata ha somma zero, ritorna NULL e in *size restituisce 0. La matrice ritornata deve essere allocata in modo tale che gli elementi siano accessibili tramite la sintassi delle parentesi quadre. Ecco un esempio,
 1 -1  2  0  0    
 3  3 -3  2  1                -1  2  0    sottomatrice di dimensione 3 che
 1 -4  1  0  2       ====>     3 -3  2    inizia nella riga 0 e colonna 1
 0  0  2  2  2                -4  1  0 
 0  0  1  1  1 
SECONDA PARTE
Esercizio 4 (max 6 punti)
Si consideri il seguente tipo:
typedef struct EStr {
    char *       str;    //stringa allocata dinamicamente
    struct EStr *next;
} EStr, *LStr;
Scrivere una funzione void inscat(LStr L) che per ogni coppia di elementi consecutivi della lista L che hanno stringhe uguali inserisce un nuovo elemento tra di essi la cui stringa è la concatenazione delle stringhe dei due elementi. Esempio:
                L = "A" → "A" → "B" -> "B" → "B"     
Dopo inscat(L), L = "A" → "AA" → "A" → "B" → "BB" → "B" → "BB" → "B"
Esercizio 5 (max 8 punti)
Scrivere una funzione void fextract(char *fname1, char *fname2, int g, int m, int a) che presi in input i nomi di due file di testo fname1 e fname2 tali che il primo contiene una sequenza di linee ognuna nel formato S G/M/A (dove S è una sequenza di caratteri alfabetici e G, M e A sono il giorno, mese ed anno di una data), aggiunge al secondo file, una per linea, le sequenze S delle linee del primo file la cui data è posteriore od uguale alla data g/m/a. Si assume che le sequenze S abbiano al più 40 caratteri. Esempio:
                                     Secondo file dopo l'esecuzione di
Primo file          Secondo file     fextract con g = 13, m = 7, a = 2011
Red 3/10/2011       Red              Red
Green 23/8/2010     White            White
Blue 3/7/2009                        Red
Brown 13/7/2011                      Brown
Esercizio 6 (max 10 punti)
Si consideri il seguente tipo:
typedef struct Elem {
    char         val[30];     //contiene una stringa di lunghezza < 30
    struct Elem *next;
} Elem, *List;
Due elementi di tipo Elem sono equivalenti se le stringhe dei campi val sono uguali. Scrivere una funzione List symdiff(List A, List B) che modifica la lista A in modo tale che contenga tutti e soli gli elementi di A che non sono equivalenti a nessun elemento della lista B e le copie degli elementi di B che non sono equivalenti a nessun elemento in A. Ritorna il puntatore alla lista A modificata. La lista B non deve essere modificata e la memoria degli eventuali elementi rimossi da A deve essere rilasciata. L'ordine degli elementi della lista modificata non ha importanza. Esempio:
A = "Cyan" → "Azure" → "Aqua" → "Ceil" → "Aqua"    B = "Blue" → "Ceil" → "Cyan" → "Ceil"
Dopo symdiff A = "Azure" → "Aqua" → "Aqua" → "Blue"