.dsy:it. - [Algoritmi] Progetto "RICHIAMI"

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

Pages (33): « First ... « 15 16 17 18 [19] 20 21 22 23 » ... Last »

Last Thread Next Thread

Author

Thread Expand all | Contract all

LjL

.consigliere.

User info:

Registered: Dec 2003
Posts: 144 (0.02 al dì)
Location: Milano
Corso: Informatica
Anno: Primo
Time Online: 16:25:17 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Nell'area file potete trovare un programmino che ho scritto per generare input validi per il progetto.

Spero vi sia utile.

E, sì, adesso il mio progetto è quasi completamente funzionante e domani invece di litigare con wingzero proverò e confronterò gli input che sono stati postati qui

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

21-02-2005 01:28

Click here to Send LjL a Private Message

LjL

.consigliere.

User info:

Registered: Dec 2003
Posts: 144 (0.02 al dì)
Location: Milano
Corso: Informatica
Anno: Primo
Time Online: 16:25:17 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Re: PROVIAMO L'OUTPUT

Originally posted by mattcobain
[snip]

io ho provato a dare in input questa sequenza:

[snip]

ho provato anche a fare le prove su carta e mi tornava tutto...se qualcuno può cmq provarlo e postare eventuali incongruenze, oppure postare altre sequenze non sarebbe una brutta cosa!

Il mio risultato è quasi uguale al tuo, con la differenza che il mio, come output del comando 'p', cita alcune volte l'automa "000" che il tuo output non cita mai.

Il diff tra il mio e il tuo output è

90d89
< 000: 1, 3
109d107
< 000: 1, 3
114d111
< 000: 1, 3
123d119
< 000: 1, 3

A me sembra che sia giusta la mia versione, dato che un automa "000" viene effettivamente creato e c'è almeno un comando 'p' che chiama gli automi con prefisso "0".

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

21-02-2005 02:15

p2p

.arcimaestro.

User info:

Registered: Oct 2002
Posts: 377 (0.04 al dì)
Location:
Corso: informatica
Anno:
Time Online: 4 Days, 7:49:11 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Originally posted by Skilotto83
ho finito....!!!!!!
solo mi rimane un problema su un output.....
dopo il segnale...l'automa 01 a me nn si muove in 2,7...invece sekondo il prof si muove e giunge a destinazione...nessuno ha lo stesso problema???
+E poi...ma l'output vuole che si veda tutto in una volta come esempio..o dopo ogni singola istruzione che stampa???
Perchè a me printa dopo ogni comando di "posizione", "esiste percorso" e "tortuosità"...va bene no??

anch io ho lo stesso problema, lo 01 resta in 8 -4 e non si sposta... questo problema io l ho anche con 10 e 11 non so, potrebbe essere calcolato male la distanza,cioe' il modulo x-x0 + y-y0 forse...
a te che distanze vengono?io ho usato questa istruzione:
(abs(xsorg - xautoma)) + (abs(ysorg - yautoma));

è giusta?

21-02-2005 09:20

Click here to Send p2p a Private Message

elpampero

Aniversario

User info:

Registered: Sep 2003
Posts: 911 (0.11 al dì)
Location: Milano
Corso: Informatica Magistrale
Anno: I
Time Online: 8 Days, 3:06:36 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

A me viene come ha detto il prof..controllate bene anche l'input

21-02-2005 09:30

Click here to Send elpampero a Private Message

elpampero

Aniversario

User info:

Registered: Sep 2003
Posts: 911 (0.11 al dì)
Location: Milano
Corso: Informatica Magistrale
Anno: I
Time Online: 8 Days, 3:06:36 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

S' 2p2 la funzione scritta così è corretta

21-02-2005 09:37

mattcobain

I am my own parasite

User info:

Registered: Oct 2003
Posts: 1033 (0.13 al dì)
Location: Periferia sud-ovest
Corso: Informatica Magistrale
Anno: Fuori corso
Time Online: 13 Days, 19:47:00: [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Re: Re: PROVIAMO L'OUTPUT

Originally posted by LjL
Il mio risultato è quasi uguale al tuo, con la differenza che il mio, come output del comando 'p', cita alcune volte l'automa "000" che il tuo output non cita mai.

Il diff tra il mio e il tuo output è

90d89
< 000: 1, 3
109d107
< 000: 1, 3
114d111
< 000: 1, 3
123d119
< 000: 1, 3

A me sembra che sia giusta la mia versione, dato che un automa "000" viene effettivamente creato e c'è almeno un comando 'p' che chiama gli automi con prefisso "0".

davvero sicuro che la tua versione sia giusta?
se guardi bene nell'input l'automa 000 che creo tento di metterlo in posizione (1,3) dove in realtò c'è il primo ostacolo che era stato inserito col comando " o 1 3 4 6" (in particolare, nel punto (1,3) c'è lo spigolo in basso a destra dell'ostacolo considerato)
se un automa va a posizionarsi su un punto appartenente ad un ostacolo, il testo del progetto dice che la funzione automa() non fa niente e quindi non inserisce l'automa....a questo punto penso che la versione giusta sia la mia....che dici?

Last edited by mattcobain on 21-02-2005 at 12:40

21-02-2005 12:16

Click Here to See the Blog of mattcobain

Click here to Send mattcobain a Private Message

Mosco

M&M

User info:

Registered: Feb 2004
Posts: 648 (0.08 al dì)
Location: Varallo Sesia
Corso: Informatica triennale
Anno: Dottore! :-)
Time Online: 4 Days, 19:17:17 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Ciao a tutti qualcuno di voi sarebbe così gentile da spiegarmi per quale motivo l'automa 00 e l'automa 1 non possono raggingere il segnale dato che il prof Fiorentini non mi da una risposta? Io mi sono fatto una tabella con excel e ho inserito gli ostacoli e i relativi automi ma da questa mi risulta che solo l'automa 0 non può raggingere il segnale...e ciò mi compare anche dall'algoritmo che ho sviluppato...qualcuno può dirmi cosa non va del mio ragionamento?..o magari è l'output sbagliato?
grazie

21-02-2005 12:27

Click here to Send Mosco a Private Message

LjL

.consigliere.

User info:

Registered: Dec 2003
Posts: 144 (0.02 al dì)
Location: Milano
Corso: Informatica
Anno: Primo
Time Online: 16:25:17 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Re: Re: Re: PROVIAMO L'OUTPUT

Originally posted by mattcobain
davvero sicuro che la tua versione sia giusta?
se guardi bene nell'input l'automa 000 che creo tento di metterlo in posizione (1,3) dove in realtò c'è il primo ostacolo che era stato inserito col comando " o 1 3 4 6" (in particolare, nel punto (1,3) c'è lo spigolo in basso a destra dell'ostacolo considerato)
se un automa va a posizionarsi su un punto appartenente ad un ostacolo, il testo del progetto dice che la funzione automa() non fa niente e quindi non inserisce l'automa....a questo punto penso che la versione giusta sia la mia....che dici?

Si', hai ragione tu. In effetti sapevo che il mio programma non considera ancora questi casi, ma mi era proprio scappato di mente... (erano anche le 3 di notte

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

21-02-2005 12:52

LjL

.consigliere.

User info:

Registered: Dec 2003
Posts: 144 (0.02 al dì)
Location: Milano
Corso: Informatica
Anno: Primo
Time Online: 16:25:17 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Originally posted by p2p
anch io ho lo stesso problema, lo 01 resta in 8 -4 e non si sposta... questo problema io l ho anche con 10 e 11 non so, potrebbe essere calcolato male la distanza,cioe' il modulo x-x0 + y-y0 forse...
a te che distanze vengono?io ho usato questa istruzione:
(abs(xsorg - xautoma)) + (abs(ysorg - yautoma));

è giusta?

E' giusta.
Piu' che questo, controllate se avete fatto i test nell'ordine giusto e e calcolate nella maniera corretta il minimo tra le distanze.

Se io ho capito bene, si determina quali automi devono muoversi in questo modo:
1) tra tutti gli automi, scegliere queli che corrispondono al prefisso indicato
2) tra questi, scegliere quelli per cui esiste un percorso libero da ostacoli
3) tra questi, scegliere quelli che si trovano a distanza minima dal richiamo
4) quelli che rimangono si muovono verso il richiamo

In particolare vi faccio notare che il punto 2 viene *prima* del punto 3. In realta' nel codice possono essere combinati per risparmiare qualche ciclo, ma se li combinate, state veramente attenti a farlo nel modo corretto.

L'altra questione e' il calcolo della distanza minima: se non usate metodi particolarmente arcani, suppongo che avrete una variabile "distanza minima" che aggiornate ogni volta che trovate un automa che la diminuisce... ecco, con che valore inizializzate questa variabile? E' facile che il problema stia li'.

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

21-02-2005 13:05

elpampero

Aniversario

User info:

Registered: Sep 2003
Posts: 911 (0.11 al dì)
Location: Milano
Corso: Informatica Magistrale
Anno: I
Time Online: 8 Days, 3:06:36 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Per mosco. Non raggiunge il segnale perchè la distanza tra l'automa 1 e il segnale non è quella minima che hanno invece gli altri due automi!

21-02-2005 13:08

Mosco

M&M

Post actions:

Edit | Report | IP: Logged

è proprio quello che non riesco a capire..perchè a me l'automa 00 e l'automa 1 ragginge il segnale con un percorso di distanza minima..e rispettivamente l'automa 1 in 18 passi e l'automa 00 in 22...sbaglio a calcolare la distanza minima?
ho usato D = abs(x1-x2) + abs(y1-y2);

21-02-2005 13:22

LjL

.consigliere.

User info:

Registered: Dec 2003
Posts: 144 (0.02 al dì)
Location: Milano
Corso: Informatica
Anno: Primo
Time Online: 16:25:17 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Originally posted by Mosco
è proprio quello che non riesco a capire..perchè a me l'automa 00 e l'automa 1 ragginge il segnale con un percorso di distanza minima..e rispettivamente l'automa 1 in 18 passi e l'automa 00 in 22...sbaglio a calcolare la distanza minima?
ho usato D = abs(x1-x2) + abs(y1-y2);

Esempio: 00 può raggiungere il richiamo in 22 passi, ma 0 può raggiungerlo in 15, quindi 00 non si muove.
Se leggi anche la mia risposta a p2p dovresti capire qual è la questione.

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

21-02-2005 13:41

Mosco

M&M

Post actions:

Edit | Report | IP: Logged

Grazie LjL tutto chiarito...mi era sfuggita sta cosa...il che significa riguardare tutta la funzione....consegnarlo entro giovedì è la mia impresa epica..

21-02-2005 13:47

LjL

.consigliere.

User info:

Registered: Dec 2003
Posts: 144 (0.02 al dì)
Location: Milano
Corso: Informatica
Anno: Primo
Time Online: 16:25:17 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Tirando le somme...

Adesso che il mio progetto è completo e (salvo alcuni casi particolari e segmentation fault vari che dovrò sistemare) sembra funzionare, posso indicarvi dei livelli di efficienza che sicuramente si possono raggiungere -- poi nessuno vieta che ne ne possano raggiungere anche di migliori, ovviamente.

- Detto 'n' il numero degli ostacoli e degli automi presenti, il piano può essere rappresentato con una struttura di dimensioni O(n²) che permette inserimento e ricerca in tempo O(n) per chiavi di tipo (x,y), senza privilegiare la x o la y.

- La ricerca degli automi che rispondono a un determinato prefisso di lunghezza k può, nel caso migliore, essere portata a termine in tempo @(k+m), dove m è il numero degli automi il cui come ha il prefisso cercato. In realtà sono abbastanza convinto che si possa raggiungere @(k+m) anche nel caso peggiore.

- Il calcolo della tortuosità per un automa può essere portato a termine in tempo O(n²), utilizzando una quantità di spazio O(n²), e volendo anche molto meno, direi O(n) ma non ne sono sicuro. Non sono in grado di dire quale sia la complessità in tempo del mio algoritmo nel caso medio (probabilmente sempre @(n²)), ma sono quasi sicuro che possa essere diminuita: infatti il mio algoritmo risolve in molti casi dei sottoproblemi che apparentemente si potrebbe evitare di considerare. Probabilmente il caso medio può arrivare fino a @(a*n), dove 'a' a occhio e croce sta tra una costante e un logaritmo.

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Last edited by LjL on 21-02-2005 at 14:18

21-02-2005 14:13

LjL

.consigliere.

User info:

Registered: Dec 2003
Posts: 144 (0.02 al dì)
Location: Milano
Corso: Informatica
Anno: Primo
Time Online: 16:25:17 [...]
Status: Offline