Classe 4 Bi 5-03-2001

Risolvere i seguenti problemi:

1. Sia a1 un atomo contenente 1, a2 un atomo contenente 2, a3 contenente 3, a4 contenente 4, a5 un atomo contenente 5.
Scrivere come si realizzano due delle seguenti liste senza utilizzare la primitiva list:

(1 2 3 4 ) --> cons(a1, cons(a2, cons(a3, cons(a4, make_nil()))));

((1)) --> cons(cons(a1,make_nil()),make_nil()));

(( 1 2 3) 4 ) --> cons(cons(a1, cons(a2,

cons(a3,make_nil()))),make_nil());
( 1 2 3 (4 5)) --> cons(a1, cons(a2, cons(a3, cons(

cons(a4, cons(a5, make_nil())), make_nil())));

2. Sia L una lista omogenea propria di caratteri. Scrivere una function che restituisce la lista a partire da una determinata posizione p di L.

La posizione è determinata dal numero di caratteri precedenti. P sarà quindi un intero che indica il numero di caratteri. La funzione ha in ingresso la lista e un intero.

Se la lista è vuota allora restituisci la lista vuota.
Se p è uguale a zero allora restituisci la lista avuta in ingresso.(Non c'è nulla da fare!!)

altrimenti procedi eliminando il primo elemento della lista e decrementando p di 1.


sexpr ultimi( sexpr s, int p) {
if( null(s) ) return s;
if( p == 0) return s;
return ultimi(cdr(s), p-1);
}

Le prime due condizioni si possono riscrivere così:

if( (null(s)) || (p == 0)) return s;

3. Scrivere una function che, avuto in ingresso una lista non omogenea, restituisce la media dei numeri interi positivi divisibili per 5.

La media aritmetica si calcola sommando tra loro tutti gli elementi che ci interessano dividendoli per la quantità di elementi sommati.

int somma(sexpr l);
int conta(sexpr l);

float media( sexpr l) {
if(conta(l) > 0)
return (float)somma(l) / conta(l);
return -1;

Per sommare gli elementi:

se la lista è vuota la somma è zero
altrimenti
se il primo elemento della lista è "buono" la somma è il primo elemento

+ la somma dei rimanenti
altrimenti la somma è uguale alla somma dei rimanenti.

int somma(sexpr l){
if( null(l) ) return 0;
if( buono(car(l)) )
return *(int*)dato(car(l)) + somma( cdr(l) );
return somma( cdr(l) );
}

int buono( sexpr a ) {
return is_int(a) && (*(int*)dato(a)%5 == 0);
}

int conta(sexpr l){
if( null(l) ) return 0;
if( buono(car(l)) )
return 1 + conta( cdr(l) );
return conta( cdr(l) );
}

4. Scrivere una funzione che, avuto in ingresso una lista omogenea di stringhe, restituisce la lista delle lunghezze.

input: sexpr
output: sexpr

Se la lista in ingresso è vuota restituisce la lista vuota;
altrimenti restituisce l'atomo contenente la lunghezza della prima stringa concatenato a tutti gli altri atomi contenenti le lunghezze delle rimanenti stringhe.

sexpr lunghezze(sexpr l) {
if( null(l) ) return make_nil();
return cons(lungo(car(l)), lunghezze(cdr(l));
}

sexpr lungo (sexpr a){
int *len = malloc(sizeof(int));

*len = strlen((char*)dato(a));
return make_elem(len, INT);
}

5. Scrivere una funzione che, avuto in ingresso una lista omogenea di stringhe, restituisce il numero di stringhe di lunghezza superiore ad n.

input: lista, n
output: intero

se la lista in ingresso è vuota restituisci 0 (non ci sono stringhe di lunghezza superiore ad n).
se la lunghezza della stringa contenuta nel primo elemento della lista è maggiore di n
restituisci 1 + conta le stringhe rimanenti
altrimenti
conta solo le stringhe rimanenti


int conta( sexpr l, int n){
if( null(l) ) return 0;
if(lunghezza(car(l)) > n)
return 1 + conta(cdr(l));
return conta(cdr(l));
}

int lunghezza(sexpr a) {
return strlen((char*)dato(a));
}

6. Scrivere una funzione che, avuto in ingresso una lista omogenea di interi positivi, calcola la somma dei primi n interi.

input: lista, n
output: intero

se la lista è vuota restituisco 0;
se n = 0 restituisco 0

restituisco il primo elemento sommato alla somma dei rimanti n-1;

int somma(sexpr l, int n) {
if( null(l) ) return 0;
if( n == 0 ) return 0;
return *(int*)dato(car(l)) + somma(cdr(l), n-1);
}

Per ogni esercizio svolto produrre, quando possibile, la descrizione del problema e la codifica in C.
Ogni esercizio verrà valutato (punti 1) solo se contiene la codifica.