Esercizi di preparazione all'esame: programmazione funzionale e parallela (2016-2017)
Esercizio 1: massimo comun divisore
Si scriva una funzione Scala
mcd che calcola il massimo comun divisore (MCD) di due numeri interi. Usare la seguente definizione ricorsiva:
MCD(x,y)=x, se y=0
MCD(x,y)=MCD(y, resto della divisione di x per y) altrimenti
Esercizio 2: somma dei quadrati
Si scriva una funzione Scala ricorsiva
sumOfSquares che, dati due interi x e y con x<=y, calcola la somma dei quadrati dei numeri da x a y, compresi.
Esercizio 3: calcolo della radice quadrata approssimata
Un semplice metodo iterativo basato sul metodo di Newton per calcolare la radice quadrata di un numero x consiste nel partire da una stima iniziale y (es. y=1) e raffinarla successivamente calcolando la media tra y e x/y. Il procedimento termina quando il quadrato della stima è sufficientemente vicino a x. Completare la seguente definizione usando un approccio ricorsivo:
def sqrt(x:Double) = {
// completare...
}
println("Radice quadrata di 2 ~ "+sqrt(2))
- Suggerimento: scomporre sempre un problema in funzioni più semplici. Questo non peggiora in pratica le prestazioni poiché il compilatore effettua inlining automaticamente, ma migliora molto la leggibilità, l'analisi di correttezza e la manutenibilità del codice. Definire funzioni annidate (es. per il calcolo del valore assoluto, ecc.).
Esercizio 4: funzioni di ordine superiore
Scrivere una funzione Scala
somma che, dato come parametro una funzione
f:Int=>Int, restituisce una funzione che prende come parametri due interi
a e
b e restituisce la somma di
f(x) per ogni
x compreso tra
a e
b (estremi inclusi). Deve essere possibile eseguire questo programma:
val sommaQuadrati = somma(x=>x*x)
println(sommaQuadrati(1,3)) // stampa 14 (somma dei quadrati di 1, 2 e 3)
Esercizio 5: funzioni di ordine superiore
Scrivere una funzione Scala
applicaDueVolte che, dati come parametri una funzione
f:Int=>Int e un intero
x, calcola
f(f(x)). Deve essere possibile eseguire questo programma:
val y = applicaDueVolte(x=>x+1, 10)
println(y) // stampa 12
Esercizio 6: funzioni di ordine superiore
Si considerino le definizioni:
def f(y:Int): Int=>Int = x => x+y
def g(h:Int=>Int): Int=>Int = x => h(h(x))
Per ciascuna delle seguenti espressioni, dire se è corretta e, in caso affermativo, che tipo ha:
- x=>f(x)
- f(10)
- f(10)(20)
- f(10)(20)(30)
- g(f)
- g(f(1))
- g(x=>2*x)
- g(g(g(x=>2*x)))
- g(g(g(x=>2*x)))(2)
Esercizio 7: funzioni parzialmente applicate
Si consideri il seguente metodo parzialmente applicato:
def f(a:Int)(b:Int)(c:Int) = a+b+c
Per ciascuna delle seguenti espressioni, dire se è corretta e, in caso affermativo, che tipo ha:
- f(1)(2)(3)
- f(1)(2) _
- f(1) _
- f _
Esercizio 8: test di primalità
Scrivere una funzione Scala che verifica se un numero è primo.
Esercizio 9: numeri di Fibonacci
Scrivere una funzione Scala che calcola l'n-esimo numero di Fibonacci F(n), dove F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=5, ecc.
Esercizio 10: uguaglianza parziale di funzioni
Scrivere una funzione Scala che, date due funzioni
f1:Int=>Int e
f2:Int=>Int e un intero
n, verifica che
f1 e
f2 calcolino lo stesso valore su ogni input compreso tra
0 e
n. La funzione deve restituire un
Boolean.
Esercizio 11: costruzione di funzioni per casi
Scrivere una funzione Scala
concatena che, date tre funzioni
f1:Double=>Double,
f2:Double=>Double e
f3:Double=>Double e due valori
Double a e
b con
a<=
b, restituisce una funzione che coincide con
f1 per tutti gli argomenti prima di
a, con
f2 nell'intervallo
[a,b], e con
f3 dopo b.
Esercizio 12: uso di map e reduce su liste
Scrivere un metodo
max che, data una lista di stringhe, restituisce la lunghezza della stringa più lunga.
- Suggerimento: usare map e reduce
Esercizio 13: funzione equal su liste (alla vaccinara)
Scrivere una funzione Scala
ricorsiva equal che verifica se due liste di interi sono uguali (uguaglianza profonda).
- Suggerimento: usare head, tail e isEmpty
Esercizio 14: funzione map su liste (alla vaccinara)
Scrivere una funzione Scala
ricorsiva mymap che, data una lista e una funzione, si comporta come la
map predefinita delle liste. Esempio di uso:
val l = List(3,1,2,4,5)
println(mymap(l, _+1)) // stampa 4,2,3,5,6
Esercizio 15: minimo e massimo di una lista
Scrivere una funzione Scala
ricorsiva minMax che, data una lista
non vuota di interi, restituisce una coppia
(min,max), dove
min e
max sono il minimo e il massimo elemento della lista, rispettivamente. Nota: data una coppia
t=(a,b),
t._1 è il primo elemento,
t._2 è il secondo elemento.
Scrivere inoltre una variante
non ricorsiva basata sui metodi standard della classe
List visti a lezione.
Esercizio 16: processamento dati di un sensore
Un sensore misura il numero di veicoli che passano in un tratto stradale in ogni minuto, producendo una lista di interi. Occasionalmente, il sensore smette di funzionare e richiede manutenzione. Quando il sensore smette di funzionare, produce un intero negativo e da quel momento in poi i numeri prodotti sono inattendibili.
Scrivere un metodo
mediaVeicoli(l:List[Int]):Double che calcola il numero medio di veicoli al minuto, ignorando tutti i valori a partire dal primo negativo. Il metodo deve essere realizzato in uno stile funzionale utilizzando i metodi di ordine superiore delle liste (e non iterazione o ricorsione).
Esercizio 17: verifica se una lista di interi contiene duplicati
Scrivere un metodo
allDistinct[T](l:List[T]):Boolean che restituisce
true se e solo se la lista di interi non contiene duplicati. Per motivi prestazionali, è possibile assumere che il dominio degli elementi sia totalmente ordinato e scrivere
allDistinct[T<%Ordered[T]](l:List[T]):Boolean
Esercizio 18: numero elementi inferiori
Scrivere un metodo
inferiori(l:List[Int]):List[(Int,Int)] che, data una lista di interi, restituisce una lista di coppie contenente gli elementi distinti della lista e il corrispondente numero di elementi più piccoli.
Esempio:
println(inferiori(List(1,3,1,2,2,1))) // deve restituire List((1,0), (2,3), (3,5))
Esercizio 19: ricerca di un elemento in una lista
Scrivere una funzione generica
find[T](x:T, l:List[T]):Boolean che, dato un elemento
x, verifica se è presente nella lista
l. Usare il costrutto
match e non
if ... else.
Esercizio 20: rimozione duplicati
Scrivere una funzione generica
removeDuplicates[T](l:List[T]):List[T] che crea una nuova lista ottenuta da
l rimuovendo gli elementi duplicati.
Esercizio 21: unione di liste
Scrivere una funzione generica
union[T](l1:List[T], l2:List[T]):List[T] che costruisce l'unione di due liste. La lista restituita non deve contenere duplicati.
Esercizio 22: intersezione di liste
Scrivere una funzione generica
intersection[T](l1:List[T], l2:List[T]):List[T] che costruisce l'intersezione di due liste. La lista restituita non deve contenere duplicati.
Esercizio 23: estensione del linguaggio con nuovi costrutti
Il nome Scala è un acronimo di SCAlable LAnguage, che riflette il design del linguaggio orientato all'estensibilità. In Scala è possibile introdurre nuovi costrutti sfruttando il meccanismo del passaggio dei parametri per nome e la flessibilità nell'invocazione dei metodi senza dover mettere argomenti tra parentesi.
Questo esercizio richiede di definire un costrutto
repeat(n) I che ripete l'istruzione
I per
n volte, dove
n è un
Int. Deve essere possibile scrivere:
repeat(3) {
println("ciao")
}
che esegue tre volte la stampa.
- Suggerimento: definire un metodo repeat parzialmente applicato dove il secondo parametro è un Unit passato per nome.
Esercizio 24: query su collezioni
Completare il seguente frammento di programma usando for comprehension:
case class Studente
(val nome:
String, val età:Int, val esami:
List[String])
val q =
List(
Studente
("Marco",
23,
List("PFP",
"SC")),
Studente
("Laura",
19,
List("SC",
"FI1",
"PFP")),
Studente
("Stefano",
23,
List("SC",
"FI1")),
Studente
("Marco",
25,
List("SC",
"FI1",
"FI2")),
Studente
("Paola",
22,
List("SC",
"PFP"))
)
val query1 =
// estrarre tutti gli studenti con età compresa tra 20 e 24 anni (inclusi) che hanno sostenuto l'esame di "PFP"
// stampare i dati degli studenti in query1
val query2 =
// estrarre tutti gli studenti con età strettamente inferiore a 24 anni che hanno sostenuto almeno due esami
// stampare i dati degli studenti in query2
Esercizio 25: classe per numeri razionali
Scrivere una classe Rational che rappresenta numeri razionali della forma num/den, dove num e den sono interi. Scrivere la classe in modo che sia possibile eseguire il seguente frammento Scala:
val r1 = new Rational(2, 7)
val r2 = new Rational(8, 6)
val r3 = new Rational(4,14)
println(r1+r2) // stampa 34/21
println(r1-r2) // stampa -22/21
println(r1*r2) // stampa 8/21
println(r1/r2) // stampa 3/14
println(r1==r3) // stampa true
println(r1!=r2) // stampa true
println(r1<r2) // stampa true
println(r2<r1) // stampa false
- Suggerimento: calcolare il massimo comun divisore di numeratore e denominatore per riportare la frazione ai minimi termini (o irriducibile). Ad esempio, 4/14 dovrebbe essere memorizzato in un oggetto Rational come 2/7.
Esercizio 26: disegno di una griglia n x n (grafica 2D)
Completare il metodo
get dell'object
Model2D seguente in modo che costruisca un modello 2D che raffigura una griglia
n x n. La figura è creata utilizzando esclusivamente segmenti di linea. La figura deve essere confinata nello spazio quadrato bidimensionale di lato unitario delimitato dall'origine degli assi fino al punto di coordinate (1,1). La figura viene poi scalata automaticamente dal modulo di visualizzazione per occupare la dimensione della finestra. Si ricordi che da Scala è possibile accedere a tutte le funzioni delle librerie Java (es. quelle della classe
Math se dovessero servire).
Per compilare da riga di comando usare:
scalac Frame2D.scala Shape.scala Model2D.scala.
object Model2D
{
def getGrid
(n:Int
) =
{
// completare costruzione di un modello 2D di una griglia con n linee verticali ed n linee orizzontali
List(new Line(0.0,
0.0,
1.0,
1.0)) // esempio di linea
}
def main
(args:
Array[String]) {
println
("Displaying 20x20 grid...")
Frame2D.
display(Model2D.
getGrid(20),
500,
500)
}
}import java.awt.{EventQueue,Graphics,Graphics2D,Dimension}
import javax.swing.{JFrame,JPanel}
object Frame2D
{
def display
(l:
List[Shape], width:Int, height:Int
) {
EventQueue.
invokeLater(new Runnable(