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:

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?

storm

.precettore.

User info:

Registered: Jun 2004
Posts: 97 (0.01 al dì)
Location: posto tranquillo
Corso: Informatica
Anno: 3° e oltre
Time Online: 1 Day, 8:29:42 [...]
Status: Offline

Post actions:

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

dirkpitt

User info:

Registered: Dec 2002
Posts: 210 (0.03 al dì)
Location:
Corso: Informatica
Anno: 3bis
Time Online: 2 Days, 21:12:55 [...]
Status: Offline

Post actions:

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

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:

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

giuze80

User info:

Registered: Sep 2003
Posts: 24 (0.00 al dì)
Location: Milano
Corso: Informatica
Anno: 3
Time Online: 10:06:23 [...]
Status: Offline

Post actions:

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

dirkpitt

User info:

Registered: Dec 2002
Posts: 210 (0.03 al dì)
Location:
Corso: Informatica
Anno: 3bis
Time Online: 2 Days, 21:12:55 [...]
Status: Offline

Post actions:

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

Last edited by dirkpitt on 03-07-2004 at 14:41

dirkpitt

User info:

Registered: Dec 2002
Posts: 210 (0.03 al dì)
Location:
Corso: Informatica
Anno: 3bis
Time Online: 2 Days, 21:12:55 [...]
Status: Offline

Post actions:

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

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

Last edited by dirkpitt on 03-07-2004 at 14:43

dirkpitt

User info:

Registered: Dec 2002
Posts: 210 (0.03 al dì)
Location:
Corso: Informatica
Anno: 3bis
Time Online: 2 Days, 21:12:55 [...]
Status: Offline

Post actions:

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

sirio

.illuminato.

User info:

Registered: Mar 2003
Posts: 187 (0.02 al dì)
Location: Milano
Corso: Informatica
Anno: Terzo
Time Online: 2 Days, 17:32:27 [...]
Status: Offline

Post actions:

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)

giuze80

User info:

Registered: Sep 2003
Posts: 24 (0.00 al dì)
Location: Milano
Corso: Informatica
Anno: 3
Time Online: 10:06:23 [...]
Status: Offline

Post actions:

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

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:

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

storm

.precettore.

User info:

Registered: Jun 2004
Posts: 97 (0.01 al dì)
Location: posto tranquillo
Corso: Informatica
Anno: 3° e oltre
Time Online: 1 Day, 8:29:42 [...]
Status: Offline

Post actions:

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

yeffa

User info:

Registered: Oct 2002
Posts: 22 (0.00 al dì)
Location:
Corso:
Anno:
Time Online: 6:35:07: [...]
Status: Offline

Post actions:

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

giuze80

User info:

Registered: Sep 2003
Posts: 24 (0.00 al dì)
Location: Milano
Corso: Informatica
Anno: 3
Time Online: 10:06:23 [...]
Status: Offline

Post actions:

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

sirio

.illuminato.

User info:

Registered: Mar 2003
Posts: 187 (0.02 al dì)
Location: Milano
Corso: Informatica
Anno: Terzo
Time Online: 2 Days, 17:32:27 [...]
Status: Offline

Post actions:

?

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.