.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- [ALGORITMI]Progetto Zoom (http://www.dsy.it/forum/showthread.php?threadid=13146)

secondo me la soluzione più semplice consiste in una lista che contiene le 1-celle, questo però complica un po il resto delle operazioni nel senso che si devono fare milti calcoli e scorrere la lista parecchie volte per funzioni tipo area. Si può usare però una struttura di supporto che memorizza le 1-celle contenute in un blocco. Bho che dite?

Si skorpius penso che la prima opeazione sia la crea.

si prima cera poi inserisci un po' di cose e alla fine f

io direi che si memorizzano solo le celle occupate cioè inserite.
mi dicevano di usare un albero di ricerca binario per memorizzare tali celle e poi delle liste per mantenere di ogni cella le celle occupate adiacenti

__________________
alessandro colombini

la tabella di hash sarà anche la soluzione da guru ma io non lo sono e guardando sul libro a me sembra molto difficile da fare. dato che il 18 va più che bene mi sa che non la userò...
ma degli alberi cosa ne dite..potrebbe essere una alternativa?

__________________
alessandro colombini

Originally posted by mitnik
secondo me la soluzione più semplice consiste in una lista che contiene le 1-celle, questo però complica un po il resto delle operazioni nel senso che si devono fare milti calcoli e scorrere la lista parecchie volte per funzioni tipo area. Si può usare però una struttura di supporto che memorizza le 1-celle contenute in un blocco. Bho che dite?

Si skorpius penso che la prima opeazione sia la crea.

Mi ci metto anch'io..
Pensare il piano delle 1-celle inserite come liste di adiacenza e servirsi poi di un albero di supporto per la parte di ricerca??

Potrebbe andare no?

ma per lista di adiacenza intendete una lista di liste? Cioé, una lista per le ascisse che contiene liste con le ordinate?

__________________
Io sono la fata verde. Sono la rovina e il rimpianto, la vergogna e il disonore. Io sono la morte, io sono l'assenzio...

Chi ha proposto la tabella di hash potrebbe illustrare un po' come applicherebbe la soluzione al problema?

Originally posted by Tosh
Chi ha proposto la tabella di hash potrebbe illustrare un po' come applicherebbe la soluzione al problema?

__________________
Questo è il giardino
Dove il principe muore
Nessun sentiero
Nessun destriero
Soltanto un nome... Eterno...

Partiamo dall'idea di inserimento dei vari punti (X, Y)..
La prima ipotesi, secondo me, e' di utilizzare delle liste di adiacenza.. Ma a quel punto mi sorge un dubbio: e' possibile utilizzare una rappresentazione con liste di adiacenza se il mio grafo puo' essere non connesso??
Potrei avere alcune 1-celle inserite che rappresentano una struttura non connessa all'intero grafo..
Vero? In pratica una foresta..
Ditemi se ci sono oppure sto andando fuori strada!!!

Ragazzi, aiutatemi, la formulina per sapere quando una k-cella è piena, è chiara.
Il problema è:supponendo di avere inserito 5 1-cella in posizioni disparate sul piano, come pensate di fare per controllare se esiste qualche k-cella piena?????

Una tabella hash ha le dimensioni fissate, cosa succede se tutta la tabella è occupata da elementi? Come si fa ad aumentare le dimensioni se e possibile? Mi spiego meglio, nel caso voglia utilizzare la tabella hash per contenere le 1-celle se arrivo ad un punto in cui la tabella e piena, la posso allargare ? se si come?
grasias per l'eventuale risposta

Originally posted by marchinkus
Ragazzi, aiutatemi, la formulina per sapere quando una k-cella è piena, è chiara.
Il problema è:supponendo di avere inserito 5 1-cella in posizioni disparate sul piano, come pensate di fare per controllare se esiste qualche k-cella piena?????

__________________
"Why, Sir, you find no man at all intellectual who is willing to leave London.
No, Sir, when a man is tired of London, he is tired of life; for there is in London all that life can afford."
(DR SAMUEL JOHNSON 1777)

MSN andrea.poretti(at)hotmail.it

ma non si puòridurre il piano alle celle occupate? nel senso che semplicemente le celle libere non ci sono, quindi il mio pisno "infinito" in realtà non è altro che una lista delle celle occupate ordinate secondo le loro x,y.
In questo modo una cella è occupata se esiste nella lista, libera altrimenti, le celle sono adiacenti se le loro x o y sono consecutive ecc..
Forse sto rasentando l'idiozia, ma magari semplicemente potrebbe funzionare, no?

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

se non ho capito male, guardando la figura 1, creando un piano K , creo automaticamente una infinità di celle predefinite, ogni 2 posizioni, ogni 3 posizioni, ogni k posizioni cominciando dal p.to 0,0; quando si chiede di eliminare una k-cella in teoria le coordinate passate alla funzione dovrebbero corrispondere ad una posizione predefinita:esempio se ci sono k-celle di lato 3, le coordinate passate alla funzione elimina dovrebbero essere 0,0 oppure 3,0 oppure 3,3 .....3,6 che dite stò impazzendo?????

Quello che avevo proposto io è l'uso di una tabella hash con concatenazione(la normale tabella di hash) non una tabella ad indirizzamento aperto. Sul libro di algoritmi è al capitolo 12.2.
Chiaramente dovete usare una prefunzione, che si trova negli appunti di torelli, che trasforma (x,y) in k.
Questo k lo date in pasto ad una funzione di hash ben fatta(sempre sul libro spiega dei metodi molto buoni per costruirla) in modo da minimizzare le collisioni che bisogna prevedere di gestire con liste.
A questo punto, una volta costruita l'algoritmo per la tabella di hash, bisogna andare a vedere il capitolo 18.4 del libro, che parla di come gestire dinamicamente la dimensione delle strutture dati in modo da adattare le dimensioni all'effettivo utilizzo. E' una parte che viene spiegata poco, ma è il modo migliore per gestire la cosa. Alternativamente si può sempre decidere di fare una dimensione molto grande della tabella di hash, così da permettere di inserire molti elementi, però questo è un errore, perchè benchè funzioni per gli esempi di prova fa delle assunzioni sulle dimensioni dell'input. In più avere 10 mega di memoria occupata quando in realtà memorizzate 3 cagate non mi sembra il massimo, quindi se riuscite a realizzare una tabella di hash e avete tempo, guardatevi pure quella cosa... secondo me lo ammazzate fiorentini.