.dsy:it. - [ALGORITMI]Progetto Zoom

Calendar

Members

Faq

Logout

.dsy:it. : Powered by vBulletin version 2.3.1

.dsy:it. > Didattica > Corsi A - F > Algoritmi e strutture dati > [ALGORITMI]Progetto Zoom

Pages (18): « First ... « 3 4 5 6 [7] 8 9 10 11 » ... Last »

Last Thread Next Thread

Author

Thread Expand all | Contract all

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:

Edit | Report | IP: Logged

Ciao a tutti, ho un dubbio/domanda da sottoporVi.
Premetto che ho scelto di implementare la struttura 1-celle tramite un albero; il mio dubbio riguarda la creazione dell'albero binario di ricerca contenente le 1-celle!
Magari sto facendomi venire il mal di testa per nulla..
Comunque, il mio problema e': quale criterio devo utilizzare per l'ordine dei nodi dell'albero??
Ordino per X, ordino per Y.. oppure per XY (..anche se non saprei come )???

Qualcuno può darmi una dritta?
ciao

21-09-2004 22:31

Click here to Send Paolo74GRS a Private Message

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:

Edit | Report | IP: Logged

21-09-2004 22:32

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:

Edit | Report | IP: Logged

Ciao a tutti, ho un dubbio/domanda da sottoporVi.
Premetto che ho utilizzato una struttura ad albero per le 1- celle;
il mio dubbio riguarda la creazione dell'albero binario di ricerca
contenente le 1-celle!
Magari sto facendomi venire il mal di testa per nulla..
Comunque, il mio problema e': quale criterio devo utilizzare per l'ordine dei nodi dell'albero??
Ordino per X, ordino per Y.. oppure per XY (..anche se non saprei come )???
Potete darmi qualche dritta?
Ciao

21-09-2004 22:42

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:

Edit | Report | IP: Logged

21-09-2004 22:44

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:

Edit | Report | IP: Logged

21-09-2004 22:44

eskimo

.illuminato.

User info:

Registered: Jul 2003
Posts: 156 (0.02 al dì)
Location: Milano
Corso: informatica
Anno: 3datroppotempoormai
Time Online: 1 Day, 22:23:46 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Ciao, io uso una struttura per mantenere la 1-celle, poi per calcolare le k-celle mi baso su di essa e mantengo una struttura con le info sulle kcelle. Il dubbio è sulla struttura che mantiene le k-celle.
Secondo voi è meglio farla come albero binario, quindi cercare le varie 1-celle componenti la kcella con una ricerca binaria su un albero (per ogni 1-cella che devo cercare per verificare se c'è ed appartiene una determinata kcella spendo log N) oppure mantenere una lista semplice, sulla quale cercherei in questo modo: ogni kcella ha una x, y di base; questo indice lo memorizzo in un puntatore (che modifico ogni volta che la mia attenzione si sposta su una nuova kcella), così so che per cercare le altre 1celle parto sempre da quel punto e non ogni volta dall'inizio della lista.

Seocondo voi quale metodo è più performante o comunque migliore???
Spero di esser stato chiaro
P. thx!!!!

22-09-2004 11:05

Click here to Send eskimo a Private Message

Dante

JUANES

User info:

Registered: Jan 2003
Posts: 188 (0.02 al dì)
Location: Legnano
Corso: Informatica
Anno: Troppi Fuori Corso...
Time Online: 1 Day, 18:39:27 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Io ho pensato così:

1) le 1celle inserite sono memorizz. in una lista in ordine di inserimento.

2) Ad ogni inserimento di 1cella verifico a quale kcella appartiene, e aggiungo ad un'altra lista di kcelle.

3) Ad ogni inserimento di kcella verifico aggiungo ad una'altra lista di kcelle-blocchi se appartiene a quel blocco, se no aggiungo ad un'altra lista di kcelle-blocco

in totale ho almeno 3 liste: 1 che memorizza semplicemente le 1celle inserite, 1 che memorizza le kcelle risultanti e almeno 1 che memorizza le kcelle di un kblocco...

area(x y): verifico che la kcella(kx ky) ci sia nella lista delle kcelle, se sì vado a cercarla nella\e lista\e dei kblocchi e faccio i conti...

secondo voi è fattibile sta cosa? la sto pensando ora...

22-09-2004 11:22

Click here to Send Dante a Private Message

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:

Edit | Report | IP: Logged

Originally posted by Dante
Io ho pensato così:

1) le 1celle inserite sono memorizz. in una lista in ordine di inserimento.

2) Ad ogni inserimento di 1cella verifico a quale kcella appartiene, e aggiungo ad un'altra lista di kcelle.

3) Ad ogni inserimento di kcella verifico aggiungo ad una'altra lista di kcelle-blocchi se appartiene a quel blocco, se no aggiungo ad un'altra lista di kcelle-blocco

in totale ho almeno 3 liste: 1 che memorizza semplicemente le 1celle inserite, 1 che memorizza le kcelle risultanti e almeno 1 che memorizza le kcelle di un kblocco...

area(x y): verifico che la kcella(kx ky) ci sia nella lista delle kcelle, se sì vado a cercarla nella\e lista\e dei kblocchi e faccio i conti...

secondo voi è fattibile sta cosa? la sto pensando ora...

Ma skusa ma nn è sufficente inserire prima tutte le 1-celle e poi calcolare le varie K celle??
Perkè una 1-cella nn per forza appartiene ad una k-cella....visto ke la K-cella esiste se è superiore il livello di riempimento....
No?
Poi ogni volta ke inserisci una 1-cella rifai la ricerka e kontrolli se è gia' in una K-cella esistente....se si' amen...altrimenti potrebbe doventare k-cella proprio kn la 1-cella inserita...e quindi prosegui...
no?

__________________
"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

22-09-2004 11:35

Click here to Send Skilotto83 a Private Message

contezer0

.amico.

User info:

Registered: Jun 2003
Posts: 38 (0.00 al dì)
Location:
Corso: informatica
Anno: molto fuori
Time Online: 5:23:08: [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Originally posted by sirio
In effetti hai ragione se usi una tab. hash a indirizzamento aperto, ciò non vale se usi la tab. con liste concatenate.

perche', se uso le liste concatenate, al momento di incrementare la dimensione della tabella, non devo usare comunque una funzione hash diversa da quella di prima?

o forse vuoi dire che non c'e' bisogno di aumentare la dimensione?

comunque...facendo due conti, e considerando che l'unica limitazione sul piano e' data dal tipo di dato intero, se ci capita un piano interamente ricoperto di celle, abbiamo un fattore di carico (2^32)/numero di posizioni nella tabella.
quindi sara' si un O(1) ma la costante nascosta da questo O mi pare abbastanza gigantesca!

oltretutto solo se la funzione hash e' molto buona.

22-09-2004 11:37

Click here to Send contezer0 a Private Message

Dante

JUANES

Post actions:

Edit | Report | IP: Logged

Originally posted by Skilotto83
Ma skusa ma nn è sufficente inserire prima tutte le 1-celle e poi calcolare le varie K celle??

Forse sì, quando chiede per la prima volta area, peso o blocchi, è allora che creo la lista di kcelle e kblocchi...

[i]Perkè una 1-cella nn per forza appartiene ad una k-cella....visto ke la K-cella esiste se è superiore il livello di riempimento....
No? [/B]

Sì, ma c'è da tenere conto che cmq il livello di riempimento può cambiare in qualsiasi momento... dentro ogni nodo della lista delle kcelle io terrei anche l'infomazione di quante 1celle ha la kcella... così la lista è riutilizzabile sempre, anche se cambi il livello di riempimento... forse l'unica che devi cambiare è la lista delle kcelle-blocchi...

[i]Poi ogni volta ke inserisci una 1-cella rifai la ricerka e kontrolli se è gia' in una K-cella esistente....se si' amen...altrimenti potrebbe doventare k-cella proprio kn la 1-cella inserita...e quindi prosegui...
no? [/B]

boh...

22-09-2004 11:47

aghito

.primate.

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:

Edit | Report | IP: Logged

facendo una lista delle 1-celle conviene farla con inserimento in coda perchè bisogna controllare che la 1 cella che inserisco non sia già nella lista..con l'inserimento in coda dato che devo controllare il campo next per vedere l'ultimo elemento controllo anche il valore di key e se è uguale a quello da inserire mi fermo...

avete del codice per liste con inserimento in coda o siti di riferimento?

__________________
alessandro colombini

22-09-2004 13:21

Click here to Send aghito a Private Message

lino

.precettore.

User info:

Registered: Jun 2003
Posts: 96 (0.01 al dì)
Location: lodi
Corso: informatica
Anno: terzo
Time Online: 2 Days, 1:25:20 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Come faccio UNA LISTA CON

22-09-2004 14:26

Click here to Send lino a Private Message

mitnik

.illuminato.

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:

Edit | Report | IP: Logged

IO sto procedendo come Dante, ho una lista con le 1-celle, poi creo una lista con le k-celle che hanno come figli le 1-celle che contengono. Per l'area devo creare un'altra lista con le k-celle che sono occupate. Il problema è sul calcolo dei blocchi, avete qualche idea?

23-09-2004 10:08

Click here to Send mitnik a Private Message

Dante

JUANES

Post actions:

Edit | Report | IP: Logged

bravo! sto scrivendo questa parte di codice.... una volta funzionante aggiungo le funzioni area, peso e blocchi... sperem....
tu sei già lì?

23-09-2004 13:10

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:

Edit | Report | IP: Logged

Originally posted by mitnik
IO sto procedendo come Dante, ho una lista con le 1-celle, poi creo una lista con le k-celle che hanno come figli le 1-celle che contengono.

Finalemtne ho dato editoria ed ora posso concentrarmi sul progetto.Il tempo è poco ma speriamo in bene.Una cosa ancora non ho capito: ma queste 1-celle sono veramente così importanti? Mi spiego meglio: quale è l'utilità di sapere che nella k-cella (k,x,y) è contenuta percisametne quella cella? Se non mi sfugg eniete nel testo non c'è nessuna funzione che ti chiede di ritornare 1-celle.L'importante è sapere QUANTE (non quali) celle sono contenute nella k-celle selezionata. Sbaglio??

Altra cosa che non mi è chiara.Nella funzione elimina (k,x,y) la cella che è da andare a trovare è la cella che ha coordinate (kx,ky) ecc. ? Oppure la 1-cella (k,y???

Grazie
Chao
Roby

23-09-2004 14:19