Corso di Laurea Ingegneria Informatica Fondamenti …...java/fondinf/ Array e Oggetti 1 Corso di...

1 http://www.dia.uniroma3.it/~java/fondinf/ Array e Oggetti

Corso di Laurea Ingegneria Informatica Fondamenti di Informatica

Dispensa 17 Array e Oggetti

A. Miola Gennaio 2012


Contenuti

q Array paralleli

q Array e oggetti

q Ricerca sequenziale

q Ricerca binaria

q Fusione di sequenze ordinate


Array paralleli q Un insieme di array paralleli è un insieme formato da due

o più array della stessa lunghezza, in cui gli elementi che occupano una stessa posizione formano un gruppo correlato di dati come nel caso degli array nomi e voti nel problema degli studenti da promuovere

Rossi Verdi

Bianchi Gialli

Neri

0 1 2 3

19

nomi

8.1 3.2 5.2 5.6

8.5

0 1 2 3

19

voti

dati sullo studente Bianchi individuati nei due array dallo stesso indice 2


Array e oggetti

q Gli elementi di un array possono essere dei riferimenti a oggetti §  il problema degli studenti da promuovere può essere

risolto usando un array di oggetti, in cui ciascun elemento è un oggetto che rappresenta i dati di uno studente la relativa valutazione

§  è una alternativa che può essere preferita agli array paralleli


Un array di oggetti

0 vs

oggetto dati per lo studente

Bianchi

nome = Rossi voto = 8.1

v0 nome = Verdi

voto = 3.2

v1 nome = Bianchi

voto = 5.2

v2 nome = Gialli

voto = 5.6

v3 nome = Neri

voto = 8.5

v19

1 2 3 19

…


La classe Valutazione /* Un oggetto Valutazione rappresenta il nome * di uno studente e la votazione che ha ricevuto. */ class Valutazione { /* Il nome dello studente. */ private String nome; /* La votazione ricevuta dallo studente. */ private double voto; /* Crea una nuova Valutazione, dati nome e votazione. */ public Valutazione(String nome, double voto) { this.nome = nome; this.voto = voto; } /* Restituisce il nome dello studente. */ public String getNome() { return nome; } /* Restituisce il voto ottenuto dallo studente. */ public double getVoto() { return voto; } }


Il problema degli studenti . . . final int NUMERO_STUDENTI = 20; // numero degli studenti Valutazione[] vs; // valutazioni degli studenti String nome; // nome di uno studente double voto; // votazione ottenuta da uno studente int i; // indice per la scansione di vs double sommaVoti; // somma dei voti double soglia; // soglia per la promozione /* crea l'array per le valutazioni degli studenti */ vs = new Valutazione[NUMERO_STUDENTI]; /* leggi nomi e votazioni dei cinque studenti */ ... stampa un messaggio ... for (i=0; i<NUMERO_STUDENTI; i++) { /* leggi nome e votazione dell'i-esimo studente */ nome = Lettore.in.leggiString(); voto = Lettore.in.leggiDouble(); /* crea la valutazione per l'i-esimo studente */ vs[i] = new Valutazione(nome,voto); }


. . . Il problema degli studenti

/* calcola la soglia per la promozione */ sommaVoti = 0; for (i=0; i<NUMERO_STUDENTI; i++) sommaVoti += vs[i].getVoto(); soglia = (2./3.) * (sommaVoti/NUMERO_STUDENTI); /* stampa l'elenco degli studenti da promuovere */ ... stampa un messaggio ... for (i=0; i<NUMERO_STUDENTI; i++) { /* verifica se l'i-esimo studente è stato promosso */ if (vs[i].getVoto() >= soglia) System.out.println(vs[i].getNome() + " " + vs[i].getVoto()); }


Esercizi q Scrivere un metodo che, dato un numero

naturale N, crea e restituisce un array di N oggetti Rettangolo creati in modo casuale

q Scrivere un metodo che, ricevendo come parametro un array di oggetti Rettangolo, calcola e restituisce il rettangolo di area massima

q Scrivere un metodo che, ricevendo come parametro un array di oggetti Rettangolo, calcola e restituisce la coppia di rettangoli la cui intersezione ha area massima


Esercizi q Data la classe Libro per rappresentare oggetti

libro con il nome dell’autore, il titolo e il numero di pagine e con i relativi metodi d’istanza §  scrivere un metodo che, ricevendo come parametro

un array di oggetti Libro, calcola e restituisce un array di oggetti Libro dello stesso autore

§  scrivere un metodo che, ricevendo come parametro un array di oggetti Libro, calcola e restituisce l’oggetto Libro con il massimo numero di pagine


Esercizi q Data la classe Auto per rappresentare oggetti

automobile con il nome della marca, il nome del modello, la targa e l’anno di immatricolazione e con i relativi metodi d’istanza §  scrivere un metodo che, ricevendo come parametro

un array di oggetti Auto, calcola e restituisce un array di oggetti Auto della stessa marca e dello stesso modello

§  scrivere un metodo che, ricevendo come parametro un array di oggetti Auto, calcola e restituisce l’oggetto Auto più vecchia


Ricerca di un elemento in un array

Descrizione del problema

q dato un array a di elementi di tipo T e un valore chiave di tipo T

q verificare se l’array a contiene un elemento uguale a chiave §  se a contiene almeno un elemento uguale a chiave,

allora deve essere calcolato e restituito l’indice (ovvero, la posizione) di uno degli elementi di a tra quelli uguali a chiave

§  altrimenti, deve essere restituito il valore -1


Il problema della ricerca in un array Nell’esecuzione di una operazione di ricerca in un array

sono possibili diverse situazioni q  se il valore chiave è uguale a 16, l’array a contiene un solo elemento

uguale a chiave §  in questo caso va restituito l’indice 6

q  se chiave è uguale a 6, l’array a non contiene nessun elemento uguale a chiave §  in questo caso va restituito il valore –1

q  se chiave è uguale a 2, l’array a contiene più di un elemento uguale a chiave §  può essere restituito indifferentemente l’indice 5 oppure 7

5 4 12 9 0 1 2 3

0 2 16 2 4 5 6 7

a


Spazio di ricerca

q Nella ricerca di una chiave in un array, in ogni momento del processo di ricerca, gli elementi dell’array sono partizionati in due insiemi: §  un insieme è composto dagli elementi che sono già

stati esaminati §  l’altro insieme è composto dagli elementi ancora

da esaminare

q Per spazio di ricerca si intende la porzione dell’array che è candidata a contenere la chiave della ricerca


Spazio di ricerca Lo spazio di ricerca varia in modo dinamico durante

l’esecuzione dell’algoritmo di ricerca

q  inizialmente lo spazio di ricerca contiene tutti gli elementi dell’array

q  la chiave viene confrontata solo con elementi dello spazio di ricerca

q ogni confronto tra la chiave e un elemento dello spazio di ricerca può §  trovare l’elemento e terminare la ricerca, oppure §  ridurre lo spazio di ricerca

Solitamente lo spazio di ricerca è una porzione contigua dell’array, delimitata da un indice o da una coppia di

indici


Spazio di ricerca nella ricerca sequenziale Nella ricerca sequenziale lo spazio di ricerca si riduce sempre di una

componente finché non viene trovato l’elemento.

34 0 9 2 7 22 12 16 5 2

7

34 0 9 7 2 22 12 16 5 2

7

34 0 9 7 2 22 12 16 5 2

7

34 0 9 7 2 22 12 16 5 2

7


Ricerca sequenziale: algoritmo q  Input: a: array con elementi di tipo T,

chiave: elemento di tipo T q  Output: indice: intero

indice della componente dell’array in cui si trova l’elemento cercato (se esiste),

-1 se non esiste q  Algoritmo

•  Gli elementi di a vengono analizzati, in sequenza, confrontandoli con l’elemento chiave da cercare, finché non viene trovato un elemento uguale a chiave

•  Se sono stati esaminati tutti gli elementi di a e non è stato trovato nessun elemento uguale a chiave la ricerca non ha avuto successo

La ricerca è sequenziale, nel senso che gli elementi dell’array

vengono scanditi in sequenza, uno dopo l’altro


Ricerca sequenziale: codifica /* Verifica se l’array a contiene un elemento uguale a * chiave, e restituisce la posizione della prima * occorrenza di chiave in a, oppure -1. */ public static int ricercaSequenziale(int[] a, int chiave){ // pre: a!=null int indice; // posizione di chiave in a int i; // indice per la scansione di a boolean trovato; // vero se l’el. e’ stato trovato

/* scandisce gli elementi di a, alla ricerca della * prima occorrenza di chiave in a */ indice = -1; trovato = false; i = 0; while (i < a.length && !trovato){

if (a[i] == chiave) { indice = i; trovato = true;} i++; }

return indice; }


Ricerca sequenziale: analisi dei costi

Ipotesi: l’array ha n elementi q Caso peggiore:

§  L’elemento non esiste nella sequenza §  Devo confrontare chiave con tutti gli elementi dell’array §  n confronti

q Caso migliore: §  L’elemento viene trovato al primo confronto §  1 confronto

q  In generale §  L’elemento esiste e si trova in posizione p < n §  p+1 confronti


Ricerca in un array ordinato

q Consideriamo il problema della ricerca in un array ordinato §  in particolare, ordinato in modo non decrescente

per i = 0..a.length-1, a[i] <= a[i+1]

0 1 3 4 0 1 2 3

7 9 12 16 4 5 6 7

22 8

34 9


Ricerca binaria q  Inizialmente lo spazio di ricerca è composto da tutti gli

elementi dell’array q Finché non è stato trovato un elemento dell’array

uguale alla chiave (e comunque lo spazio di ricerca è non vuoto) §  confronta la chiave con l’elemento centrale dello spazio di

ricerca §  se la chiave è uguale all’elemento centrale dello spazio di

ricerca, allora la ricerca termina con esito positivo §  se invece la chiave è maggiore dell’elemento centrale dello

spazio di ricerca, rimuovi dallo spazio di ricerca l’elemento centrale e tutti quelli alla sua sinistra

§  se invece la chiave è minore dell’elemento centrale dello spazio di ricerca, rimuovi dallo spazio di ricerca l’elemento centrale e tutti quelli alla sua destra


Ricerca binaria – successo

0 1 3 4 7 9 12 16 22 34

s=0 c=5 d=10

7

0 1 3 4 7 9 12 16 22 34

s=0 d=5 c=2

7

0 1 3 4 7 9 12 16 22 34

s=3 d=5 c=4

7


Ricerca binaria – fallimento

0 1 3 4 7 9 12 16 22 34

s=0 c=5 d=10

18

0 1 3 4 7 9 12 16 22 34

s=6 d=10 c=8

0 1 3 4 7 9 12 16 22 34

s=6 d=8 c=7

18

18

0 1 3 4 7 9 12 16 22 34

s=d=8


Spazio di ricerca nella ricerca binaria Nella ricerca binaria lo spazio di ricerca è formato da

insieme di elementi contigui di a, delimitato mediante una coppia di indici, sinistra e destra

q sinistra è l’indice del primo elemento dello spazio di ricerca (ovvero, quello più a sinistra)

q destra è l’indice del primo elemento oltre lo spazio di ricerca §  lo spazio di ricerca è perciò composto dagli elementi di indice

tra sinistra (incluso) e destra (escluso) q  l’algoritmo usa anche una variabile centro per indicare

l’elemento centrale dello spazio di ricerca §  ad ogni iterazione, centro viene scelto pari a (sinistra+destra)/2 §  N.B.: ( / denota la divisione tra interi)


Ricerca binaria: codifica /* Ricerca chiave nell'array a ordinato in modo * non descrescente, restituendo l'indice di un * elemento di a uguale a chiave (oppure -1). */ public static int ricercaBinaria(int[] a, int chiave) { // pre: a!=null && a è ordinato in modo non decrescente int posizione; // posizione di un elemento di a // uguale a chiave, se esiste int sinistra; // indice del primo elemento dello // spazio di ricerca int destra; // indice del primo elemento oltre // lo spazio di ricerca int centro; // indice dell'elemento centrale // dello spazio di ricerca boolean trovato; // vero se l’elemento viene trovato


Ricerca binaria: codifica /* inizialmente lo spazio di ricerca comprende * tutti gli elementi di a */ sinistra = 0;

destra = a.length; trovato = false;

/* cerca l'indice di un elemento di a uguale * a chiave, se esiste, mediante la ricerca binaria */ posizione = -1; while (sinistra<destra && !trovato) { centro = (sinistra+destra)/2; if (a[centro]==chiave){ // trovato trovato = true;

posizione = centro; } else if (a[centro]>chiave) // continua a sinistra destra = centro; else // continua a destra sinistra = centro+1; } return posizione; }


Analisi dei costi della ricerca binaria

Confronto spazio di ricerca 1° …………………… n 2° …………………… n / 2 3° …………………… n / 22

…. …. h+1-esimo ………... n / 2h = 1

Quanti confronti? h+1, ma h = log2 n, quindi log2 n + 1 confronti

0 1 3 4 7 9 12 16

Ipotesi: n è una potenza di due n = 2h

Ad ogni iterazione lo spazio di ricerca si dimezza


Esempio

0 2 3 4 7 9 12 16

Cerchiamo il valore 1

1

0 2 3 4 7 9 12 16

1

0 2 3 4 7 9 12 16

1

0 2 3 4 7 9 12 16

1

1° confronto

2° confronto

3° confronto

4° confronto


Esercizi

q Scrivere un metodo che, dati due array di interi, non necessariamente della stessa dimensione, ciascuno dei quali è ordinato in modo crescente, calcola il numero di elementi comuni ai due array

q Discutere il costo dell’algoritmo implementato, nel caso peggiore

2 7 11 21 48 89 A

7 11 15 21 42 45 B


Esercizi

q Descrivere l’applicazione dell’algoritmo di ricerca binaria con riferimento al seguente array

§  usando come chiave i valori 0, -5, 22 e 44 §  descrivere, in particolare, l’evoluzione dello spazio

di ricerca q Scrivere un metodo, basato sulla ricerca

binaria, che calcola la posizione del primo elemento di un array ordinato uguale alla chiave della ricerca

0 1 3 4 0 1 2 3

7 9 12 16 4 5 6 7

22 8

34 9


Esercizio

q Scrivere un metodo int[ ] inserisci(int[ ] a, int v), in cui a è un array ordinato in modo non decrescente, che crea e restituisce un nuovo array che contiene l’elemento v insieme a tutti gli elementi di a, ed è ancora ordinato in modo non descrescente §  ad esempio, inserisci(new int[ ] { 3, 5, 6, 8 }, 4) deve

restituire l’array { 3, 4, 5, 6, 8 }


Fusione di sequenze ordinate q La fusione di due sequenze ordinate è una

operazione che §  date due sequenze a e b ordinate in modo non

decrescente §  costruisce una nuova sequenza s che contiene tutti

gli elementi di a e b - la cui lunghezza è quindi uguale alla somma delle lunghezze di a e b - ed è ordinata in modo non decrescente

5 12 26 34

6 8 21

a

b

5 6 8 12 21 s 26 34


Strategia di fusione

q Assegno gli elementi di s — uno alla volta, in sequenza §  individuo la posizione di s in cui inserire il prossimo

elemento di a o di b •  l’indice iniziale di s vale 0

§  il prossimo elemento (di a o di b) viene scelto tra l’elemento più piccolo di a e quello più piccolo di b tra quelli che non sono ancora stati inseriti in s


Algoritmo di fusione

q L’algoritmo per la fusione di array ordinati gestisce tre indici §  l’indice ia del più piccolo elemento di a tra quelli che

non sono ancora stati inseriti in s §  l’indice ib del più piccolo elemento di b tra quelli che

non sono ancora stati inseriti in s §  l’indice is del prossimo elemento da inserire in s

•  inizialmente valgono tutti 0

§  in modo iterativo, il prossimo elemento da inserire in s[is] viene scelto tra a[ia] e b[ib]

•  attenzione all’incremento degli indici


Indici nella fusione di array

5 12 26 34

6 8 21

a

b

5 6 8 s

ia=1

ib=2

is=3

5 12 26 34

6 8 21

a

b

5 6 8 12 s

ia=2

ib=2

is=4

12


Indici nella fusione di array

q A un certo punto, tutti gli elementi di uno dei due array saranno stati inseriti in s

§  da questo momento in poi, l’algoritmo procede diversamente con la copia degli elementi residui dell’altro array

5 12 26 34

6 8 21

a

b

5 6 8 12 21 s

ia=2

ib=3

is=5


Implementazione della fusione . . . /* Fonde gli array a e b ordinati in modo * non decrescente in un nuovo array ordinato. */ public static int[] fusione(int[] a, int[] b) { // pre: a!=null && b!=null && // a e b ordinati in modo non decrescente int[] s; // risultato della fusione di a e b int ia, ib, is; // indici per a, b e s /* inizializzazioni */ s = new int[a.length+b.length]; ia = 0; ib = 0; is = 0; . . . segue . . .


. . . Implementazione della fusione . . . . . . segue . . . /* prima fase della fusione: inserisci da a e b */ while (ia<a.length && ib<b.length) { /* inserisci in s il più piccolo tra a[ia] e b[ib] */ if (a[ia]<b[ib]) { s[is] = a[ia]; ia++; } else { s[is] = b[ib]; ib++; } is++; } /* ora ia==a.length || ib==b.length */ . . . segue . . .


. . . Implementazione della fusione . . . segue . . . /* seconda fase della fusione: inserisci da a o b */ if (ib==b.length) /* inserisci da a: */ /*l'indice ib non serve piu': lo riutilizzo nel ciclo */ for (ib=ia; ib<a.length; ib++){ s[is] = a[ib]; is++;} else

/* inserisci da b */ /*l'indice ia non serve piu': lo riutilizzo nel ciclo */ for (ia=ib; ia<b.length; ia++){ s[is] = b[ia]; is++;} /* ora la fusione è stata completata */ return s; }


Esercizio

q Affrontare nuovamente il seguente problema, ispirandosi all’algoritmo di fusione §  calcola il numero di elementi comuni a due array

ordinati in modo crescente

2 7 11 21 48 89 A

7 11 15 21 42 45 B


Esercizio

q Implementare la fusione con rimozione di duplicati §  ciascuna delle sequenze iniziali non contiene

duplicati

5 12 26 34

5 8 26

a

b

5 8 12 26 34 s


Riferimenti al libro di testo q Per lo studio di questi argomenti si fa

riferimento al libro di testo, e in particolare ai paragrafi dal 19.6 alla fine del capitolo 19

Corso di Laurea Ingegneria Informatica Fondamenti …...java/fondinf/ Array e Oggetti 1 Corso di...

Documents

Transcript of Corso di Laurea Ingegneria Informatica Fondamenti …...java/fondinf/ Array e Oggetti 1 Corso di...