Programmazione e analisi di dati Modulo A: Programmazione in Java
Paolo Milazzo
Dipartimento di Informatica, Universit`a di Pisa http://pages.di.unipi.it/milazzo
milazzo di.unipi.it
Corso di Laurea Magistrale in Informatica Umanistica A.A. 2017/2018
Altre strutture dati...
In certe situazioni gli array, i vettori e le altre strutture dati fornite dalla Libreria di Java non sono semplici da usare...
Esempio: albero genealogico
Supponiamo di voler scrivere un programma che gestisce un albero genealogico
Abbiamo un individuo, di cui dobbiamo indicare i genitori, i nonni, i bisnonni, ecc...
Possiamo assumere di rappresentare l’individuo tramite unoggetto Il metodosetGenitoriconsente di specificare i genitori dell’individuo I genitori saranno a loro volta individui... di cui si potranno specificare i genitori, ecc...
Albero genealogico (2)
Come deve essere fatta laclasse Individuo?
Deve prevedere una stringa per il nome dell’individuo Deve prevedere riferimenti ai due individui genitori
I ossia, due variabili di tipoIndiviuo
Quindi: la classe Individuo conterr`a riferimenti a oggetti della stessa classe!
p u b l i c c l a s s I n d i v i d u o { // n o m e d e l l ’ i n d i v i d u o p r i v a t e S t r i n g n o m e ;
// r i f e r i m e n t o al p a d r e ( di t i p o I n d i v i d u o ) p r i v a t e I n d i v i d u o p a d r e ;
// r i f e r i m e n t o a l l a m a d r e ( di t i p o I n d i v i d u o ) p r i v a t e I n d i v i d u o m a d r e ;
// c o s t r u t t o r e : i n i z i a l i z z a s o l o il n o m e p u b l i c I n d i v i d u o ( S t r i n g n o m e ) {
// p a d r e e m a d r e i n i z i a l i z z a t i di d e f a u l t a n u l l t h i s. n o m e = n o m e ;
} ( s e g u e )
Albero genealogico (4)
( s e g u e I n d i v i d u o )
// r e s t i t u i s c e il n o m e
p u b l i c S t r i n g g e t N o m e () { r e t u r n n o m e ; } // r e s t i t u i s c e l ’ i n d i v i d u o p a d r e
p u b l i c I n d i v i d u o g e t P a d r e () { r e t u r n p a d r e ; } // i m p o s t a il p a d r e ( se non a n c o r a i m p o s t a t o ) p u b l i c v o i d s e t P a d r e ( I n d i v i d u o p a d r e ) {
if (t h i s. p a d r e == n u l l) t h i s. p a d r e = p a d r e ; }
// r e s t i t u i s c e l ’ i n d i v i d u o m a d r e
p u b l i c I n d i v i d u o g e t M a d r e () { r e t u r n m a d r e ; } // i m p o s t a la m a d r e ( se non a n c o r a i m p o s t a t a ) p u b l i c v o i d s e t M a d r e ( I n d i v i d u o m a d r e ) {
if (t h i s. m a d r e ==n u l l) t h i s. m a d r e = m a d r e ; }
}
Come si usa? Vediamo un main...
p u b l i c c l a s s U s a A l b e r o G e n e a l o g i c o {
p u b l i c s t a t i c v o i d m a i n ( S t r i n g [] a r g s ) {
I n d i v i d u o b a r t = new I n d i v i d u o (" B a r t S i m p s o n ");
I n d i v i d u o m a r g e = new I n d i v i d u o (" M a r g e B o u v i e r ");
b a r t . s e t M a d r e ( m a r g e );
I n d i v i d u o h o m e r = new I n d i v i d u o (" H o m e r S i m p s o n ");
b a r t . s e t P a d r e ( h o m e r );
I n d i v i d u o n o n n o 1 = new I n d i v i d u o (" A b r a h a m S i m p s o n ");
h o m e r . s e t P a d r e ( n o n n o 1 ); // n o t a : m e t o d o i n v o c a t o su h o m e r ! I n d i v i d u o n o n n a 1 = new I n d i v i d u o (" M o n a S i m p s o n ");
h o m e r . s e t M a d r e ( n o n n a 1 ); // n o t a : m e t o d o i n v o c a t o su h o m e r ! I n d i v i d u o n o n n o 2 = new I n d i v i d u o (" C l a n c y B o u v i e r ");
m a r g e . s e t P a d r e ( n o n n o 2 ); // n o t a : m e t o d o i n v o c a t o su m a r g e ! I n d i v i d u o n o n n a 2 = new I n d i v i d u o (" J a c q u e l i n e B o u v i e r ");
m a r g e . s e t M a d r e ( n o n n a 2 ); // n o t a : m e t o d o i n v o c a t o su m a r g e ! }
Albero genealogico (6a)
Albero genealogico (6c)
Albero genealogico (6e)
E se volessimo stampare l’albero genealogico (tramite un nuovo metodo stampaAlberoGenealogico())?
Ad esempio, cercando di ottenere questo risultato:
B a r t S i m p s o n - - H o m e r S i m p s o n - - - - A b r a h a m S i m p s o n - - - - M o n a S i m p s o n - - M a r g e S i m p s o n - - - - C l a n c y B o u v i e r - - - - J a c q u e l i n e B o u v i e r
Albero genealogico (8)
Per poter stampare l’albero genealogicodi un individuo, il metodo stampaAlberoGenealogico() dovrebbe:
stampare il nome dell’individuo su cui `e chiamato stampare l’albero genealogicodel padre
stampare l’albero genealogicodella madre Ma....
anche il padre e la madre sono individui...
la funzionalit`a di stampa dell’albero genealogico di un individuo la stiamo definendo ora...
questo `e uncane che si morde la coda...
Tutto sotto controllo!
Il metodo stampaAlberoGenealogico() che stiamo definendo `ericorsivo al suo interno richiama se stesso!
// n u o v o m e t o d o d e l l a c l a s s e I n d i v i d u o p u b l i c v o i d s t a m p a A l b e r o G e n e a l o g i c o () {
S y s t e m . out . p r i n t l n ( n o m e );
if ( p a d r e !=n u l l) p a d r e . s t a m p a A l b e r o G e n e a l o g i c o ();
if ( m a d r e !=n u l l) m a d r e . s t a m p a A l b e r o G e n e a l o g i c o ();
}
// u t i l i z z o del m e t o d o ( a g g i u n t o in f o n d o al m a i n ) b a r t . s t a m p a A l b e r o G e n e a l o g i c o ();
Albero genealogico (10)
Attenzione: il controllo padre!=null (analogo per madre) serve per due motivi:
se il padre (o la madre) `e null non abbiamo niente da stampare per quanto lo riguarda
se la variabile padre `e null, il comando
padre.stampaAlberoGenealogico() da un errorea tempo di esecuzione
I eccezione NullPointerException
Risultato:
B a r t S i m p s o n H o m e r S i m p s o n A b r a h a m S i m p s o n M o n a S i m p s o n M a r g e B o u v i e r C l a n c y B o u v i e r J a c q u e l i n e B o u v i e r
Mancano i trattini prima dei nomi degli avi!
Albero genealogico (11)
Proviamo a modificare il metodo...
// n u o v o m e t o d o d e l l a c l a s s e I n d i v i d u o p u b l i c v o i d s t a m p a A l b e r o G e n e a l o g i c o () {
S y s t e m . out . p r i n t l n ( n o m e );
if ( p a d r e !=n u l l) {
S y s t e m . out . p r i n t (" - - ");
p a d r e . s t a m p a A l b e r o G e n e a l o g i c o ();
}
if ( m a d r e !=n u l l) {
S y s t e m . out . p r i n t (" - - ");
m a d r e . s t a m p a A l b e r o G e n e a l o g i c o ();
} }
Risultato:
B a r t S i m p s o n - - H o m e r S i m p s o n - - A b r a h a m S i m p s o n - - M o n a S i m p s o n - - M a r g e B o u v i e r - - C l a n c y B o u v i e r - - J a c q u e l i n e B o u v i e r
Non ci siamo ancora...
Il numero di trattini che devono essere stampati in ogni riga dipende da “quanto vecchio” `e l’individuo
ossia, da quanto `e lontano dall’individuo radice dell’albero (bart) Soluzione: aggiungere un contatore da passare da un individuo ai suoi genitori incrementandolo ogni volta
Albero genealogico (13)
Nuovo tentativo...
Ora il metodo ricorsivo prevede anche un parametro intero (il contatore)
// n u o v o m e t o d o d e l l a c l a s s e I n d i v i d u o
p u b l i c v o i d s t a m p a A l b e r o G e n e a l o g i c o (int c o n t a t o r e ) { // s t a m p a t a n t i t r a t t i n i q u a n t i i n d i c a t i da c o n t a t o r e for (int i =0; i < c o n t a t o r e ; i ++)
S y s t e m . out . p r i n t l n (" - - ");
S y s t e m . out . p r i n t l n ( n o m e );
// c h i a m a t e r i c o r s i v e con c o n t a t o r e a u m e n t a t o
if ( p a d r e !=n u l l) p a d r e . s t a m p a A l b e r o G e n e a l o g i c o ( c o n t a t o r e + 1 ) ; if ( m a d r e !=n u l l) m a d r e . s t a m p a A l b e r o G e n e a l o g i c o ( c o n t a t o r e + 1 ) ; }
Modifichiamo anche la chiamata nel main
// all ’ i n i z i o il c o n t a t o r e e ’ 0 ( non s e r v o n o t r a t t i n i per b a r t )
Risultato:
B a r t S i m p s o n - - H o m e r S i m p s o n - - - - A b r a h a m S i m p s o n - - - - M o n a S i m p s o n - - M a r g e B o u v i e r - - - - C l a n c y B o u v i e r - - - - J a c q u e l i n e B o u v i e r
Ci siamo!
La struttura dati Albero (1)
La struttura dati che abbiamo usato per realizzare l’albero genealogico prende il nome di Albero
Un albero:
E’ costituito da nodi (in Java sono oggetti) tra i quali esiste unarelazione padre-figlio Ha un nodo radice(senza padri) Ha nodi foglia(senza figli)
Un sottoalbero`e una porzione di un albero che consiste di un nodo
Il numero di figli di ogni nodo di un albero pu`o essere fiassato o variabile Quando il numero dei figli di ogni nodo `e fissato a 2, l’albero si dice binario (come nell’esempio dell’albero genealogico)
La struttura dati Albero (3)
Quando il numero dei figli di ogni nodo `e fissato a 1, l’albero in realt`a descrive una lista concatenata
Una lista concatenata `e una struttura dati che in Java si usa raramente le sue funzionalit`a (aggiungere e togliere elementi dalla sequenza) sono simili a quelle di Vector, ArrayList e altre strutture dati presenti nella Libreria Standard
Quando il numero dei figli di ogni nodopu`o variare, in Java di solito i riferimenti ai figli si memorizzano tramite vettori
La struttura dati Albero (5)
Esempio: I generi letterari dei libri di una biblioteca Ogni generi (es. prosa, poesia, ....)
... ha tanti sotto-generi ( es. romanzi, racconti, ....)
... che prevedono sotto-sotto-generi (es. romanzo storico, romanzo di avventura, ...)
p u b l i c c l a s s G e n e r e L e t t e r a r i o { p r i v a t e S t r i n g n o m e G e n e r e ;
p r i v a t e Vector < G e n e r e L e t t e r a r i o > s o t t o g e n e r i ; // ... c o s t r u t t o r i e m e t o d i
}
Generalizzando un po’ la definizione di albero, otteniamo un grafo
Un grafo:
E’ costituito da nodi (in Java sono oggetti)
I nodi sono collegati daarchi(in Java sono riferimenti, o oggetti aggiuntivi)
Molti programmi richiedono l’uso di grafi (es. gestione reti ferroviarie e stradali, social network, World Wide Web, ....)
Gli algoritmi che utilizzano grafi possono essere piuttosto complicati si va ben oltre gli scopi di questo corso...
La ricorsione (1)
Un programma `e detto ricorsivo quando risolve un problema di una certa dimensione riutilizzando se stesso su un problema di dimensione minore Nell’esempio dell’albero genealogico:
il metodo che stampa l’albero(di un individuo) riutilizza se stesso per stampare un sottoalbero(di un geniore dell’individuo)
L’approccio ricorsivosi contrappone all’approccio iterativoin cui i problemi sono risolti mediante cicli
L’approccio ricorsivo pu`o essere molto efficace (consente di scrivere alcuni programmi in poche righe) ma:
pu`o essere difficile da imparare ad utilizzare propriamente se usato impropriamente pu`o causare problemi (es. mancata
Confrontiamo l’approccio iterativo e l’approccio ricorsivo.
Esempio (classico): Il calcolo del fattoriale n! = n · n − 1 · ... · 2 · 1
// s o l u z i o n e i t e r a t i v a
p r i v a t e int f a t t o r i a l e I t e r a t i v o (int n ) {
int ris = 1;
for (int i =1; i <= n ; i ++) ris *= i ;
r e t u r n ris ; }
// s o l u z i o n e r i c o r s i v a
p r i v a t e int f a t t o r i a l e R i c o r s i v o (int n ) { if ( n = = 0 ) r e t u r n 1;
e l s e r e t u r n n * f a t t o r i a l e R i c o r s i v o ( n - 1 ) ; }
La ricorsione (3)
L’approccio ricorsivo `e abbastanza comune inmatematica:
definiamo la funzione matematicafattoriale(n)
fattoriale(n) =
(1 se n = 0;
n · fattoriale(n − 1) altrimenti
Come tutte le chiamate di metodi, le chiamate ricorsive sono gestite tramite record di attivazione (rivedere lezioni precedenti)
La chiamata ricorsiva:
sospende il metodo in corso di esecuzione
attiva il metodo chimamato (una nuova istanza dello stesso metodo) quando al termine del metodo chiamato il controllo ritorna al
chiamante
La ricorsione (5)
Esempio di metodo ricorsivo:
p u b l i c v o i d e s e m p i o R i c o r s i o n e (int i ) { if ( i = = 0 ) S y s t e m . out . p r i n t l n (" E C C O 0 ");
e l s e {
S y s t e m . out . p r i n t l n (" P R I M A " + i );
e s e m p i o R i c o r s i o n e ( i - 1 ) ;
S y s t e m . out . p r i n t l n (" D O P O " + i );
} }
Chiamando il metodo come segue:
e s e m p i o R i c o r s i v o ( 3 ) ;
Il risultato sar`a:
P R I M A 3 P R I M A 2 P R I M A 1 E C C O 0 D O P O 1
Un metodo ricorsivo deve prevedere un numero di casi che varia a seconda del problema da affrontare
Dobbiamo avere:
uno o pi`u casi baseche risolvono il problema senza bisogno di chiamate ricorsive
uno o pi`u casi ricorsivi che hanno bisogno di effettuare chiamate ricorsive per risolvere sottoproblemi
p r i v a t e int f a t t o r i a l e R i c o r s i v o (int n ) { if ( n = = 0 ) r e t u r n 1; // c a s o b a s e
e l s e r e t u r n n * f a t t o r i a l e R i c o r s i v o ( n - 1 ) ; // c a s o r i c o r s i v o }
La ricorsione (7)
La condizione necessaria affinch`e la ricorsione possa funzionare `e che le chiamate ricorsive prima o poi raggiungano un caso base
altrimenti il programmanon terminerebbe mai... eseguirebbe chiamate ricorsive all’infinito
Vediamo un esempio di programma ricorsivo mal posto.
che succede se si invoca il metodo con parametro dispari?
p r i v a t e int f a t t o r i a l e D i f e t t o s o (int n ) { if ( n = = 0 ) r e t u r n 1; // c a s o b a s e
e l s e r e t u r n n * f a t t o r i a l e R i c o r s i v o ( n - 2 ) ; // c a s o r i c o r s i v o }
Rivediamo l’esempio della stampa dell’albero genealogico
// n u o v o m e t o d o d e l l a c l a s s e I n d i v i d u o
p u b l i c v o i d s t a m p a A l b e r o G e n e a l o g i c o (int c o n t a t o r e ) { // s t a m p a t a n t i t r a t t i n i q u a n t i i n d i c a t i da c o n t a t o r e for (int i =0; i < c o n t a t o r e ; i ++)
S y s t e m . out . p r i n t l n (" - - ");
S y s t e m . out . p r i n t l n ( n o m e );
// c h i a m a t e r i c o r s i v e con c o n t a t o r e a u m e n t a t o
if ( p a d r e !=n u l l) p a d r e . s t a m p a A l b e r o G e n e a l o g i c o ( c o n t a t o r e + 1 ) ; if ( m a d r e !=n u l l) m a d r e . s t a m p a A l b e r o G e n e a l o g i c o ( c o n t a t o r e + 1 ) ; }
In questo esempio:
Abbiamoricorsione multipla (2 chiamate ricorsive)
Il caso base lo si ha quando padre e madre sono entrambi null (si stampa solo il nome)
Il sottoproblema non `e identificato dalparametro del metodo, ma dall’oggettosu cui il metodo `e invocato
quando `e chiamato su bart, radice dell’albero intero...
Esempio: la ricerca dicotomica (o binaria) (1)
Vediamo un esempio complesso di programma ricorsivo:
Laricerca dicotomica (oricerca binaria)
Supponiamo di avere un array ordinatocontenente interi vogliamo sapere se un certo numero`e contenuto nell’array
Prima soluzione (iterativa)
p u b l i c c l a s s R i c e r c a {
p u b l i c s t a t i c v o i d m a i n ( S t r i n g [] a r g s ) { // a r r a y o r d i n a t o di l u n g h e z z a 12
int[] a = { 2 , 3 , 6 , 8 , 9 , 10 , 14 , 15 , 21 , 22 , 24 , 30 , 41 };
b o o l e a n t r o v a t o = r i c e r c a ( a , 1 9 ) ; // r e s t i t u i s c e f a l s e }
// r e s t i t u i s c e t r u e se x e ’ p r e s e n t e in a p r i v a t e b o o l e a n r i c e r c a (int[] a , int x ) {
b o o l e a n t r o v a t o = f a l s e; for (int y : a ) {
if ( x == y ) t r o v a t o =t r u e; }
r e t u r n t r o v a t o ; }
}
Esempio: la ricerca dicotomica (o binaria) (3)
Ragioniamo un attimo:
l’algoritmo che abbiamo implementato va a guardare tutti i valori dell’array
I se l’array `e grande, questo pu`o richiederetempo
non abbiamo sfruttato il fatto che gli elementisono ordinati Idea: come si cerca di solito una parola in un vocabolario?
Altra soluzione:
leggiamo il valore centrale dell’array e lo confrontiamo con il valore cercato
il confronto ci dice se continuare la ricerca nella met`a di destra o di sinistra dell’array
ripetiamo la ricerca ricorsivamentenella met`a selezionata Quanti numeri dovremo leggere?
Ad ogni passo ne buttiamo via la met`a senza leggerli
Alla fine avremo confrontato il numero cercato con un numero di valori dell’array pari al logaritmo della dimensione (quindi molti meno)
I Nell’esempio i numeri erano 12, ma bastano 3 confronti...
Esempio: la ricerca dicotomica (o binaria) (5)
p u b l i c c l a s s R i c e r c a B i n a r i a {
p u b l i c s t a t i c v o i d m a i n ( S t r i n g [] a r g s ) { // a r r a y o r d i n a t o di l u n g h e z z a 12
int[] a = { 2 , 3 , 6 , 8 , 9 , 10 , 14 , 15 , 21 , 22 , 24 , 30 , 41 };
b o o l e a n t r o v a t o = r i c e r c a B i n a r i a ( a , 0 , a . length , 1 9 ) ; // r e s t i t u i s c e f a l s e }
// r e s t i t u i s c e t r u e se x e ’ p r e s e n t e in a
// sx e dx s o n o gli e s t r e m i d e s t r o e s i n i s t r o d e l l a p o r z i o n e // di a r r a y che si c o n s i d e r a
p u b l i c b o o l e a n r i c e r c a B i n a r i a (int[] a , int sx , int dx , int x ) { b o o l e a n t r o v a t o ;
if ( sx <= dx ) {
int c e n t r o = ( sx + dx ) / 2 ; // c a l c o l a il c e n t r o if ( x < a [ c e n t r o ])
r e t u r n r i c e r c a B i n a r i a ( a , sx , centro -1 , x );
if ( x > a [ c e n t r o ])
r e t u r n r i c e r c a B i n a r i a ( a , c e n t r o +1 , dx , x );
if ( x == a [ c e n t r o ]) r e t u r n t r u e; }
e l s e
r e t u r n f a l s e;
