.dsy:it. - [Algoritmi - Torelli] Appello Luglio

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)
-- [Algoritmi - Torelli] Appello Luglio (http://www.dsy.it/forum/showthread.php?threadid=11694)

Posted by mitnik on 02-07-2004 09:34:

Una domanda.

Supponiamo di avere una configurazione tale per cui un invitato ha 4 insiemi di tavoli adeguati e tutti e quattro con la stessa distanza d(S), quale insieme considero per il calcolo della pozizione ottimale dell'invitato? (è come nell'esempio del prof)

Io direi di considerare l'insieme con il tavolo inserito per prima, voi che dite?

Posted by storm on 02-07-2004 12:29:

Che roba.....ieri l'ho letto e mi è venuto il mal di testa !!...Caz è peggio dell'altra volta ! Mi piace solo il titolo.. :asd:

Posted by dirkpitt on 02-07-2004 13:45:

Originally posted by mitnik
Supponiamo di avere una configurazione tale per cui un invitato ha 4 insiemi di tavoli adeguati e tutti e quattro con la stessa distanza d(S), quale insieme considero per il calcolo della pozizione ottimale dell'invitato? (è come nell'esempio del prof)

Io direi di considerare l'insieme con il tavolo inserito per prima, voi che dite?

Suppongo di sì. Comunque penso che adesso il problema maggiore sia capire quale struttura dati utilizzare per implementare il tutto

__________________
Esistono 10 tipi di persone al mondo: quelli che conoscono il codice binario e quelli che non lo conoscono...

Posted by mitnik on 02-07-2004 14:00:

Si ma anche il controllo a spirale non è banale.
Per la struttura dati io penso di utilizzare delle liste; una per i tavoli, una per gli invitati messi in base all'ordine di arrivo. Ora vedrò ....

Posted by giuze80 on 02-07-2004 16:13:

varie

Originally posted by mitnik
Si ma anche il controllo a spirale non è banale.
Per la struttura dati io penso di utilizzare delle liste; una per i tavoli, una per gli invitati messi in base all'ordine di arrivo. Ora vedrò ....

verissimo! la funzione che restituisce le coordinate dell'i-esimo step della visita a spirale non e' affatto banale, sto partendo da li' perche' credo che potrebbe essere uno dei nodi 'ammazza efficienza' del listato.....
per il resto, sono daccordo nell'implementare con una lista l'insieme degli invitati (che vanno aggiornati e si muovono secondo una logica FIFO), non altrettanto per i tavoli: non credo fosse indicato come significativo in nessun punto delle specifiche l'ordine di inserimento del tavolo....boh! iniziamo con la spirale.....

.....che belli che erano gli specchi!!!!!

Posted by dirkpitt on 03-07-2004 13:51:

Originally posted by mitnik
Per la struttura dati io penso di utilizzare delle liste; una per i tavoli, una per gli invitati messi in base all'ordine di arrivo. Ora vedrò ....

Niente RB-alberi?

Nonostante l'inserimento in una lista abbia un tempo di esecuzione minore rispetto agli RB-alberi (O(1) rispetto a O(lg n)), la ricerca (che dovrà essere eseguita abbastanza spesso) ha un tempo di esecuzione di TetaGrande(n) nelle liste e di O(lg n) negli RB-alberi (idem per la cancellazione).

Non ho però idea di come (e se) implementare le celle...

__________________
Esistono 10 tipi di persone al mondo: quelli che conoscono il codice binario e quelli che non lo conoscono...

Posted by dirkpitt on 03-07-2004 14:38:

Re: varie

Originally posted by giuze80
verissimo! la funzione che restituisce le coordinate dell'i-esimo step della visita a spirale non e' affatto banale, sto partendo da li' perche' credo che potrebbe essere uno dei nodi 'ammazza efficienza' del listato.....

Certo, ma se prima non sai quale struttura dati utilizzare per le celle, potrebbe essere difficoltoso ideare un algoritmo per la visita a spirale da applicare su di esso. O sbaglio?

__________________
Esistono 10 tipi di persone al mondo: quelli che conoscono il codice binario e quelli che non lo conoscono...

Posted by dirkpitt on 03-07-2004 15:41:

Proposta

Ma ogni singolo invitato, deve avere:
- nome : stringa
- posizione : coppia di valori (a,b) interi
- cibi : lista

Ma se ogni invitato ha una lista di cibi, l'insieme degli invitati diventa una lista (o un RB-albero) di invitati a loro volta contenenti una lista. Non è un po' pesante come cosa?

Inoltre: qualcuno conosce il tempo di elaborazione per ricerca, inserimento ed eliminazione in liste ordinate?

__________________
Esistono 10 tipi di persone al mondo: quelli che conoscono il codice binario e quelli che non lo conoscono...

Posted by sirio on 04-07-2004 16:32:

Re: Proposta

Originally posted by dirkpitt
Ma ogni singolo invitato, deve avere:
- nome : stringa
- posizione : coppia di valori (a,b) interi
- cibi : lista

Ma se ogni invitato ha una lista di cibi, l'insieme degli invitati diventa una lista (o un RB-albero) di invitati a loro volta contenenti una lista. Non è un po' pesante come cosa?

Inoltre: qualcuno conosce il tempo di elaborazione per ricerca, inserimento ed eliminazione in liste ordinate?

Se la lista è ordinata nel caso peggiore cioè quando l'elemento che si sta cercando è nell'ultima posizione il tempo diventa n a cui aggiungi il tempo di inserimento o cancellazione che è costante, per cui alla fine si ha O(n)O(1)=O(n)
:-o

Posted by giuze80 on 05-07-2004 07:23:

Re: Re: varie

Originally posted by dirkpitt
Certo, ma se prima non sai quale struttura dati utilizzare per le celle, potrebbe essere difficoltoso ideare un algoritmo per la visita a spirale da applicare su di esso. O sbaglio?

beh, si', ma credo che non usero' nessuna struttura per la cella!!! o meglio, se noti, operativamente cella e punto sono omogenei (due coordinate, stop), quindi possono essere gestite allo stesso modo; se sai che il commensale <i>i</i> sta nel punto (o cella

di coordinate (x,y) la tua ricerca a spirale puo partire considerando incrementi unitari, senza bisogno di fare riferimenti ad altre strutture. no?
Inoltre non capisco l'esigenza di ordinare gli invitati per cibi di preferenza: l'unico ordinamento significativo per l'invitato e' quello di inserimento. Per i tavoli, riparliamone

Posted by mitnik on 05-07-2004 14:41:

Idee sulla spirale?

Io ci sto ragionando un po e mi sembra che possa venire una cosa molto dispendiosa in termini di tempo, perchè se lo spazio è indefinito, prima o poi il tavolo sarà inseribile quindi la struttura dati che contiene i tavoli continuerà a crescere e così anche il tempo di verifica. Certo che nel nostro utilizzo non si inseriscono molti tavoli però non si sa mai che nei test del prof ne vengano inseriti parecchi.

Bho

Posted by storm on 05-07-2004 14:50:

... non ho proprio idea di come fare la visita...sono ferma da 2 ore già...che palle sto progetto ! :cry:

Posted by yeffa on 05-07-2004 14:56:

visita a spirale

qualcuno ha idee per la visita a spirale?
se c'è un gruppo di lavoro in laboratorio mi unisco subito
in modo da mettere assieme le idee.

ciao

Posted by giuze80 on 05-07-2004 15:07:

boh! io mi sto facendo degli schemini, cerco delle regolarita', lo sto approcciando come un quesito della settimana enigmistica..... prima o poi emergera' qualcosa....

Posted by sirio on 06-07-2004 13:23:

Da quello che leggo sul forum mi sembra che quasi tutti hanno già capito quale sia la struttura dati più efficente e soprattutto come gestire la ricerca di una cella che riguarda sia la posizione dei tavoli (e di tutte le celle vicine) che quella degli invitati.

All times are GMT. The time now is 08:28.

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