mitnik

User info:

Registered: Jun 2002
Posts: 235 (0.03 al dì)
Location:
Corso:
Anno:
Time Online: 3 Days, 4:25:25 [...]
Status: Offline

Post actions:

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.

aghito

User info:

Registered: Jun 2003
Posts: 71 (0.01 al dì)
Location: milano
Corso: Informatica
Anno: 3
Time Online: 20:29:57 [...]
Status: Offline

Post actions:

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

aghito

User info:

Registered: Jun 2003
Posts: 71 (0.01 al dì)
Location: milano
Corso: Informatica
Anno: 3
Time Online: 20:29:57 [...]
Status: Offline

Post actions:

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

ghily

rozzettino

User info:

Registered: Jul 2003
Posts: 718 (0.09 al dì)
Location: Settimo
Corso: Informatica spec
Anno: 2
Time Online: 13 Days, 1:05:36 [...]
Status: Offline

Post actions:

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.

Paolo74GRS

.primate.

User info:

Registered: Mar 2003
Posts: 71 (0.01 al dì)
Location: Bergamo
Corso: Informatica
Anno: > 3
Time Online: 2 Days, 11:55:02: [...]
Status: Offline

Post actions:

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?

Eruyomë

Duca di Elchingen

User info:

Registered: Feb 2003
Posts: 147 (0.02 al dì)
Location:
Corso: Informatica
Anno: II^ Magistrale
Time Online: 3 Days, 1:27:46 [...]
Status: Offline

Post actions:

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...

Tosh

User info:

Registered: Nov 2003
Posts: 94 (0.01 al dì)
Location: Bergamo
Corso: Informatica
Anno: 2° Specialistica
Time Online: 2 Days, 1:31:23 [...]
Status: Offline

Post actions:

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

LazerPhEa

Vendo Steinberger GM7TA

User info:

Registered: Jul 2002
Posts: 4400 (0.51 al dì)
Location: S. Donato Beach
Corso: TICo
Anno: Finito tutto
Time Online: 83 Days, 22:35:22 [...]
Status: Offline

Post actions:

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

Se vai qui trovi tutto quello che ti serve, compresi esempi di codice C!
IMO comunque non serve un hash ad indirizzamento aperto; gestisciti le collisioni con le liste concatenate e sei a posto!
Io nel mio progetto ho fatto così ed è andato tutto liscio...

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

Paolo74GRS

.primate.

User info:

Registered: Mar 2003
Posts: 71 (0.01 al dì)
Location: Bergamo
Corso: Informatica
Anno: > 3
Time Online: 2 Days, 11:55:02: [...]
Status: Offline

Post actions:

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!!!

marchinkus

User info:

Registered: May 2003
Posts: 33 (0.00 al dì)
Location: cernusco sul naviglio
Corso: informatica
Anno: 2
Time Online: 2 Days, 7:53:49 [...]
Status: Offline

Post actions:

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?????

attila79

User info:

Registered: Jun 2003
Posts: 49 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 23:55:22 [...]
Status: Offline

Post actions:

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

Skilotto83

..Energia positiva...

User info:

Registered: Jun 2003
Posts: 1608 (0.19 al dì)
Location: Arconate
Corso: Informatica
Anno: LAUREATO!!!
Time Online: 15 Days, 6:32:44 [...]
Status: Offline

Post actions:

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

maynard80

.novellino.

User info:

Registered: Jul 2007
Posts: 3 (0.00 al dì)
Location: Milano (e non interland, tendo a precisare)
Corso: informatica
Anno: SESTO
Time Online: 12 Days, 14:28:38 [...]
Status: Offline

Post actions:

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 !

marchinkus

User info:

Registered: May 2003
Posts: 33 (0.00 al dì)
Location: cernusco sul naviglio
Corso: informatica
Anno: 2
Time Online: 2 Days, 7:53:49 [...]
Status: Offline

Post actions:

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?????

torak

Renaulto muori

User info:

Registered: Dec 2002
Posts: 440 (0.05 al dì)
Location: Bollate
Corso: Informatica laurea triennale
Anno: 3
Time Online: 6 Days, 2:35:19 [...]
Status: Offline

Post actions:

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.