Fondamenti di Programmazione     a.a. 2011-2012
Soluzioni prova scritta - 25 gennaio 2012

//Ritorna vero se il sottovettore di A dall'indice i all'indice j è d-uniforme
int isqunif(float A[], int i, int j, float d) {
    float ave = 0;
    for (int k = i ; k <= j ; k++)
        ave += A[k];
    ave /= (j - i + 1);              //La media del sottovettore
    for (int k = i ; k <= j ; k++)
        if (A[k] - ave > d || A[k] - ave < -d) return 0;
    return 1;
}

int qunif(float A[], int n, float d) {
    int max = 0;
    for (int i = 0 ; i < n ; i++)
        for (int j = i ; j < n ; j++)
            if (j - i + 1 > max && isqunif(A, i, j, d))
                max = j - i + 1;
    return max;
}

int blkcnt(char *s, char start, char end) {
    int count = 0, started = 0;
    for (int i = 0 ; s[i] != '\0' ; i++) {
        if (s[i] == start) 
            started = 1;
        if (s[i] == end) {
            if (started) 
                count++;
            started = 0;
        }
    }
    return count;
}

#include <stdlib.h>

int **zerosum(int n, int M[n][n], int *size) {
    int max = 0, rmax, cmax;
    for (int r = 0 ; r < n ; r++) {
        for (int c = 0 ; c < n ; c++) {    //(r, c) angolo superiore sinistro della sottomatrice
            int k = (r > c ? n - r : n - c);   //La massima dim. della sottomatrice
            while (k > max) {          //Per tutte le possibili dimensioni 
                int s = 0;
                for (int i = 0 ; i < k ; i++)       //Calcola la somma della sottomatrice
                    for (int j = 0 ; j < k ; j++)
                        s += M[r + i][c + j];
                if (s == 0) {                       //Se è zero, aggiorna la massima dimensione
                    max = k;                        //e la locazione della sottomatrice
                    rmax = r;
                    cmax = c;
                }
                k--;
            }   
        }
    }
    *size = max;
    if (max > 0) {                            //Se una sottomatrice con somma zero esiste
        int **subm = malloc(max*sizeof(int *));     //Alloca la matrice in cui copiare
        for (int i = 0 ; i < max ; i++) {           //la sottomatrice
            subm[i] = malloc(max*sizeof(int));
            for (int j = 0 ; j < max ; j++)         //Copia la sottomatrice
                subm[i][j] = M[rmax + i][cmax + j];   
        }
        return subm;
    } else
        return NULL;
}

#include <stdlib.h>
#include <string.h>

void inscat(LStr L) {
    if (L == NULL) return;
    EStr *p = L;
    while (p->next != NULL) {
        if (strcmp(p->str, (p->next)->str) == 0) {
            EStr *e = malloc(sizeof(EStr));
            e->str = malloc(2*strlen(p->str) + 1);
            strcpy(e->str, p->str);
            strcat(e->str, p->str);
            e->next = p->next;
            p->next = e;
            p = e->next;
        } else
            p = p->next;
    }
}

#include <stdio.h>

void fextract(char *fname1, char *fname2, int g, int m, int a) {
    FILE *f1 = fopen(fname1, "r");
    FILE *f2 = fopen(fname2, "a");
    if (f1 == NULL || f2 == NULL) return;
    char s[41];
    while (fscanf(f1, "%s", s) == 1) {
        int gg, mm, aa;
        fscanf(f1, "%d/%d/%d", &gg, &mm, &aa);
        if (aa > a || ((aa == a && mm > m) || (aa == a && mm == m && gg >= g)))
            fprintf(f2, "%s\n", s);
    }
    fclose(f1);
    fclose(f2);
}

#include <stdlib.h>
#include <string.h>

//Funzione ausiliaria che ritorna vero se c'è un elemento in L per cui la stringa
//del campo val è uguale alla stringa v.
static int isin(List L, char *v) {
    while (L != NULL && strcmp(L->val, v) != 0)
        L = L->next;
    return (L != NULL);
}

List symdiff(List A, List B) {
    List BA = NULL;           //Puntatore alla lista che conterrà la differenza simmetrica
    Elem *p = B;
    while (p != NULL) {       //Scorri B per trovare gli elementi di B - A
        if (!isin(A, p->val)) {              //Se non è in A,
            Elem *e = malloc(sizeof(Elem));  //aggiungi una copia dell'elemento
            strcpy(e->val, p->val);          //in testa alla nuova lista
            e->next = BA;
            BA = e;
        }
        p = p->next;
    }
    Elem **pp = &A;
    while (*pp != NULL) {    //Scorri A per eliminare gli elementi comuni
        if (isin(B, (*pp)->val)) {    //Se è in B,
            Elem *e = *pp;            //sgancia l'elemento da A
            *pp = e->next;
            free(e);
        } else
            pp = &((*pp)->next);
    }                        //Al termine del while, in A rimagono gli elementi di A - B
    *pp = BA;                //Accoda gli elementi di B - A
    return A;
}