Home Introduzione Programma Orario Laboratorio Nettuno Esame Diario 02-03 Materiale Challenge News Link Forum Esoneri

horizontal rule

Tema n. 3

dal 4/06/2006 al 24/06/2006, estremi inclusi

Range query bidimensionale

Scrivere un algoritmo Java che consenta di inserire, dentro una opportuna struttura di dati, punti appartenenti al piano cartesiano discretizzato, aventi dunque coordinate intere. Oltre all'operazione di inserimento punti, la struttura dati deve supportare quella di interrogazione di range: dato un range  [x1, y1] ´ [x2, y2] si desidera conoscere il numero di punti presenti nella struttura le cui coordinate (x, y) soddisfino: (x1 <= x <= x2) e (y1 <=y <= y2).

Specifiche

  1. La classe da realizzare si chiama Dizio2D. Qualora si rendessero necessarie più classi, tutte queste saranno memorizzate nel file Dizio2D.java
  2. La classe ha un costruttore che istanzia una struttura dati vuota
  3. La classe ha un metodo public boolean insert(int x, int y) che tenta di inserire il punto (x, y) nella struttura; poiché non sono ammessi punti duplicati, il tentativo di inserire un punto già presente causerà il fallimento dell'operazione. Se il metodo ha successo restituisce true, altrimenti restituisce false
  4. La classe ha un metodo public int range2D(int x1, int y1, int x2, int y2) che restituisce il numero di punti presenti nella struttura dati, le cui coordinate (x, y) soddisfano (x1 <= x) && (x <= x2) && (y1 <= y) && (y <= y2)
  5. La classe ha un metodo public static String getMatricola() che restituisce la matricola dello studente partecipante

Soluzione del docente con cui confrontarsi. File TestDizio2Da.class, contenente un possibile main per il test della soluzione elaborata. I file pubblicati sono stati revisionati alle 20:01 del 21-06-2006, a causa di vari problemi segnalati dagli studenti.

Per poter eseguire l'inserimento di molti punti può necessario aumentare la dimensione dell'heap in uso alla JVM. Questa può essere avviata con le opzioni -XmsNUMERO1 e -XmxNUMERO2, che specificano la dimensione iniziale dell'heap e quella massima ammissibile: le dimensioni di default sono 2MB e 64MB. Ad esempio java -Xms256M -Xmx512M TestDizio2Da 200000 100 lancia il test su una JVM con heap iniziale pari a 256MB, dimensione massima pari a 512MB, eseguendo l'inserimento e la verifica di 200000 chiavi random e l'esecuzione e la verifica di 100 range query random.

Si consiglia di testare la propria classe con il main qui fornito, per verificare di aver rispettato le specifiche sui metodi da implementare

invio contributi

 

horizontal rule

Bacheca di Algoritmi e Strutture Dati a.a. 2007-08 - canale A - L

forum del corso

ultima modifica: 03/04/2008 23.37
by FdA