LSD
Mercoledi'8 maggio
2002
ESERCIZI SU INSIEMI
-
Si scriva la classe SetTheory
che contiene i seguenti metodi:
- public static Set union (Set s1, Set s2)
che restituisce l'unione degli insiemi passati per argomento.
- public static Set intersection (Set s1, Set s2)
che restituisce l'intersezione degli insiemi passati per argomento.
- public static Set difference (Set s1, Set s2)
che restituisce la differenza degli insiemi passati per argomento, cioe' gli elementi di s1 che non sono elementi di s2 .
Scrivere inoltre un semplice programma di verifica per testare i metodi.
Soluzione: SetTheory.java
-
Si scriva la classe
NextElement contentente
il metodo statico next:
import lab2.*;
public class NextElement {
public static Integer next
( int n, Set s ) {
// da completare
}
} |
Si assume che tutti gli elementi nell'insieme s siano di tipo Integer:
se ciò non è vero,
il metodo deve lanciare un'eccezione ClassCastException.
Il metodo next restituisce l'oggetto in
s
il cui valore è il più piccolo tra quelli strettamente maggiori
di n, e null se questo non esiste (cioè
se tutti gli elementi di s
hanno valore minore o uguale a n).
Per testare la classe NextElement, si compili ed esegua la classe
TestNextElement.
L'output deve essere il seguente:
Provo il metodo NextElement.next(int,Set)...
Next di 5 in { -5 0 1
2 6 7 9 10 11 45}: 6
Insieme dopo next:{ -5 0 1
2 6 7 9 10 11 45}
Next di 15 in { 6 9 11
-5}: null
Insieme dopo next: { 6 9 11
-5}
Next di 48 nell'insieme vuoto : null
invoco next({ 3 56 89
bingo!},2)
Ok: multipli ha lanciato l'eccezione java.lang.ClassCastException |
Soluzione: NextElement.java
-
Sia data la seguente interfaccia che estende Set:
import
lab2.*;
interface RetSet
extends
Set{
/* restituisce
un oggetto dell'insieme su cui
* viene invocato che sia uguale (nel senso di
* "equals") all'oggetto passato per argomento.
* Restituisce null
se non esiste un tale oggetto.
*/
Object
retrieve
(Object
o);
}
|
Si scriva una classe HashRetSet,
che eredita
da HashSet
ed implementa questa interfaccia. Si compili
la classe; per testarla si passi al prossimo esercizio.
Soluzione: HashRetSet.java
-
Si vuole realizzare una rudimentale rubrica telefonica,
in cui ad ogni nome è associato al massimo un numero. Si scriva
per prima cosa una classe chiamata Entry, avente
-
due variabili d'istanza private, nome e numTel di tipo String;
-
un costruttore Entry(String name, String tel);
-
un costruttore Entry(String name);
-
un metodo String getTel() che restituisce
il valore di numTel;
-
un metodo String getNome() che restituisce
il valore di nome;
- un metodo
public boolean equals(Object obj) tale
che entry.equals(obj) vale true solo se obj è
un'istanza della classe Entry
e i valori della variabile d'istanza
nome di obj
ed entry sono
equals
.
un metodo
public int hashCode() che sovrascrive il corrispondente metodo della classe Object
in accordo al nuovo metodo equals.
Si scriva quindi la classe principale
Rubrica
contenente solo il metodo main.
Questo metodo dichiara una variabile
rubrica di tipo RetSet (si veda l'esercizio precedente)
e le assegna un'istanza della classe HashRetSet.
Quindi chiede all'utente un certo numero di nomi e corrispondenti numeri
di telefono, crea le corrispondenti istanze di Entry e le inserisce nella rubrica. Infine chiede all'utente alcuni nomi da cercare, e ne stampa
il numero di telefono se esiste, o un messaggio opportuno altrimenti.
Soluzione: Rubrica.java
Altri Esercizi su Liste e Insiemi
[AbsSet] Si
scriva la classe AbsSet contentente il metodo statico abs:
import lab2.*;
public class AbsSet {
public static int abs ( Set
s ) {
// da completare
}
} |
Si assume che tutti gli elementi dell'insieme s
siano di tipo Integer: se ciò non è vero,
il metodo deve lanciare un'eccezione IllegalArgumentException.
Il metodo
abs deve modificare l'insieme passato come parametro
attuale, sostituendo ogni oggetto con valore negativo con un Integer
avente il corrispondente valore assoluto. Il metodo restituisce la somma
degli elementi dell'insieme
s PRIMA della modifica.
Per testare la classe AbsSet, si compili
ed esegua la classe TestAbsSet.
L'output deve essere ESATTAMENTE il seguente:
Provo il metodo AbsSet.abs(Set)...
Somma di { -45 -10 -5
-1 0 2 6 7 9 11}: -26
Insieme dopo abs:{ 0 1 2
5 6 7 9 10 11 45}
Somma di { 5 6 9 11}:
31
Insieme dopo abs: { 5 6 9
11}
Insieme vuoto. Somma: 0
Invoco abs({ 3 56 89 bingo!})
Ok: togliMultipli ha lanciato una IllegalArgumentException |
Soluzione: AbsSet.java
[SortedUnion]
Si scriva la classe
SortedUnion, contenente il metodo statico
merge:
import lab2.*;
public class SortedUnion {
public static List merge (
Queue q, Stack s) {
// da completare
}
} |
Si assuma che la coda q e la pila s
contengano solo istanze di Integer (quindi che implementano
l'interfaccia Comparable). Il metodo merge,
senza modificare né la coda q né la pila
s
passate per argomento, deve restituire una lista che contiene tutti gli
oggetti che compaiono in q o in s, senza
ripetizioni ed in ordine crescente. Il metodo deve lanciare una IllegalArgumentException
se uno dei due parametri è
null.
Suggerimento: per ottenere in modo automatico l'ordinamento
degli oggetti, si utilizzi una istanza di TreeSet
come
contenitore ausiliario.
Per testare il metodo, si esegua la classe TestSortedUnion.class.
e si corregga il programma finché l'output non sia esattamente il
seguente:
Provo il metodo ' SortedUnion.merge(Queue,Stack)'...
OK: il metodo mi sembra corretto. |
Soluzione: SortedUnion.java
[Implementazione di Set con Array]
Si scriva la classe ArraySet che implementa
l'interfaccia Set usando un array in modo naif (senza l'uso
di una funzione hash). Ad ogni istante, un segmento iniziale dell'array
(determinato dal valore di una variabile d'istanza) è occupato,
o con elementi dell'insieme o con elementi marcati per cancellazione.
Il metodo add scandisce la parte occupata
dell'array per vedere se l'elemento è già presente, ed in
caso contrario lo inserisce nella prima posizione libera dell'array.
remove
non cancella effettivamente l'elemento dall'insieme, ma lo marca come cancellato.
Gli elementi marcati vengono effettivamente eliminati (e l'array ricompattato)
quando si esegue una add ma l'array è pieno.
Se si invoca una add quando l'array è
pieno e non ci sono elementi marcati per cancellazione, allora si
raddoppia la dimensione dell'array (come in ArrayStack.java).
L'iteratore scandisce gli elementi dell'insieme nell'ordine
in cui compaiono nell'array.
Il numero ed il tipo di variabili d'istanza della classe
ArraySet
sono a discrezione dello studente. L'unico vincolo è che la classe
realizzi tutti i metodi dell'interfaccia Set secondo le indicazioni date.