.dsy:it. - Progetto Colori

Pages (6): « 1 [2] 3 4 5 6 »
Show 150 posts per page

.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- Progetto Colori - Help (http://www.dsy.it/forum/showthread.php?threadid=38958)

Posted by Lallac10 on 02-09-2009 15:10:

si implemento il grafo con liste di adiacenza ma non capisco cosa mi serve un albero rb....per la ricerca?

Posted by khelidan on 02-09-2009 15:10:

Originally posted by Lallac10
no ovvio che una tabella in questo caso è inadeguata, ma io pensavo a un grafo per ogni ingresso ad esempio, con le coordinate salvate insieme al colore, un albero non ce lo vedo proprio non riesco a collegarlo con una rappresentazione iniziale e concettuale a tabella...

scusa ma il grafo come lo implementi??

__________________
Khelidan

Posted by khelidan on 02-09-2009 15:11:

Originally posted by Lallac10
si implemento il grafo con liste di adiacenza ma non capisco cosa mi serve un albero rb....per la ricerca?

puoi fare una lista di liste ma computazionalmente fa schifo,un albero rb è molto meglio,la ricerca è molto piu veloce

__________________
Khelidan

Posted by Lallac10 on 02-09-2009 15:13:

scusa ma se ho un grafo con liste di adiacenza, posso usare una visita in profondità.....non so pooi magari non ho molta dimestichezza con gli alberi rb però nn so non mi convincono....

Posted by khelidan on 02-09-2009 15:15:

Originally posted by Lallac10
scusa ma se ho un grafo con liste di adiacenza, posso usare una visita in profondità.....non so pooi magari non ho molta dimestichezza con gli alberi rb però nn so non mi convincono....

ok....ora dimmi come fai materialmente ad implementare un grafo...(cmq non preoccuparti gli stessi quesiti c'è li siamo posti uguali al tempo

)

__________________
Khelidan

Posted by Lallac10 on 02-09-2009 15:16:

una lista di nodi e per ogni nodo la sua lista di adiacenza...così non ho problemi di grandezza del grafo...

Posted by khelidan on 02-09-2009 15:18:

Originally posted by Lallac10
una lista di nodi e per ogni nodo la sua lista di adiacenza...così non ho problemi di grandezza del grafo...

va bene questa è la soluzione piu inefficente...scusa perche per rappresentare la tua prima lista quella dei nodi non puoi usare un albero?a questo punto non capisco quale sia il tuo dubbio...al posto della lista usi l'albero molto piu efficente....hai una ricerca in logn al posto di n

__________________
Khelidan

Posted by Lallac10 on 02-09-2009 15:19:

ok e gli alberi rb sono migliori di un albero di ricerca binaria?

l'albero di ricerca binaria forse è meglio
anche perchè io non ho il problema delle cancellazioni ma solo eventuali inserimenti, per cui non ci sarebbe tutto inefficiente? Poi avendo delle coordinate numeriche posso definire quale è il maggiore e quale il minore...tenendo come punto discriminante (0,0)....o mi sbaglio?

Posted by khelidan on 02-09-2009 16:36:

Originally posted by Lallac10
ok e gli alberi rb sono migliori di un albero di ricerca binaria?

l'albero di ricerca binaria forse è meglio
anche perchè io non ho il problema delle cancellazioni ma solo eventuali inserimenti, per cui non ci sarebbe tutto inefficiente? Poi avendo delle coordinate numeriche posso definire quale è il maggiore e quale il minore...tenendo come punto discriminante (0,0)....o mi sbaglio?

gli alberi red black sono un ottimizzazione degli alberi di ricerca binaria,oltre ad essere ordinati hanno un colore per nodo,o rosso o nero e mediante apposite regole(che tra l'altro Torelli mi ha chiesto all'orale) si bilanciano in modo da avere una ricerca nel caso peggiore uguale al caso medio ovvero O(logn),mentre negli alberi binari se ad esempio immetti un input già ordinato avrai un albero tutto sbilanciato a destra con una ricerca di O(n) (una lista in pratica)

la questione delle eliminazioni è un vantaggio nel senso che ad esempio rispetto al progetto che feci io ingranaggi 2 non ti devi occupare dell'aggiornamento dei puntatori quando l'albero si bilancia dopo una cancellazione(nell'inserimento non c'è bisogno di fare questo),un motivo in più per usare i red black,casomai la presenza delle cancellazione sarebbe stato un motivo per optare per i piu facili alberi binari,anche se l'aggiornamento dei puntatori è comunque una cosa fattibile,trovi codice di esempio nel mio stesso progetto in filez,ma comuqnue a voi in questo progetto non serve

__________________
Khelidan

Posted by Lallac10 on 03-09-2009 09:36:

ci ho ragionato su all'albero rb, e mi sorge una domanda: è utile sui colori? in fondo non faccio nessuna ricerca sul piano colori o meglio, faccio più ricerche sui pazienti...
Altra domanda come posso memorizzare le figure? Pensavo con una lista di coordinate delle celle per ogni paziente, e una lista default con tutte le figure base. Non vorrei che ci volesse anche qui un RB.....

Posted by bramar on 03-09-2009 14:21:

Originally posted by Lallac10
ci ho ragionato su all'albero rb, e mi sorge una domanda: è utile sui colori? in fondo non faccio nessuna ricerca sul piano colori o meglio, faccio più ricerche sui pazienti...
Altra domanda come posso memorizzare le figure? Pensavo con una lista di coordinate delle celle per ogni paziente, e una lista default con tutte le figure base. Non vorrei che ci volesse anche qui un RB.....

__________________
mcb

Posted by Lallac10 on 03-09-2009 14:26:

in effetti sono stata poco chiara!
Mi spiego meglio:
la prima parte riguarda l'uso degli alberi rb che ho deciso di usare comunque mi costano meno di una lista
la seconda parte è un dubbio sulle figure. Come le memorizzo? cioè che struttura posso usare? una per ogni paziente oppure una con le figure base e poi da li risalgo a quelle dei pazienti tramite i colori che ognuno non riconosce?

spero di essere stata più chiara ora

Posted by khelidan on 04-09-2009 12:23:

Originally posted by Lallac10
in effetti sono stata poco chiara!
Mi spiego meglio:
la prima parte riguarda l'uso degli alberi rb che ho deciso di usare comunque mi costano meno di una lista
la seconda parte è un dubbio sulle figure. Come le memorizzo? cioè che struttura posso usare? una per ogni paziente oppure una con le figure base e poi da li risalgo a quelle dei pazienti tramite i colori che ognuno non riconosce?

spero di essere stata più chiara ora

Non mi ricordo bene bene le specifiche(ogni tanto mi tocca lavorare

) ma mi pare che non si abbia necessità di salvare le figure riconosciute,le si calcola al volo e si stampa l'output!

__________________
Khelidan

Posted by ma721737 on 07-09-2009 11:27:

io sto usando un albero per i colori e mi sorge un dubbio che sulle specifiche mi sembra non chiaro, ovvero: se io tento di inserire nell'albero un nodo in una determinata posizione che è già occupata cosa si decide di fare? ci avete pensato?

__________________
If I were to be alone, silence would rock my tears.

Posted by Lallac10 on 07-09-2009 13:19:

tu stai parlando dello schema ricavato dal file? quello con tutti i colori possibili da cui trarre le figure? Nelle specifiche dice di tenere conto che l'input sia sempre coerente quindi che tu non vada a inserire una nuova cella dove già risiede una cella colorata...

tu usi un albero ordinato secondo le coordinate? e le liste di adiacenza dei colori?

All times are GMT. The time now is 16:49.

Pages (6): « 1 [2] 3 4 5 6 »
Show all 88 posts from this thread on one page