soluzioni proposte

PROGRAMMAZIONE 1 e LABORATORIO (A,B) - a.a. 2014-2015
Esercitazione del 16/12/2014
SOLUZIONI PROPOSTE
ESERCIZIO 1
Dato il tipo degli alberi binari
type ’a btree = Void
| Node of ’a * ’a btree * ’a btree
si definisca in CAML una funzione forall con tipo
forall : (’a -> bool) -> ’a btree -> bool
in modo che (forall p bt) restituisca true se tutti i nodi di bt soddisfano p, restituisca false altrimenti.
Soluzione
let rec forall p bt = match bt with
Void -> true
| Node(x, lbt, rbt) when not (p x) -> false
| Node(x, lbt, rbt) when (p x) -> if (forall p lbt)
then (forall p rbt)
else false;;
ESERCIZIO 2
Definire in CAML una funzione
foo : int list -> int list
in modo che (foo lis) restituisca la lista vuota se tutti gli elementi di lis sono pari, la lista che contiene l’ultimo
elemento dispari di lis altrimenti. Ad esempio:
foo [3;10;20;5;40;30] = [5]
foo [10;2;8] = []
Facoltativo: Definire la funzione foo senza utilizzare ricorsione esplicita.
Soluzione
Soluzione ricorsiva
let rec foo lis = let pari x = x mod 2 = 0 in
match lis with
[] -> []
| x::xs when (pari x) -> foo xs
| x::xs when not (pari x) -> let l= foo xs in if l=[] then [x] else l ;;
Soluzione con foldr
let foo lis = let pari x = x mod 2 = 0 in
let f x y = if pari x then y else
if y=[] then [x] else y
in foldr f [] lis;;
ESERCIZIO 3
Indicare il tipo delle seguenti funzioni
(i)
let f x y = (y x) 2;;
(ii) let h (x,y) = x (y+1) 4;;
(iii)
let rec g x y z = match z with
[] -> []
| w::ws -> (w x y)::(g x y ws);;
Soluzione
let f x y = (y x) 2;;
f : ’a -> (’a -> int -> ’b) -> ’b
let h (x,y) = x (y+1) 4;;
h : (int -> int -> ’a) * int -> ’a
let rec g x y z = match z with
[] -> []
| w::ws -> (w x y)::(g x y ws);;
g : ’a -> ’b -> (’a -> ’b -> ’c) list -> ’c list
ESERCIZIO 4
Definire una funzione ricorsiva f da coppie di naturali in naturali che soddisfi la propriet`a
∀n, m ∈ N. f (n, m) = n
in modo che la relazione di precedenza indotta su N × N sia la seguente
∀n, m, n , m ∈ N. n, m ≺f n , m ≡ (m > 0 ∧ m = m − 1 ∧ n = n + 2)
Facoltativo: Dimostrare per induzione ben fondata la correttezza della definizione data.
Soluzione
Una possibile rappresentazione grafica della relazione indicata `e la seguente
.
.
.
(4,x+2)
|
(2,x+1)
|
(0,x)
.
.
.
(5,x+2)
|
(3,x+1)
|
(1,x)
.
.
.
(y+4,2)
|
(y+2,1)
|
(y,0)
dove x indica un numero naturale e y un numero naturale maggiore di 1.
Dunque:


n
f (n, m) = n


f (n − 2, m − 1) + 2
se m = 0
se n <= 1
se n > 1 ∧ m > 0
Omettiano la domostrazione dei casi base. Dimostriamo il caso induttivo:
f (n, m) = n =⇒ f (n + 2, m + 1) = n + 2
f (n + 2, m + 1)
= {def. di f , terzo caso}
f (n, m) + 2
= {Ip. induttiva}
n+2
ESERCIZIO 5
Date le seguenti definizioni:
struct el {int info; struct el *next;};
typedef struct el ElementoDiLista;
typedef ElementoDiLista *ListaDiInteri;
scrivere in C una procedura che, dati in ingresso attraverso opportuni parametri una lista di interi e un valore x,
elimina, se esiste, il primo elemento della lista preceduto da un elemento che contiene x.
Soluzione
void foo (ListaDiInteri lis, int x)
{ if (lis != NULL)
if (lis->next != NULL)
{ int trovato = 0;
while (lis -> next != NULL && !trovato)
if (lis -> info == x)
{ ListaDiInteri aux = lis -> next;
lis->next = lis->next->next;
free(aux);
trovato=1; }
else lis = lis -> next;
}
}

Download Report