Esercizi di preparazione all'esame: programmazione funzionale e parallela (2016-2017)
Esercizio 1: massimo comun divisore
Si scriva una funzione Scala 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
Soluzione:
def mcd(x:Int, y:Int):Int = if (y==0) x else mcd(y, x%y)
Esercizio 2: somma dei quadrati
Si scriva una funzione Scala che, dati due interi x e y con x<=y, calcola la somma dei quadrati dei numeri da x a y, compresi.
Soluzione:
def sommeQuad(x:Int, y:Int):Int = if (x>y) 0 else x*x + sommeQuad(x+1, y)
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.
Si suggerisce di 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.
Soluzione:
def sqrt(x:Double) = {
val epsilon = 0.0001
def abs(x:Double) = if (x<0) -x else x
def trovataBuonaStima(y:Double, x:Double) = abs(y*y-x) < epsilon
def stimaMigliore(y:Double, x:Double) = (y+x/y)/2.0
def raffinaSqrt(y:Double, x:Double):Double = if (trovataBuonaStima(y,x)) y else raffinaSqrt(stimaMigliore(y,x), x)
raffinaSqrt(1.0, x)
}
println("Radice quadrata di 2 ~ "+sqrt(2))
Esercizio 4: composizione di funzioni
Scrivere una funzione Scala
componi che, date due funzioni
f1:Int=>Int e
f2:Int=>Int, restituisce una funzione
f che compone
f1 ed
f2, calcolando
f(x)=f1(f2(x)). Deve essere possibile eseguire questo programma:
val f = componi(x=>x*x, x=>x+1)
println(f(9)) // stampa 100
Esercizio 5: 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 6: 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 7: funzioni di ordine superiore
Si considerino le definizioni:
def f(y:Int): Int=>Int = x => x+y
def g(f:Int=>Int): Int=>Int = x => f(f(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 8: 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 9: test di primalità
Scrivere una funzione Scala che verifica se un numero è primo.
Esercizio 10: 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 11: ricorsione di coda
Si fornisca una variante della soluzione dell'Esercizio 2 che esibisca ricorsione di coda.
Esercizio 12: 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 13: 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 14: 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 15: 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 16: funzione filter su liste (alla vaccinara)
Scrivere una funzione Scala
ricorsiva filter che, data una lista e un predicato booleano, si comporta come la
filter predefinita delle liste. Esempio di uso:
val l = List(3,1,2,4,5)
println(filter(l, _>2)) // stampa 3,4,5
Esercizio 17: 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 18: 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 19: 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 20: 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 21: 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 22: 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 23: 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 24: 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 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() {
override def run
() {
val ex =
new Frame2D
(l,width,height
)
ex.
setVisible(true)
}
})
}
}
class Frame2D
(l:
List[Shape], width:Int, height:Int
) extends JFrame {
class Surface2D
extends JPanel {
def doDrawCircle
(c:Circle, g2d:
Graphics2D) {
val xc =
(width*
(c.
x-c.
r)).
toInt
val yc = height/
2-
(height*
(c.
y-c.
r)).
toInt
val wc =
(2*width*c.
r).
toInt
val hc =
(2*height*c.
r).
toInt
g2d.
drawOval(xc, yc, wc, hc
)
}
def doDrawLine
(l:
Line, g2d:
Graphics2D) {
val x1 =
(width*l.
x1).
toInt
val y1 = height-
(height*l.
y1).
toInt
val x2 =
(w