Sol060208PZ0708 < Programmazione1

Tags: view all tags
<div align="center"><big><b>Programmazione I &nbsp; &nbsp;(canale P-Z) a.a. 2007-2008<br>
</b></big>
Docente: R. Silvestri &nbsp; &nbsp; Esercitatore: A. Carosi &nbsp; &nbsp;
Tutor: J. Stefa<br>
Prova scritta - 6 febbraio 2008
</div>
<i>Non usare variabili globali.
&Egrave; consentito usare le funzioni della libraria standard ma tutte le altre
funzioni usate devono essere definite. Se una soluzione non &egrave; scritta
in modo <b>chiaro ed ordinato</b> non sar&agrave; presa in considerazione.
Il voto (in trentesimi) &egrave; la somma dei punti ottenuti negli esercizi svolti.<br>
<b>Per chi fa solamente la Seconda Parte:</b> i punti degli esercizi 4, 5 e 6
sono da intendersi raddoppiati. <br>
<b>Per chi fa entrambe le parti</b>: per raggiungere la sufficienza
deve ottenere almeno 8 punti sulla Prima Parte e almeno 8 punti sulla Seconda Parte. 
<br>
</i>
<br>
<div align="center"><big><b>Prima parte</b></big></div>

<dl><b>Esercizio 1 (max 6 punti)</b>
<dd>Scrivere una funzione, con prototipo <tt>int nochar(char *str, char x)</tt>, che 
ritorna la lunghezza della pi&ugrave; lunga sottostringa (sequenza di caratteri
consecutivi) di <tt>str</tt> che non contiene il carattere <tt>x</tt>. Ad esempio,
se <tt>str = "stringa di esempio"</tt> e <tt>x = 'i'</tt> allora la funzione
ritorna <tt>6</tt>.
</dd>
<b>Soluzione</b>
<dd>
<tt><pre>
int nochar(char *str, char x)
{
    int max = 0, i, k;
    for (i = 0 ; str[i] != '\0' ; i++) {
        k = 0;
        while (str[i + k] != x && str[i + k] != '\0') k++;
        if (k > max) max = k;
    }
    return max;
}
</pre></tt>
</dd>
</dl>

<dl><b>Esercizio 2 (max 8 punti)</b>
<dd>Scrivere una funzione, con prototipo <tt>int eqfreq(int A[], int B[], int n)</tt>, che presi in input
due vettori <tt>A</tt> e <tt>B</tt> di eguale dimensione <tt>n</tt> ritorna il numero di valori distinti
che hanno la stessa frequenza positiva sia in <tt>A</tt> che in <tt>B</tt>. Per frequenza
di un valore si intende il numero di volte che il valore appare nel vettore.
Ad esempio, se <tt>A = [3, 5, 3, 1, 2, 5, 5]</tt> e <tt>B = [4, 3, 5, 2, 3, 5, 4]</tt> allora la
funzione ritorna <tt>2</tt> perch&eacute; il valore <tt>3</tt> ha frequenza 2 in entrambi i vettori,
il valore <tt>2</tt> ha frequenza 1 in entrambi i vettori e tutti gli altri valori hanno frequenze 
differenti nei due vettori.
</dd>
<b>Soluzione</b>  
<dd>
<tt><pre>
/* Funzione ausiliaria che ritorna la frequenza del valore v nel vettore X
   di dimensione n.                                                       */
in freq(int X[], int n, int v)
{
    int f = 0, i;
    for (i = 0 ; i < n ; i++) if (X[i] == v) f++;
    return f;
}

int eqfreq(int A[], int B[], int n)
{
    int ef = 0, i;
    for (i = 0 ; i < n ; i++)                          //per ogni valore in A
        if (freq(A, i, A[i]) == 0)                     //se e' la prima occorrenza di A[i] in A
            if (freq(A, n, A[i]) == freq(B, n, A[i]))  //allora controlla le frequenze in entrambi i vettori
                ef++;                                  
    return ef;
}
</pre></tt>
</dd>
</dl>

<dl><b>Esercizio 3 (max 10 punti)</b>
<dd>Scrivere una funzione, con prototipo <tt>char *replacex(char *str, char *rep)</tt>, 
che ritorna una stringa allocata dinamicamente ottenuta sostituendo ogni occorrenza
del carattere <tt>'X'</tt> nella stringa <tt>str</tt> con la stringa <tt>rep</tt>.
Il blocco di memoria allocato per la stringa ritornata non deve essere pi&ugrave;
grande del necessario. Ad esempio, se <tt>str = "XXena e Xla vuota"</tt>
e <tt>rep ="la pi"</tt> allora la funzione ritorna la stringa <tt>"la pila piena e la pila vuota"</tt>.
</dd>
<b>Soluzione</b> 
<dd>
<tt><pre>
char *replacex(char *str, char *rep)
{
    long lrep = strlen(rep), len = strlen(str);
    long i, j, k;
    for (i = 0 ; str[i] != '\0' ; i++) 
        if (str[i] == 'X') len += lrep - 1;
    char *strep = malloc(sizeof(char)*(len + 1));
    for (k = i = 0 ; str[i] != '\0' ; i++)
        if (str[i] == 'X') {
            for (j = 0 ; rep[j] != '\0' ; j++)
                strep[k++] = rep[j];
        } else strep[k++] = str[i];
    strep[k] = '\0';
    return strep;
}
</pre></tt>
</dd>
</dl>
<hr width="100%" size="2"><br>
<div align="center"><big><b>Seconda parte</b></big></div>
<dl><b>Esercizio 4 (max 6 punti)</b>
<dd>Si consideri il seguente tipo:
<tt><pre>
typedef struct Elem {
    int          val;
    struct Elem *next;
} Elem, *List;
</pre></tt>
Scrivere una funzione, con prototipo <tt>void fiblist(List L)</tt>, che presa in input una lista
di interi <tt>L</tt> aggiunge in coda alla lista un nuovo elemento con valore nel campo <tt>val</tt>
pari alla somma dei valori degli ultimi due elementi di <tt>L</tt>. Se la lista ha meno di due elementi
la funzione non fa nulla. Ad esempio, se la lista <tt>L</tt> &egrave; <tt>3 -> 13 -> 11 -> 25</tt> allora 
la funzione modifica la lista cos&igrave; <tt>3 -> 13 -> 11 -> 25 -> 36</tt>.
</dd>
<b>Soluzione</b>   
<dd>
<tt><pre>
void fiblist(List L)
{
    if (L == NULL || L->next == NULL) return;   //Se ha meno di due elementi non fa nulla
    Elem *e1 = L, *e2 = L->next;                //Manteniamo in e1 ed e2 i puntatori ai
    L = e2;                                     //due elementi precedenti durante
    while (L->next != NULL) {                   //la scansione della lista.
        e1 = e2;
        e2 = L->next;
        L = e2;
    }                                           //Quando il while termina in L c'e'
    Elem *e = malloc(sizeof(Elem));             //il puntatore all'ultimo elemento
    e->val = e1->val + e2->val;                 //della lista.
    e->next = NULL;
    L->next = e;                                //aggancia il nuovo elemento in coda
}
</pre></tt>
</dd>
</dl>
<dl><b>Esercizio 5 (max 8 punti)</b>
<dd>Scrivere una funzione, con prototipo <tt>void flines(char *infile, char *outfile)</tt>, che prende in input
il nome di un file di tipo testo (nella stringa <tt>infile</tt>) che contiene linee di testo terminate dal carattere
newline <tt>'\n'</tt> e crea un nuovo file di tipo testo, il cui nome &egrave; nella stringa <tt>outfile</tt>, e
vi scrive, per ogni linea del file di input, una linea che contiene <tt>linea k: n</tt>, dove
<tt>k</tt> &egrave; l'indice di linea (la prima linea ha indice 1) e <tt>n</tt> &egrave; il numero di caratteri
della linea <tt>k</tt>. Si assume che le linee del file di input abbiano al pi&ugrave; 100 caratteri. Ad esempio, 
<tt><pre>
        file di input                                            file di output

        Quant'&egrave; bella giovinezza                                 linea 1: 24
        che si fugge tuttavia!                                   linea 2: 22
        Chi vuol esser lieto, sia:                               linea 3: 26
        di doman non c'&egrave; certezza.                               linea 4: 26

</pre></tt>
</dd>
<b>Soluzione</b>   
<dd>
<tt><pre>
void flines(char *infile, char *outfile)
{
    FILE *in = fopen(infile, "r");                 //apri in lettura il file di input
    FILE *out = fopen(outfle, "w");                //crea e apri in scrittura il file di output
    char linea[101];                               //array per mantenere una linea letta
    int k = 1;
    while (fgets(linea, 101, in) != NULL) {                    //leggi le linee del file di input
        fprintf(out, "linea %d: %d\n", k, strlen(linea));
        k++;
    }
    fclose(in);
    fclose(out);
}
</pre></tt>
</dd>
</dl>
<dl><b>Esercizio 6 (max 10 punti)</b>
<dd>Si consideri il seguente tipo:
<tt><pre>
typedef struct Estr {
    char *       str;      //stringa allocata dinamicamente
    struct Estr *next;
} Estr, *Strlist;
</pre></tt>
Scrivere una funzione, con prototipo <tt>Strlist update(Strlist L, char c)</tt>, che presa in input una
lista di stringhe rimuove da essa tutti gli elementi che hanno nel campo <tt>str</tt> una stringa
che contiene il carattere <tt>c</tt>, aggiunge in testa alla lista un nuovo elemento che nel campo
<tt>str</tt> ha una stringa formata concatenando tutte le stringhe rimosse e ritorna il puntatore
alla lista modificata. Se non ci sono elementi
che hanno nel campo <tt>str</tt> una stringa che contiene il carattere <tt>c</tt> allora la funzione non
fa nulla. Ad esempio, se <tt>L</tt> &egrave; <tt>"verde" -> "rosso" -> "nero" -> "verde" -> "giallo" -> "viola"</tt>
e <tt>c = 'e'</tt> allora la funzione modifica la lista cos&igrave; <tt>"verdeneroverde" -> "rosso"
-> "giallo" -> "viola"</tt>.
</dd>
<b>Soluzione</b>   
<dd>
<tt><pre>
/* Funzione ausiliaria che ritorna true se la stringa str contiene il carattere c,
   altrimenti ritorna false.                                                     */
int inchar(char *str, char c)
{
    int i;
    for (i = 0 ; str[i] != '\0' && str[i] != c ; i++) 
    return (str[i] == c);
}

Strlist update(Strlist L, char c)
{
    Strlist p = L;
    long size = 0;
    while (p != NULL) {              //scorri la lista per calcolare la somma delle
        if (inchar(p->str, c))       //lunghezze delle stringhe da rimuovere
            size += strlen(p->str);
        p = p->next;
    }
    if (size == 0) return L;          //se non ci sono stringhe da rimuovere non fare nulla
    char *concat = malloc(sizeof(char)*(size + 1));   //alloca il blocco per la concatenazione
    concat[0] = '\0';                                 //delle stringhe da rimuovere 
    Strlist *pL = &L;
    while (*pL != NULL) {                //scorri la lista
        if (inchar((*pL)->str, c)) {     //se l'elemento ha una stringa che contiene c
            strcat(concat, (*pL)->str);  //concatena la stringa da rimuovere
            free((*pL)->str);            //libera la memoria della stringa
            Estr *next = (*pL)->next;    //salva il puntatore al prossimo elemento
            free(*pL);                   //libera la memoria dell'elemento
            *pL = next;                  //sgancia l'elemento dalla lista
        } else pL = &((*pL)->next);
    }
    p = malloc(sizeof(Estr));            //alloca il nuovo elemento
    p->str = concat;
    p->next = L;                         //aggiungi il nuovo elemento in testa
    return p;
}
</pre></tt>
</dd>
</dl>

<br>
<br>
<br>
<br>
<br>
<br>




-- Users.RiccardoSilvestri - 07 Feb 2008