Programmazione – CdS in Matematica
Appello d’esame 14 Luglio 2023
INDICARE SUBITO NOME, COGNOME E MATRICOLA SU TUTTI I FOGLI
PROTOCOLLO CHE VI SONO STATI CONSEGNATI
Scrivere le risposte e commentare i programmi CHIARAMENTE (la chiarezza sarà un
criterio determinante nella valutazione degli esercizi). Scrivere con calligrafia
leggibile. Le parti illeggibili non saranno corrette.
Esercizio 1
A. Scrivere un descrittore di lista che data una lista di matrici L, filtri L, rimuovendo
per ogni matrice M in L, le righe aventi come somma dei propri valori un
numero pari.
Esempio: con
L = [ [[1, 1],[3, 4],[5, 6]],
[[7, 8, 9],[10, 11, 12]],
[[1]],
[[0]] ]
l’output sarà [[[3, 4], [5, 6]], [[10, 11, 12]], [[1]], []].
B. Indicare i valori stampati dal seguente script Python. Mostrare inoltre il
diagramma di stato finale.
x = [['a','b','c']]
y = x[:]
x[len(x)-1][1] = 5
z = y[0][:]
z[2] = x[0]
del z[0]
x = x[0]
print(x,y,z)
Esercizio 2
A. Scrivere la funzione RICORSIVA C(a) dove a è un albero binario a valori interi,
eventualmente vuoto. Questa funzione deve restituire un intero pari alla somma
dei valori dei nodi con due figli meno la somma dei valori dei nodi con un solo
figlio. In caso di albero vuoto restituire 0.
Esempio, data la classe albero:
class A():
def __init__(self, v, l=None, r=None):
self.v = v
self.l = l
self.r = r
e l'albero T = A(3, A(4), A(7, A(1, A(2)), A(5, None, A(9))))
allora C(T) = 4.
B. Definire la funzione ITERATIVA circ(L) che prende in input una lista di
circonferenze definite come coppie ((cx, cy), r) dove (cx, cy) sono le
coordinate del centro e r il raggio. La funzione deve restituire la lista di
circonferenze che non intersecano nessun'altra circonferenza nella lista.
Si ricorda che la distanza tra due punti P1=(x1,y1) e P2=(x2,y2), in un piano 2D,
può essere calcolata come √(𝑥1 − 𝑥2 )2 + (𝑦1 − 𝑦2 )2
Esempio: data la lista di circonferenze:
L = [((0,0),2), ((1,1),3), ((2,2),1), ((1,6),1), ((5,4),1),
((5,1),1)]
allora circ(L) restituirà [((1, 6), 1), ((5, 4), 1)].
Esercizio 3
A. Descrivere dettagliatamente le funzionalità e le assunzioni che devono essere verificate
sui valori dati ai parametri della seguente funzione ricorsiva (ovvero pre e post
condizioni).
def G(a, b):
if not a or not b: return True
return a.v+b.v == 0 and G(a.l, b.l) and G(a.r, b.r)
B. Dare esempi NON BANALI ED ESAUSTIVI di a e corrispondente G(a,b).
C. Dimostrare la correttezza del programma rispetto alle pre/post indicate al punto A.
Esercizio 4
Dire se sono Vere (V) o False (F) le seguenti affermazioni.
NOTA: La vostra risposta dovrà essere o la lettera V, in caso di vero, o F altrimenti.
4.1 Una tupla può sempre essere usata come chiave di un dizionario.
4.2 I dizionari sono tipi associativi
4.3 Nella ricorsione cosiddetta "all’indietro", le operazioni che esegue la funzione
precedono la chiamata ricorsiva.
4.4 Data una lista L, il valore restituito da [Link](x) è la lista L con l’oggetto x
inserito come ultimo elemento.
4.5 La complessità dell’inserimento in un BST (albero binario di ricerca) nel caso
pessimo è O(n) dove n è il numero di nodi.
4.6 Il risultato di un'espressione basata su connettivi logici ritorna sempre un valore
booleano.
4.7 Dato un albero binario completo con n nodi, la sua altezza è di ordine logaritmico
rispetto a n.
4.8 Dato x, riferimento ad una lista di liste, e data la copia y = x[:], allora ogni modifica
alle liste interne di x ha effetto su y.
4.9 Un riferimento non può mai riferire ad un altro riferimento.
4.10 E’ possibile definire una classe senza costruttore.
Esercizio 5
Il 7 e mezzo è un gioco di carte in cui lo scopo è di totalizzare un punteggio più
possibile vicino (minore o uguale) a 7.5. Si gioca con le carte all'italiana:
• valori: (1), 2, 3, ..., Fante (8), Cavallo (9) e Re (10).
• semi: denari, coppe, spade e bastoni e ogni carta vale quanto il suo valore a
meno delle figure (i.e., Fante, Cavallo e Re) che valgono 0.5.
Il gioco si svolge in modo simile al blackjack:
• All'inizio al giocatore viene data una carta;
• il giocatore può poi scegliere se pescare una nuova carta dal mazzo il cui valore
verrà sommato alla sua mano corrente, o fermarsi;
• Il gioco termina quando o il giocatore supera il 7.5 (perde) o si ferma. Se il suo
punteggio finale è > 6 vince, altrimenti perde.
Creare le seguenti classi per simulare una partita a 7 e mezzo.
La classe Carta che rappresenta una carta da gioco che contiene:
• il costruttore __init__(self, valore, seme) che crea una carta con il
valore e il seme indicati;
• il metodo valore(self) che restituisce il valore della carta seguendo le regole
descritta sopra;
• il metodo speciale __str__(self) che restituisce una rappresentazione in
stringa della carta, ad esempio "4 di Coppe";
La classe Mazzo che rappresenta un mazzo di carte (40) all'italiana, che contiene:
• il costruttore __init__(self) che inizializza il mazzo mischiato;
• il metodo pesca(self) che restituisce la carta in cima al mazzo la quale non
potrà più essere pescata durante l'intero turno di gioco.
La classe Sette_Mezzo che gestisce il gioco la quale contiene:
• il metodo round(self) che gestisce un round di 7 mezzo e restituisce True se
il giocatore ha vinto il turno, altrimenti False.
• il metodo play(self, turni=5) che effettua un numero di round di gioco
pari a turni. Il giocatore vince la partita se riesce a vincere più del 50% dei
turni.
Programmazione – CdS in Matematica
Appello d’esame 24 Febbraio 2023
INDICARE SUBITO NOME, COGNOME E MATRICOLA SU TUTTI I FOGLI
PROTOCOLLO CHE VI SONO STATI CONSEGNATI
Scrivere le risposte e commentare i programmi CHIARAMENTE (la chiarezza sarà un
criterio determinante nella valutazione degli esercizi). Scrivere con calligrafia
leggibile. Le parti illeggibili non saranno corrette.
Esercizio 1
A. Sia P una lista di liste di interi, dove ogni sottolista può avere dimensione
arbitraria. Definire un descrittore di lista che ritorna una lista il cui i-esimo
elemento è l’i-esima lista di P, se essa ha numero pari di elementi, altrimenti è la
somma dei suoi elementi.
Esempio: dato P = [[1,2,3], [4,5], [6,-1,8,9], [10], []] il
descrittore ritornerà [6, [4,5], [6,-1,8,9], 10, []].
B. Dire qual è il contenuto delle liste X, Y e Z al termine dell'esecuzione delle
seguenti istruzioni:
X = list(range(2,-4,-2))
Y = X
Y[1] = len(list(range(4,5)))
Z = X[:2]
Z[0] = len(X) (*)
Y[Z[1]] = 5
Y [Z[1]-1] = Z (*)
Mostrare inoltre il diagramma di stato dopo la quinta e l’ultima istruzione
(occorre dunque mostrare due diagrammi separatamente).
Esercizio 2
A. Scrivere la funzione ITERATIVA M(L,v) che data L lista di liste di interi, e un
valore intero v, ritorna la lista dei multipli di v contenuti nella lista di L con il
maggior numero di multipli di v.
Esempio: L = [[2,6,10],[1,2,3,6],[4,16,3,64,40],[22,44,88,4]],
v=4, allora M(L,v) = [4, 16, 64, 40].
B. Dare una funzione RICORSIVA contenuti(P,L) che, data una lista P ed una
lista T di interi (con valori non ripetuti nelle singole liste), ritorna il valore
booleano che indica se tutti gli elementi di P sono contenuti in T nello stesso
ordine, non necessariamente contigui.
Esempio:
T = [0,9,2,10,3,1], P = [2,3,1] ritorna True;
T = [1,2,3,14,5], P = [2,3,1] ritorna False.
Esercizio 3
A. Descrivere dettagliatamente le funzionalità e le assunzioni che devono essere
verificate sui valori dati ai parametri della seguente funzione ricorsiva (ovvero
pre e post condizioni).
def H(a,p):
if not a:
return 0
if p==0:
return a.v>0
else:
return H([Link],p-1)+H([Link],p-1)
B. Dare esempi NON BANALI ED ESAUSTIVI di coppie a,p e corrispondente H(a,p).
C. Dimostrare la correttezza del programma rispetto alle pre/post del punto A.
Esercizio 4
Dire se sono Vere (V) o False (F) le seguenti affermazioni.
NOTA: La vostra risposta dovrà essere o la lettera V, in caso di vero, o F altrimenti.
4.1 Gli alberi binari di ricerca possono contenere esclusivamente valori di tipo
numerico.
4.2 L'ordine delle chiavi in un dizionario rispecchia l'ordine con cui gli elementi sono
stati inseriti.
4.3 In python è possibile passare una funzione come argomento di un’altra funzione.
4.4 Data una lista L, [Link]([1,2,3]) è equivalente a L += [1,2,3].
4.5 La complessità del merge sort nel caso pessimo è O(n2).
4.6 All’interno della definizione del metodo speciale __repr__ è necessario utilizzare la
funzione print().
4.7 Un albero binario di altezza h è completo se ha un numero di nodi pari 2h – 1.
4.8 Dato x, riferimento ad una lista di liste, e data la copia y = x[:], allora ogni modifica
alle liste interne di x non ha alcun effetto su y.
4.9 Un riferimento non può riferire ad un altro riferimento.
4.10 La ricerca di un valore all'interno di un albero binario bilanciato con n nodi ha
complessità O(log2(n)).
Esercizio 5
Si realizzi la classe python Roulette che simula la roulette (semplificata) di un
casinò. In particolare, le puntate possibili sono limitate al singolo numero (da 0 a
36) e la vincita paga 3 volte la puntata del giocatore.
La classe dovrà contenere:
• Un costruttore __init__(self, stacks) che inizializza il tavolo della roulette. stacks
è un dizionario i cui elementi hanno chiave una stringa che rappresenta il nome
del giocatore e come valore l’ammontare di fiches (gettoni) che il giocatore ha a
sua disposizione all’inizio; Aggiungere inoltre tutti gli attributi che risultino utili.
• Il metodo puntata(self, p, n, a) che effettua la puntata del giocatore p sul
numero n di a gettoni. Tale puntata sarà effettuata se e solo se il giocatore è
presente al tavolo, non ha già effettuato una puntata per il giro corrente e ha a
disposizione sufficienti gettoni. Il metodo ritorna True (e aggiorna le dovute
strutture) se la puntata è avvenuta con successo, altrimenti False;
• Il metodo giro(self) che esegue un giro di roulette (genera un numero random
tra 0 e 36), pagando le puntate vincenti e incassando le perdenti;
• Il metodo guadagno_medio(self) che ritorna la media di guadagno del banco
ad ogni giro (guadagno totale/numero di giri effettuati). Notare che tale
guadagno può essere negativo quando il banco è in perdita;
• Il metodo numeri_fortunati(self) che ritorna la lista di numeri che sono stati
estratti il maggior numero di volte. Tale lista avrà un singolo elemento o più
elementi in caso di pari merito tra più numeri.
Programmazione – CdS in Matematica
Appello d’esame 30 Giugno 2023
INDICARE SUBITO NOME, COGNOME E MATRICOLA SU TUTTI I FOGLI
PROTOCOLLO CHE VI SONO STATI CONSEGNATI
Scrivere le risposte e commentare i programmi CHIARAMENTE (la chiarezza sarà un
criterio determinante nella valutazione degli esercizi). Scrivere con calligrafia
leggibile. Le parti illeggibili non saranno corrette.
Esercizio 1
A. Scrivere un unico descrittore di lista che, dato un intero k >= 1, ritorni una
matrice contenente nella diagonale i valori da 1 a k e, per ogni riga, a destra del
valore della diagonale, le potenze intere positive crescenti di tale numero, e a
sinistra, quelle intere negative decrescenti.
Esempio: Dato k = 4 la matrice risultante dovrà essere del tipo:
[[1, 1, 1, 1],
[1, 2, 4, 8],
[0.3333333333333333, 1, 3, 9],
[0.0625, 0.25, 1, 4]]
B. Indicare i valori stampati dal seguente script Python. Mostrare inoltre il
diagramma di stato.
x = [1,4,5]
y = [x for i in range(3)]
c = 2
y[c] = [k for k in x if k<=3]
c = y[:]
c[y[2][0]][0] = -1
[Link](3)
print(x,y,c)
Esercizio 2
A. Scrivere la funzione RICORSIVA mid(L) che data una lista di interi L di lunghezza
dispari ritorna l’intero che si trova al centro della lista.
Esempio: data la lista L = [1,2,3,4,5,6,7], allora mid(L) = 4.
B. Dare una funzione ITERATIVA incluso(P,T)che, data una lista P ed una lista T
di interi positivi, ritorna il valore booleano che indica se per ogni elemento di P
corrispondono elementi in T, nello stesso ordine, non necessariamente contigui,
tale che l’elemento in T sia multiplo dell’elemento in P.
Esempio:
T = [1,9,2,10,5,1,2], P = [2,5,4] ritorna True;
(perché 2 è multiplo di 1, 5 è multiplo di 5 e 4 è multiplo di 1).
T = [4,2,3,14,5], P = [2,6,1] ritorna False.
(perché 2 è multiplo di 2, 6 è multiplo di 3 ma 1 non è multiplo di alcun
elemento rimanente in T).
Esercizio 3
A. Descrivere dettagliatamente le funzionalità e le assunzioni che devono essere
verificate sui valori dati ai parametri della seguente funzione ricorsiva (ovvero
pre e post condizioni).
def U(a, b):
if not a and not b:
return None
if a and b:
return A(a.v+b.v, U(a.l, b.l), U(a.r, b.r))
if a:
return A(a.v, U(a.l, None), U(a.r, None))
return A(b.v, U(None, b.l), U(None, b.r))
B. Dare esempi NON BANALI ED ESAUSTIVI di coppie a,b e corrispondente U(a,b).
C. Dimostrare la correttezza del programma rispetto alle pre/post del punto A.
Esercizio 4
Dire se sono Vere (V) o False (F) le seguenti affermazioni.
NOTA: La vostra risposta dovrà essere o la lettera V, in caso di vero, o F altrimenti.
4.1 Dato un albero BST bilanciato, ovvero avente altezza proporzionale al logaritmo del
numero di nodi, allora la complessità della ricerca è logaritmica.
4.2 Liste e dizionari sono tipi associativi
4.3 In python è possibile passare una funzione come argomento di un’altra funzione.
4.4 Data una lista L, [Link]([1,2,3]) è equivalente a [Link]([1,2,3]).
4.5 Una funzione produce un side-effect (o effetto collaterale) se modifica il valore di
una variabile fornita come parametro.
4.6 All’interno della definizione del metodo speciale __str__ è necessario utilizzare la
funzione print().
4.7 Dato un albero binario completo con n nodi, la sua altezza è di ordine logaritmico
rispetto a n.
4.8 Dato x, riferimento ad una lista di liste, e data la copia y = x[:], allora ogni modifica
alle liste interne di x ha effetto su y.
4.9 Un riferimento può riferire ad un altro riferimento.
4.10 La complessità in tempo nel caso peggiore dell’algoritmo di ordinamento
MergeSort è migliore di quella dell’algoritmo di ordinamento SelectionSort.
Esercizio 5
Creare la coppia di classi Canzone e Playlist che simulano una playlist musicale (ad
esempio di Spotify ® ).
In particolare, la classe Canzone dovrà contenere:
• il costruttore __init__(self, titolo, artista, album) che accetta in input il titolo
della canzone, il nome dell’artista e il titolo dell’album;
• il metodo speciale __repr__(self) che ritorna una stringa che rappresenta la
canzone.
Mentre la classe Playlist dovrà contenere:
• il costruttore __init__(self, titolo) che accetta in input il titolo della playlist;
• il metodo speciale __add__(self, ogg) che ha come parametro il riferimento
ogg che si può assumere essere o una Canzone o una Playlist. Nel caso sia di
tipo Canzone, questa deve essere aggiunta in coda alla playlist. Se invece ogg
rappresenta una Playlist, tutte le canzoni di tale playlist devono essere aggiunte
in coda nell’ordine in cui appaiono in ogg;
Suggerimento: si ricorda che per verificare il tipo di un oggetto o si può
ricorrere alla funzione type(o).
• il metodo speciale __repr__(self) che ritorna una stringa che rappresenta la
playlist;
• il metodo play(self, shuffle=False) che simula l’esecuzione della playlist. Il
parametro shuffle indica se la riproduzione sarà nell’ordine in cui compaiono
le canzoni (False) oppure casuale (True). Per simulare la riproduzione
stampare a video la lista delle canzoni indicandone il numero progressivo.
Ad esempio:
1. Time – Hans Zimmer (Inception OST)
2. Primavera – Ludovico Einaudi (Divenire)
3. ecc…
• il metodo artisti(self) che restituisce l’insieme dei nomi degli artisti contenuti
nella playlist.
Creare infine uno script di test contenente almeno un esempio di invocazione
per ogni metodo implementato.
Programmazione – CdS in Matematica
Appello d’esame 03 Febbraio 2023
INDICARE SUBITO NOME, COGNOME E MATRICOLA SU TUTTI I FOGLI
PROTOCOLLO CHE VI SONO STATI CONSEGNATI
Scrivere le risposte e commentare i programmi CHIARAMENTE (la chiarezza sarà un
criterio determinante nella valutazione degli esercizi). Scrivere con calligrafia
leggibile. Le parti illeggibili non saranno corrette.
Esercizio 1
A. Dato N, scrivere un descrittore di lista che crea una matrice (lista di liste)
quadrata con N righe, tale che ogni elemento sotto la diagonale rappresenta la
sua distanza dalla diagonale e ogni elemento sopra la diagonale è uguale a N.
Esempio (N=3): [[0,3,3],[1,0,3],[2,1,0]].
Esempio (N=4): [[0,4,4,4],[1,0,4,4],[2,1,0,4],[3,2,1,0]].
B. Dire qual è il contenuto delle liste y e z al termine dell'esecuzione delle
seguenti istruzioni:
a = "a"
b = "b"
x = []
y = [x, [b]]
[Link]([1,2]) (*)
z = y[::-1]
y[1][0] = a
z[1][0] = 2 (*)
Mostrare inoltre il diagramma di stato dopo la quarta e l’ultima istruzione.
Occorre dunque mostrare due diagrammi separatamente.
Esercizio 2
A. Definire una funzione ITERATIVA catch_me(L) che, data una lista L di interi
non vuota, scorre L, eventualmente più volte, sommando gli elementi, fino a
trovare un indice i tale per cui la somma ottenuta fino a quel momento divide
L[i]. La funzione ritorna il valore di i trovato.
Esempio 1: Dato L = [11, 7, 7, 7, 5, 3, 8, 2], catch_me(L) restituisce 6 perché
11+7+7+7+5+3 = 40 che è divisibile per 8 che è il settimo (indice 6) elemento di L.
Esempio 2: Dato L = [2, 7, 2, 7], catch_me(L) restituisce 0 perché 2 + 7 + 2 + 7 =
18 che è divisibile per 2 che è il primo (indice 0) elemento di L.
B. Creare una funzione RICORSIVA C(a) dove è un albero binario di ricerca (BST).
Questa funzione deve restituire una coppia (tupla) di interi dove il primo intero
rappresenta il valore minimo e il secondo il valore massimo contenuto in a.
Esempio: Data la classe albero:
class A():
def __init__(self, v, l=None, r=None):
self.v = v
self.l = l
self.r = r
e l'albero T = A(16, A(7, A(1, None, A(4)), A(9)), A(18, None, A(21, A(7))))
allora: C(T) = (1, 21).
Esercizio 3
A. Descrivere dettagliatamente le assunzioni che devono essere verificate sui valori
dati ai parametri e la funzionalità della seguente funzione ricorsiva (ovvero pre e
post condizioni).
B. Dare esempi NON BANALI E ESAUSTIVI di a e corrispondente S(a).
C. Dimostrare la correttezza del programma rispetto alle pre/post del punto A.
def S(a, p=True):
if not a:
return True
return (a.v%2 == p) and S(a.l,not p) and S(a.r,not p)
Esercizio 4
Dire se sono Vere (V) o False (F) le seguenti affermazioni.
NOTA: La vostra risposta dovrà essere o la lettera V, in caso di vero, o F altrimenti.
4.1 Riferimento ad un oggetto è sinonimo di oggetto.
4.2 Tupla, lista e dizionario sono tutti esempi di tipi sequenza.
4.3 In python non è possibile passare una funzione come argomento di un’altra
funzione.
4.4 Dato x = [[1,2],[3,4]], l'assegnamento y = x[:] crea una copia profonda
di x e la assegna a y.
4.5 La complessità del merge sort nel caso pessimo è O(n).
4.6 La definizione di metodi speciali all'interno di una nuova classe è un esempio di
overloading degli operatori.
4.7 Le chiavi di un dizionario devono essere oggetti di un tipo immutabile.
4.8 Dato un albero binario a, l'espressione not a verifica se l'albero è vuoto.
4.9 Dato un albero binario di ricerca (BST) avente n nodi, la complessità della ricerca di
un valore al suo interno è sempre log2(n).
4.10
Nella ricorsione "all’indietro", le operazioni che eseguono la funzione precedono la
chiamata ricorsiva.
Esercizio 5
Creare una classe python Eq2grado che rappresenti un’equazione di secondo grado
del tipo ax2+bx+c=0. Si assume a diverso da 0.
In particolare la classe dovrà contenere i seguenti metodi:
• Un costruttore __init__(self, a, b, c) che inizializza l’equazione con i
coefficienti a,b,c;
• Il metodo speciale __repr__(self) che ritorna una rappresentazione di tipo
stringa dell’equazione. Fare attenzione ai segni e al valore dei coefficienti;
• Il metodo delta(self) che ritorna il valore del delta che si ricorda essere b2 -
4ac;
• Il metodo impossibile(self) che ritorna True se non esistono soluzioni
reali, ovvero delta è < 0, altrimenti False;
• Il metodo solve(self) che ritorna le due soluzioni dell’equazione come tupla
quando esistono altrimenti ritorna None.
• Il metodo speciale __add__(self, eq2) che ritorna un nuovo oggetto della
classe Eq2grado che rappresenta la somma dell’equazione con eq2.
• Si chiede infine di creare una funzione test() che:
o Crea in modo random 100 equazioni di secondo grado;
o Stampa la sua rappresentazione e corrispondente soluzione quando non è
impossibile;
o Ritorna il numero di equazioni risultate impossibili.
Programmazione – CdS in Matematica
Appello d’esame 13 Settembre 2023
INDICARE SUBITO NOME, COGNOME E MATRICOLA SU TUTTI I FOGLI
PROTOCOLLO CHE VI SONO STATI CONSEGNATI
Scrivere le risposte e commentare i programmi CHIARAMENTE (la chiarezza sarà un
criterio determinante nella valutazione degli esercizi). Scrivere con calligrafia
leggibile. Le parti illeggibili non saranno corrette.
Esercizio 1
A. Data A una matrice di dimensione MxN (M e N fissate), utilizzando un descrittore di
lista, definire una lista che contenga tutti i valori della matrice A che siano multipli di 3,
visitando la matrice per colonne.
Esempio:
A = [ [1 ,2 ,9 ,4 ,5 ,6 ],
[8 ,6 ,3 ,4 ,5 ,27],
[15,4 ,1 ,12,2 ,7 ]]
L = [15,6,9,3,12,6,27]
B. Dire qual è il contenuto delle liste X, Y e Z al termine dell'esecuzione delle seguenti
istruzioni:
X = list(range(2,-4,-2))
Y = X
Y[1] = len(range(4,5))
Z = X[:2]
Z[0] = len(X)
Y[Z[1]] = 5
Y [Z[1]-1] = Z
Mostrare inoltre il diagramma di stato dopo l’ultima istruzione.
Esercizio 2
A. Dare una funzione RICORSIVA n_percorsi(n,m) che calcoli il numero di percorsi possibili
in una griglia con n righe e m colonne. I percorsi sono ottenuti a partire dalla cella (0,0)
(quella in alto a sinistra) per arrivare alla cella (n-1, m-1) (quella in basso a destra). Le
mosse a disposizione sono solo le mosse giù e destra.
Suggerimento: per una griglia di una sola riga o una sola colonna si ha un solo
possibile percorso!
Esempio: per una griglia 3x3 si hanno 6 possibili percorsi. Per una griglia 4x3 si hanno
10 possibili percorsi.
B. Scrivere una funzione Inverti(D) che, dato un dizionario D avente chiavi di tipo stringa e
valori di tipo intero, restituisce un nuovo dizionario R nel quale chiavi e valori di D sono
invertite. Nel caso esistano valori ripetuti in D che collidono in una stessa chiave di R, il
valore associato a tale chiave in R sarà la lista delle chiavi di D con tale valore associato.
Esempio: D = {“a”:1, “b”:2, “c”:3, “d”:1, “e”:3},
R = {1:[“a”,”d”], 2:”b”, 3:[“c”,”e”]}
Esercizio 3
A. Descrivere dettagliatamente le funzionalità e le assunzioni che devono essere verificate
sui valori dati ai parametri della seguente funzione ricorsiva (ovvero pre e post
condizioni).
def S(a, p):
if not a: return True
if not a.l and not a.r: return p == a.v
return S(a.l, p-a.v) and S(a.r, p-a.v)
B. Dare esempi NON BANALI E ESAUSTIVI di a,p e corrispondente S(a,p)
C. Dimostrare la correttezza del programma rispetto alle pre/post indicate al punto A.
Esercizio 4
Dire se sono Vere (V) o False (F) le seguenti affermazioni.
NOTA: La vostra risposta dovrà essere o la lettera V, in caso di vero, o F altrimenti.
4.1 All’interno di una funzione è possibile usare una variabile definita all’esterno.
4.2 Il costrutto WHILE è un costrutto di selezione
4.3 Nella ricorsione cosiddetta "in avanti", le operazioni che esegue la funzione
precedono la chiamata ricorsiva.
4.4 Il metodo append della classe list non ha effetti collaterali.
4.5 La complessità della ricerca in un BST (albero binario di ricerca) nel caso pessimo è
O(n) dove n è il numero di nodi.
4.6 La complessità in tempo nel caso peggiore dell’algoritmo di ordinamento
MergeSort è migliore di quella dell’algoritmo di ordinamento BubbleSort.
4.7 Liste, stringhe e tuple sono tutti tipi sequenziali.
4.8 Dato x, riferimento ad una lista, e data la copia y = x[:], allora ogni modifica alla
lista x non ha effetto su y.
4.9 Un riferimento non può mai riferire ad un altro riferimento.
4.10 Un’espressione condizionale quando valutata non ha effetti collaterali a meno che
non li abbiano le espressioni contenute in essa.
Esercizio 5
L'algebra degli intervalli di Allen definisce diverse relazioni possibili tra intervalli temporali, i
quali sono definiti da un'istante di inizio e uno di fine.
Si chiede di creare una classe Interval che implementi i seguenti metodi:
• un costruttore che accetta come parametri l'istante di inizio e di fine dell'intervallo
temporale definiti come numeri reali non negativi.
Consiglio : utilizzare una tupla (inizio, fine). Controllare che l'istante di inizio preceda quello
di fine e che siano effettivamente >=0, se tutte queste condizioni sono verificate creare
l'intervallo (inizio, fine), altrimenti creare l'intervallo vuoto definito come la tupla vuota ();
• definire il metodo length(self) che restituisce la lunghezza dell'intervallo assumendo la
lunghezza dell'intervallo vuoto uguale a -1;
• definire il metodo overlap(self, other) che ritorna vero se l'intervallo sovrappone other 'a
sinistra', ovvero: l'inizio dell'intervallo precede l'inizio di other, la fine dell'intervallo precede
la fine di other e l'inizio di other precede la fine dell'intervallo.
Esempio : x = (3, 10), y = (7, 13).
• definire il metodo meet(self, other) che ritorna vero se l'intervallo termina esattamente
quando inizia other.
Esempio : x = (3, 10), y = (10, 12).
• definire il metodo speciale __and__(self, other) che ritorna un nuovo intervallo che
rappresenta l'intersezione tra l'intervallo e other. Nel caso non ci sia intersezione restituire
un intervallo vuoto.
Esempio : x = (3, 10), y = (7, 13), x and y ritorna l'intervallo (7, 10), mentre se y fosse (11,
91) ritornerebbe ().
Si chiede infine di creare una funzione test() che:
- crea 100 intervalli casuali non vuoti con istante di fine < 100;
- cerca e stampa a video l'intervallo che rappresenta l'intersezione più lunga tra due intervalli
(ovviamente presi tra i 100 creati).