Programmazione I (canale P-Z) a.a. 2007-2008
Docente: R. Silvestri Esercitatore: A. Carosi
Tutor: J. Stefa
Prova scritta - 6 febbraio 2008
Non usare variabili globali.
È consentito usare le funzioni della libraria standard ma tutte le altre
funzioni usate devono essere definite. Se una soluzione non è scritta
in modo chiaro ed ordinato non sarà presa in considerazione.
Il voto (in trentesimi) è la somma dei punti ottenuti negli esercizi svolti.
Per chi fa solamente la Seconda Parte: i punti degli esercizi 4, 5 e 6
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 6 punti)
- Scrivere una funzione, con prototipo int nochar(char *str, char x), che
ritorna la lunghezza della più lunga sottostringa (sequenza di caratteri
consecutivi) di str che non contiene il carattere x. Ad esempio,
se str = "stringa di esempio" e x = 'i' allora la funzione
ritorna 6.
Soluzione
-
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;
}
Esercizio 2 (max 8 punti)
- Scrivere una funzione, con prototipo int eqfreq(int A[], int B[], int n), che presi in input
due vettori A e B di eguale dimensione n ritorna il numero di valori distinti
che hanno la stessa frequenza positiva sia in A che in B. Per frequenza
di un valore si intende il numero di volte che il valore appare nel vettore.
Ad esempio, se A = [3, 5, 3, 1, 2, 5, 5] e B = [4, 3, 5, 2, 3, 5, 4] allora la
funzione ritorna 2 perché il valore 3 ha frequenza 2 in entrambi i vettori,
il valore 2 ha frequenza 1 in entrambi i vettori e tutti gli altri valori hanno frequenze
differenti nei due vettori.
Soluzione
-
/* 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;
}
Esercizio 3 (max 10 punti)
- Scrivere una funzione, con prototipo char *replacex(char *str, char *rep),
che ritorna una stringa allocata dinamicamente ottenuta sostituendo ogni occorrenza
del carattere 'X' nella stringa str con la stringa rep.
Il blocco di memoria allocato per la stringa ritornata non deve essere più
grande del necessario. Ad esempio, se str = "XXena e Xla vuota"
e rep ="la pi" allora la funzione ritorna la stringa "la pila piena e la pila vuota".
Soluzione
-
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;
}
Seconda parte
Esercizio 4 (max 6 punti)
- Si consideri il seguente tipo:
typedef struct Elem {
int val;
struct Elem *next;
} Elem, *List;
Scrivere una funzione, con prototipo void fiblist(List L), che presa in input una lista
di interi L aggiunge in coda alla lista un nuovo elemento con valore nel campo val
pari alla somma dei valori degli ultimi due elementi di L. Se la lista ha meno di due elementi
la funzione non fa nulla. Ad esempio, se la lista L è 3 -> 13 -> 11 -> 25 allora
la funzione modifica la lista così 3 -> 13 -> 11 -> 25 -> 36.
Soluzione
-
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
}
Esercizio 5 (max 8 punti)
- Scrivere una funzione, con prototipo void flines(char *infile, char *outfile), che prende in input
il nome di un file di tipo testo (nella stringa infile) che contiene linee di testo terminate dal carattere
newline '\n' e crea un nuovo file di tipo testo, il cui nome è nella stringa outfile, e
vi scrive, per ogni linea del file di input, una linea che contiene linea k: n, dove
k è l'indice di linea (la prima linea ha indice 1) e n è il numero di caratteri
della linea k. Si assume che le linee del file di input abbiano al più 100 caratteri. Ad esempio,
file di input file di output
Quant'è bella giovinezza linea 1: 24
che si fugge tuttavia! linea 2: 22
Chi vuol esser lieto, sia: linea 3: 26
di doman non c'è certezza. linea 4: 26
Soluzione
-
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);
}
Esercizio 6 (max 10 punti)
- Si consideri il seguente tipo:
typedef struct Estr {
char * str; //stringa allocata dinamicamente
struct Estr *next;
} Estr, *Strlist;
Scrivere una funzione, con prototipo Strlist update(Strlist L, char c), che presa in input una
lista di stringhe rimuove da essa tutti gli elementi che hanno nel campo str una stringa
che contiene il carattere c, aggiunge in testa alla lista un nuovo elemento che nel campo
str 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 str una stringa che contiene il carattere c allora la funzione non
fa nulla. Ad esempio, se L è "verde" -> "rosso" -> "nero" -> "verde" -> "giallo" -> "viola"
e c = 'e' allora la funzione modifica la lista così "verdeneroverde" -> "rosso"
-> "giallo" -> "viola".
Soluzione
-
/* 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;
}
--
RiccardoSilvestri - 07 Feb 2008
This topic: Programmazione1
> WebHome >
Prog1PZ > Sol060208PZ0708
Topic revision: r2 - 2008-02-07 - RiccardoSilvestri