Simeon

User info:

Registered: Aug 2004
Posts: 984 (0.13 al dì)
Location: Milano
Corso: Informatica
Anno: IT IS OVER!
Time Online: 14 Days, 19:29:42 [...]
Status: Offline

Post actions:

Originally posted by darkAntAreS
io ho fatto sottopercorso!!!
un consiglio: NON fare l'errore di calcolarti ogni sottopercorso da ogni punto..ragiona su come è fatto un sottopercorso e da dove deve, per forza di cose, partire per essere tale...
nel caso peggiore a me viene (nlogn)/2, ma bisogna essere proprio sfigati...e nel caso medio viene circa n/2

Mmm forse ho capito, anche quei tempi li possono essere un'indizio .

Quindi tu hai finito tutto o devi fare riduci?

tandrea85

User info:

Registered: Sep 2004
Posts: 95 (0.01 al dì)
Location:
Corso: informatica
Anno: 1
Time Online: 18:21:48 [...]
Status: Offline

Post actions:

per quelli che hanno gia fatto la struttura base.. potete dirmi se il ragionamento che ho in testa regge e come la vedete voi?

avevo in mente 2 strutture
- un albero binario per i i punti a cui vengono variati i valori tramite la funzione "valore"
- un grafo che memorizza il percorso della mappa in base alla specifica e 1 algoritmo del cammino minimo.

non riesco ancora a capire cosa associare al piano e alla mappa..

mettiamo che faccio una funzione con il prototipo Piano new_piano(int m, int n, char *nome);
cosa deve ritornarmi alla struttura piano? tutti i valori dei punti del piano è da escludere..
l'unica cosa che mi viene in mente è fagli tornare i valori dei punti presi da file e memorizzati in un array e magari la struttura che contiene le varie mappe del piano..

riguardo appunto la struttura che raggruppa tutte la mappe posso benissimo usare o una lista o un array.

e infine la mappa sarà appunto un grafo.

se qualcuno mi illumina la retta via gliene sarei grato! grazie

Last edited by tandrea85 on 18-02-2006 at 13:25

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:

Originally posted by Simeon
Mmm forse ho capito, anche quei tempi li possono essere un'indizio .

Quindi tu hai finito tutto o devi fare riduci?

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Simeon

User info:

Registered: Aug 2004
Posts: 984 (0.13 al dì)
Location: Milano
Corso: Informatica
Anno: IT IS OVER!
Time Online: 14 Days, 19:29:42 [...]
Status: Offline

Post actions:

Originally posted by maynard80
illumina anche chi non ha capito..please

Ma forse intendeva il fatto che per un percorso pi ... pj i dev'essere i>= j e quindi non devi guardarti tutti i punti... boh! Bluffavo, non lo so ancora perche sto rifinendo riduci()

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:

Originally posted by Simeon
Ma forse intendeva il fatto che per un percorso pi ... pj i dev'essere i>= j e quindi non devi guardarti tutti i punti... boh! Bluffavo, non lo so ancora perche sto rifinendo riduci()

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Simeon

User info:

Registered: Aug 2004
Posts: 984 (0.13 al dì)
Location: Milano
Corso: Informatica
Anno: IT IS OVER!
Time Online: 14 Days, 19:29:42 [...]
Status: Offline

Post actions:

Originally posted by maynard80
e mica è vero, se il punto di indice i e quello di indice j sono 2 punti adiacenti??nonostante magari nel percorso della mappa non c'è un hop che li collega..

Mi sa che hai ragione e che su sta funzione ci devo proprio ragionare, ma non oggi va...

@tandrea85

L'albero binario per i punti mi sembra ok

Per il resto... il piano non esiste.

Voglio dire, non crei una struttura per rappresentare il piano, ma fai in modo che ogni volta che hai bisogno di trovare il valore di un punto di questo piano o gli associ il valore di default (che trovi tramite la nota3) oppure gli associ un valore deciso da te (ma prima devi settarglielo tramite "valore(x,y,n)".

Per la struttura che memorizza le mappe puoi usare una lista o un albero o quel che ti pare a te...

Infine riguardo al "la mappa sarà un grafo" non ti posso dire se sia giusto o sbagliato, cioè io non ho fatto così ad esempio ma potrei aver adottato un approccio differente.

darkAntAreS

...bloup will rule you...

User info:

Registered: Jun 2004
Posts: 267 (0.03 al dì)
Location: gorgonzola(MI)
Corso: informatica
Anno: x
Time Online: 3 Days, 14:49:45 [...]
Status: Offline

Post actions:

bhe, senza sbilanciarmi troppo

considerate che, se cercate i percorsi a partire da un punto P(i) e P(i-1) è >=0, bhe, in un ciclo precedente avreste potuto controllare i percorsi da P(i-1) che sono sicuramente maggiori di quelli da P(i)...

riduci l'ho fatto, ma ci mette troppo, quindi sto ragionando per velocizzarlo un po'...e per farlo sto pensando ad un albero come appoggio (a sinistra se vai in una direzione, a destra se vai verso l'altra...)

per la struttura di memorizzazione delle mappe l'albero è ottimo, visto che, se lo si ordina sui nomi delle mappe, la ricerca è molto veloce...l'unico problema si incontra con l'eliminazione di un nodo interno, ma basta leggere gli esempi del libro che lo spiegano benissimo

__________________
"Ash nazg durbatulûk, ash nazg gimbatul, ash nazg thrakatulûk agh burzum-ishi krimpatul"

Simeon

User info:

Registered: Aug 2004
Posts: 984 (0.13 al dì)
Location: Milano
Corso: Informatica
Anno: IT IS OVER!
Time Online: 14 Days, 19:29:42 [...]
Status: Offline

Post actions:

Originally posted by darkAntAreS

riduci l'ho fatto, ma ci mette troppo, quindi sto ragionando per velocizzarlo un po'...

Ci mette troppo in che termini? A me l'esecuzione dell'input del prof e' instantanea ad occhio, ma magari ci mette che so 100ms e sono troppi (in fondo l'input del prof è piccolino).

Cosa intendi per troppo scusa?

p.s Grazie per la dritta sui percorsi

darkAntAreS

...bloup will rule you...

User info:

Registered: Jun 2004
Posts: 267 (0.03 al dì)
Location: gorgonzola(MI)
Corso: informatica
Anno: x
Time Online: 3 Days, 14:49:45 [...]
Status: Offline

Post actions:

bhe, io non mi sto confrontando coi tempi del mio processore...è ovvio che se piazzo un algoritmo come il mio attuale riduci, a meno che non metto i 2 punti a distanze immani, la differenza di tempo non è apprezzabile...più che altro sto facendo i calcoli della complessità dei tempi degli algoritmi...
quindi il discorso di velocizzare le cose si basa sull'algoritmo, non sull'implementazione...

forse ho trovato il metodo per ridurlo a m*n (con m e n intese come le differenze tra le coordinate dei punti)

__________________
"Ash nazg durbatulûk, ash nazg gimbatul, ash nazg thrakatulûk agh burzum-ishi krimpatul"

Simeon

User info:

Registered: Aug 2004
Posts: 984 (0.13 al dì)
Location: Milano
Corso: Informatica
Anno: IT IS OVER!
Time Online: 14 Days, 19:29:42 [...]
Status: Offline

Post actions:

Originally posted by darkAntAreS
bhe, io non mi sto confrontando coi tempi del mio processore...è ovvio che se piazzo un algoritmo come il mio attuale riduci, a meno che non metto i 2 punti a distanze immani, la differenza di tempo non è apprezzabile...più che altro sto facendo i calcoli della complessità dei tempi degli algoritmi...
quindi il discorso di velocizzare le cose si basa sull'algoritmo, non sull'implementazione...

forse ho trovato il metodo per ridurlo a m*n (con m e n intese come le differenze tra le coordinate dei punti)

tandrea85

User info:

Registered: Sep 2004
Posts: 95 (0.01 al dì)
Location:
Corso: informatica
Anno: 1
Time Online: 18:21:48 [...]
Status: Offline

Post actions:

domanda stupidissima e veloce:
se uso un albero binario di ricerca e come chiavi uso le coordinate x,y di un punto come faccio a discriminare le chaivi per farle andare o nel sottoalbero sinistro o quello destro?

YoMo

User info:

Registered: Oct 2004
Posts: 96 (0.01 al dì)
Location: Placentia
Corso: Info triennale
Anno: laureato
Time Online: 2 Days, 0:18:13 [...]
Status: Offline

Post actions:

Originally posted by tandrea85
domanda stupidissima e veloce:
se uso un albero binario di ricerca e come chiavi uso le coordinate x,y di un punto come faccio a discriminare le chaivi per farle andare o nel sottoalbero sinistro o quello destro?

tandrea85

User info:

Registered: Sep 2004
Posts: 95 (0.01 al dì)
Location:
Corso: informatica
Anno: 1
Time Online: 18:21:48 [...]
Status: Offline

Post actions:

Originally posted by YoMo
Io ho ordinato in base alla coordinata x ed, in caso di uguaglianza, in base alla y. Non sembrano esserci problemi, neanche cn le rotazioni (ho usato un rbtree).

Simeon

User info:

Registered: Aug 2004
Posts: 984 (0.13 al dì)
Location: Milano
Corso: Informatica
Anno: IT IS OVER!
Time Online: 14 Days, 19:29:42 [...]
Status: Offline

Post actions:

Ma se per trovare il sottopercorso migliore io scandisco l'array che contiene il percorso UNA SOLA VOLTA... è tempo lineare vero ?

Se si, e se il mio algoritmo funziona, ho trovato una soluzione in tempo lineare.

Dubito molto fortemente della seconda ipotesi però...

darkAntAreS

...bloup will rule you...

User info:

Registered: Jun 2004
Posts: 267 (0.03 al dì)
Location: gorgonzola(MI)
Corso: informatica
Anno: x
Time Online: 3 Days, 14:49:45 [...]
Status: Offline

Post actions:

se riesci si, è tempo lineare...ma non riesco a immaginarlo...bhe, se funziona sei un grande

__________________
"Ash nazg durbatulûk, ash nazg gimbatul, ash nazg thrakatulûk agh burzum-ishi krimpatul"