Esercizio 1:
Testo:
Dato il programma:
#include
void f(int a, int b, int *c, int *d)
{
*c = 0; *d = a;
while (*d >= b) { *d -= b; (*c)++; }
a = 0; b = 1;
}
int main ()
{
int m , n , p , q ;
scanf("%d %d %d %d ", &m , &n , &p , & q ) ;
f(m,n,&p,&q) ;
printf("%d %d %d %d ", m , n , p , q ) ;
}
Spiegare cosa calcola la funzione f, in modo formale. Scrivere che cosa stampa il programma se l’input è: $$20 3 25 4$$.
Soluzione:
Dal prototipo della funzione:
void f(int a, int b, int *c, int *d)
possiamo subito notare che essendo il tipo di ritorno void, la f non è una funzione (matematicamente parlando) ma una procedura. Quindi per poter calcolare qualcosa essa deve modificare lo stato del chiamante. L’unico modo per far questo è modificare delle variabili passate per riferimento. Ed infatti le variabili c, d sono puntatori, attraverso cui modificare lo stato del chiamante. Per elimiare i puntatori dall’analisi della funzione possiamo riscrivere la funzione in questo modo (semanticamente equivalente):
void f(int a, int b, int *c, int *d)
{
int x = 0, y = a;
while (y >= b) { y -= b; x++; }
a = 0; b = 1;
*c = x; *d = y;
}
Notiamo quindi che le ultime istruzioni (riga 6) servono per passare il risultato del calcolo fuori dalla f, al chiamante. Le istruzioni alla riga 5 sono del tutto inutili poichè la modifica delle variabili locali a,b, non influenza dopo l’esecuzione della riga 5 il valore di x,y e non viene vista dal chiamante (perche le variabili sono locali alla funzione). Quindi il valore di x,y è determinato solo dal ciclo con le condizioni iniziali date da x=0, y=a;
Nel ciclo while, le sottrazioni ripetute nell’istruzione y -= b e il conteggio x++, ci portano intuitivamente a considerare che i valori di x,y corrispondano rispettivamente al quoziente ed al resto della divisione intera tra a e b.
Per formalizzare questa intuizione, notiamo che all’inizio del ciclo si ha: y = a; x = 0;
- Dopo il primo passo del ciclo, si ha y = y – b, quindi y = a-b, e x = 1;
- Dopo il secondo passo si ha: y = a – 2b, e x = 2;
- Al passo i-esimo quindi si ha: $$y = a – x \; b$$ che è l’invariante del ciclo. Il ciclo continua fino a quando y >= b, quindi quando si esce dal ciclo si ha: $$0 \leq y < b$$, e $$x*b+y = a$$, da cui la tesi.
Esercizio 2: (Sudoku)
Testo: Dato uno schema di Sudoku, cioè una matrice quadrata 9×9, piena di interi compresi tra 1 e 9, verificare che tale matrice sia una soluzione valida del gioco. Tale soluzione e’ valida se ogni riga, ogni colonna e le 9 sottomatrici che iniziano in posizione [3*i,3*j] con i=0,..2, j=0,..2 contengono i numeri da 1 a 9 senza ripetizioni.
Soluzione:
La soluzione richiede di scrivere una funzione che verifica se una matrice 9×9 è una soluzione del sudoku. Prima di presentare questa funzione, scriviamo un main per poter verificare che funzioni (il main non fa parte del compito).
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <assert.h>
#define N 9
bool check_sudoku(int m[N][N]);
int test[N][N] = {
{5,3,4,6,7,8,9,1,2},
{6,7,2,1,9,5,3,4,8},
{1,9,8,3,4,2,5,6,7},
{8,5,9,7,6,1,4,2,3},
{4,2,6,8,5,3,7,9,1},
{7,1,3,9,2,4,8,5,6},
{9,6,1,5,3,7,2,8,4},
{2,8,7,4,1,9,6,3,5},
{3,4,5,2,8,6,1,7,9}
};
int main(int argc, char *argv[])
{
// verifico che la matrice corretta venga riconosciuta tale.
assert(check_sudoku(test) == true);
// cambiamo un elemento:
test[0][3] = test[3][0];
assert(check_sudoku(test) == false);
printf("ok\n");
return 0;
}
Se la funzione check_sudoku è scritta correttamente, il main stampa “ok”, in quanto su una matrice che è soluzione la funzione restituisce true, mentre se alteriamo leggermente la soluzione si deve ottenere false.
Ecco la soluzione con alcune funzioni di supporto:
// copia una sottomatrice 3x3 in posizione (a,b) da m in v
void copy_submatrix(int m[N][N], int v[N], int a, int b)
{
int c = 0;
for (int i=a; i<a+3; i++)
for (int j=b; j<b+3; j++)
v[c++] = m[i][j];
}
// true iff v e' una permutazione di {1,..9}.
bool completo(int v[N])
{
int t[N] = { 0 };
for (int i=0; i<N; i++) t[v[i]-1]++;
int j = 1;
while (j<N && t[j]) j++;
return j == N;
}
bool check_sudoku(int m[N][N])
{
// controllo le righe
for (int i=0; i<N; i++)
if (!completo(m[i])) return false;
// controllo le colonne
int temp[N];
for (int i=0; i<N; i++) {
// copio la colonna i di m in temp;
for (int j=0; j<N; j++) temp[j] = m[j][i];
if (!completo(temp)) return false;
}
// controllo le sottomatrici.
for (int i=0; i<N; i+=N/3)
for (int j=0; j<N; j+=N/3) {
copy_submatrix(m,temp,i,j);
if (!completo(temp)) return false;
}
return true;
}
Se volessimo implementare la funzione completo, senza usare un vettore d’appoggio, per valori di N<64, potremmo riscriverla usando delle semplici proprietà delle potenze, (che nel caso particolare della base 2, diventano degli shift) in questo modo:
bool completo2(int v[N])
{
unsigned int x = 0;
for (int i=0; i<N; i++) x += 1L << (v[i]-1); // x += pow(2,v[i]-1);
return x == (1L << N)-1; // x == pow(2,N)-1;
}
Esercizio 3
Testo:
Considerate una base di dati di studenti, per ogni studente conservate la matricola (un intero), nome, cognome ed email (stringhe di al più 50 caratteri). Tali informazioni sono contenute in un file binario
studenti.dat, ordinati sul campo matricola. Scrivere:
- Una funzione che dato un numero di matricola m, trova (se esiste) e stampa le informazioni relative allo studente con matricola m, usando il minimo numero di letture possibili dal file.
- Considerate un albero binario che contiene solo la matricola e il cognome, ordinato sul campo cognome. Scrivere una funzione che legge i record degli studenti, e li inserisce nell’albero (in
modo da tenerlo ordinato per il campo cognome). - Scrivere una funzione che ricerca uno studente per cognome, visitando prima l’albero costruito al punto precedente, trovando la matricola corrispondente e usando poi la funzione scritta nel
primo punto.
Soluzione:
Cominciamo con il dichiarare una struttura dati adeguata:
#define LEN 50
typedef struct s {
int matricola;
char nome[LEN];
char cognome[LEN];
char email[LEN];
} Studente;
3.1 – Ricerca Binaria
Bene, adesso per risolvere il primo problema (trovare un elemento data la matricola), possiamo sfruttare l’ordinamento dei record all’interno del file binario.
Usiamo quindi una ricerca binaria per trovare l’elemento con matricola data.
/* Esercizio 3.1, trova lo studente con matricola m,
e stampa i dati: deve minimizzare le letture da file.
*/
void CercaStudente(FILE *fin, int m)
{
// troviamo quanti studenti sono memorizzati:
fseek(fin,0,SEEK_END);
int len = ftell(fin) / sizeof(Studente);
int low = 0, mid = 0, hi = len;
bool trovato = false;
Studente s;
while (hi>low && !trovato)
{
// ci spostiamo nel punto di mezzo e leggiamo un record:
mid = (low + hi) / 2;
fseek(fin,sizeof(Studente)*mid,SEEK_SET);
if (fread(&s,sizeof(Studente),1,fin) < 1) {
printf("Errore in lettura\n");
exit(EXIT_FAILURE);
}
// vediamo se l'abbiamo trovato
if (s.matricola == m) {
trovato = true;
} else if (s.matricola < m)
low = mid+1;
else
hi = mid-1;
}
if (trovato)
printf("Trovato lo studente:\n"
"matricola: %d\n"
"nome: %s\n"
"cognome: %s\n"
"email: %s\n", s.matricola, s.nome, s.cognome, s.email);
}
3.2 – Costruzione Albero
Cominciamo con il dichiarare un albero con matricola e cognome, e scriviamo una piccola funzione che faccia da “costruttore” per un elemento dell’albero.
typedef struct node {
int matricola;
char cognome[LEN];
struct node *l, *r;
} TreeNode;
TreeNode *newNode(int m, const char* cognome)
{
TreeNode *p = malloc(sizeof(TreeNode));
strcpy(p->cognome,cognome);
p->matricola = m;
p->l = p->r = NULL;
return p;
}
A questo punto possiamo scrivere una funzione che inserisce un certo studente nell’albero, e quindi usare questa funzione per inserire i dati letti dal file:
void Insert(TreeNode **p, const Studente *s)
{
TreeNode *tree = *p;
if (tree == NULL) {
TreeNode *new = newNode(s->matricola, s->cognome);
*p = new;
} else if (strcmp(s->cognome, tree->cognome) > 0) { // s > p
Insert(&tree->r, s);
} else {
Insert(&tree->l, s);
}
}
TreeNode *CreaAlbero(FILE *f)
{
TreeNode *radice = NULL;
Studente s;
int i = 0;
while (!feof(f))
{
fread(&s,sizeof(Studente),1,f);
Insert(&radice, &s);
}
return radice;
}
3.3 – Ricerca usando l’albero
A questo punto possiamo usare l’albero costruito per trovare (velocemente) la matricola associata ad un certo cognome. Notiamo che questo meccanismo per accelerare le ricerche per cognome vale solo se la relazione cognome<->matricola è bigettiva, cosa in generale non vera.
int TrovaMatricola(TreeNode *radice, char *cognome)
{
if (radice == NULL) return 0;
int cmp = strcmp(radice->cognome,cognome);
if (cmp == 0)
return radice->matricola;
else if (cmp > 0)
return TrovaMatricola(radice->l, cognome);
else
return TrovaMatricola(radice->r, cognome);
}
void TrovaFastCognome(TreeNode *radice, char *cognome, FILE *fin)
{
// Ricerca per cognome, non leggo i singoli record
// dal file ma uso l'albero.
int matricola = TrovaMatricola(radice,cognome);
if (matricola == 0)
printf("Nessun studente con cognome %s\n",cognome);
else
CercaStudente(fin, matricola);
}