|
|
|
|
 |
| |
|
 wingzero |
| [QUOTE][i]Originally posted by Novalis [/i]
... |
16-02-2005 08:05 |
|
 |
wingzero |
.precettore.
Registered: Mar 2004
Posts: 96 (0.01 al dì)
Location:
Corso: Diploma Univ. Informatica
Anno: Laureato
Time Online: 1 Day, 11:14:09: [...]
Status: Offline
Edit | Report | IP: Logged |
Originally posted by Novalis
non ho detto mica questo...
gli automi vanno messi nell'albero di ricerca in base alla stringa che viene passata al momento della creazione (detto in soldoni, faccio un ciclo for, e se l'i-esimo carattere è uno zero, vado in un sottoalbero sinistro, se invece è un uno, vado in quello destro).
Una volta emesso un segnale, ad esempio 10101, partirò dalla radice, visiterò prima il sottoalbero destro, poi andrò a sinistra, poi di nuovo a destra, ancora a sinistra e infine a destra: a questo punto tutti gli automi "da qui in giù" sono sensibili al richiamo.
Controllare che poi possano effettivamente muoversi, è una cosa totalmente diversa
La trovo un pò dispendiosa come cosa solo per controllare il prefisso della stringa in pratica.
|
|
16-02-2005 08:05 |
|
|
| |
|
| elpampero |
| EsistePercorso sono riuscito a implementarlo..mi m ... |
16-02-2005 11:08 |
|
|
elpampero |
Aniversario
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
Edit | Report | IP: Logged |
EsistePercorso sono riuscito a implementarlo..mi manca tortuosità e poi è fatta. Ho fatto come è stato detto ieri: con chiamate ricorsive che valutano la posizione corrente e si spostano in base alla destinazione
|
|
16-02-2005 11:08 |
|
|
| |
|
| Petrik22 |
| sono contento per voi che avete gia finito!!!
... |
16-02-2005 15:01 |
|
|
Petrik22 |
:the broser:
Registered: Jul 2003
Posts: 76 (0.01 al dì)
Location: Seregno
Corso: TICom
Anno: ultimo
Time Online: 1 Day, 5:39:38 [...]
Status: Offline
Edit | Report | IP: Logged |
sono contento per voi che avete gia finito!!!
io sono ancora al main!!!! 
__________________
lol
|
|
16-02-2005 15:01 |
|
|
| |
|
| Alececk84 |
| [QUOTE][i]Originally posted by Petrik22 [/i]
... |
16-02-2005 16:22 |
|
|
Alececk84 |
.fò:preciis.
Registered: Oct 2003
Posts: 1656 (0.20 al dì)
Location: Bocch dol ràt
Corso: Informatica
Anno: Almeno dodès
Time Online: 17 Days, 6:52:23 [...]
Status: Offline
Edit | Report | IP: Logged |
Originally posted by Petrik22
sono contento per voi che avete gia finito!!!
io sono ancora al main!!!!
Io devo ancora installare un compilatore...
__________________
Se Ghe L'ìo Me La Dào - MLCM
Corri corri ragazzo ribelle fuma e bevi sotto le stelle...ma non bucare mai la tua pelle se no le stelle non le vedi più...
De bei come nuun la mam la n'en fa più...'lsa rot la machineta e al pà 'lghe tira più...
MY SITE - MY BLOG- MY FOTO ALBUM - MSN: alececk84@hotmail.it
|
|
16-02-2005 16:22 |
|
|
| |
|
| p2p |
| scusate ma mi sapete dire come mai questo codice c ... |
16-02-2005 16:23 |
|
|
p2p |
.arcimaestro.
Registered: Oct 2002
Posts: 377 (0.04 al dì)
Location:
Corso: informatica
Anno:
Time Online: 4 Days, 7:49:11 [...]
Status: Offline
Edit | Report | IP: Logged |
scusate ma mi sapete dire come mai questo codice compila ma fa crashare?ho tutti gli automi nella mia bella lista e adesso voglio confrontare i campi per vedere quali sono quelli con minima istanza che effettivamente andranno spostati:
for che scorre...
if (p->distanza < p->next->distanza)
tmp =p->distanza;
else tmp=p->next->distanza;
}
|
|
16-02-2005 16:23 |
|
|
| |
|
| p2p |
| [QUOTE][i]Originally posted by p2p [/i]
... |
16-02-2005 17:54 |
|
|
p2p |
.arcimaestro.
Registered: Oct 2002
Posts: 377 (0.04 al dì)
Location:
Corso: informatica
Anno:
Time Online: 4 Days, 7:49:11 [...]
Status: Offline
Edit | Report | IP: Logged |
Originally posted by p2p
scusate ma mi sapete dire come mai questo codice compila ma fa crashare?ho tutti gli automi nella mia bella lista e adesso voglio confrontare i campi per vedere quali sono quelli con minima istanza che effettivamente andranno spostati:
for che scorre...
if (p->distanza < p->next->distanza)
tmp =p->distanza;
else tmp=p->next->distanza;
}
mi auto rispondo... l ultimo elemento non ha un puntatore all elemento dopo ovviamente e quindi si incazza solo che come faccio? se blocco prima il controllo l ultimo non viene confrontato.....
|
|
16-02-2005 17:54 |
|
|
| |
|
| Jacoposki |
| non puoi mettere il tutto in un while(next->distan ... |
16-02-2005 18:36 |
|
|
Jacoposki |
.arcimaestro.
Registered: Sep 2004
Posts: 498 (0.06 al dì)
Location: Milano
Corso: Informatica
Anno: in tesi-sa dio per quanto
Time Online: 4 Days, 0:36:57 [...]
Status: Offline
Edit | Report | IP: Logged |
non puoi mettere il tutto in un while(next->distanza != NULL) o qualcosa del genere?
__________________
Mai sottovalutare l'ampiezza di banda di una station wagon piena di nastri lanciata a tutta velocità lungo l'autostrada. - Andrew S. Tanenbaum - Reti di Calcolatori
|
|
16-02-2005 18:36 |
|
|
| |
|
| p2p |
| si ho risolto co un
... |
16-02-2005 22:22 |
|
|
p2p |
.arcimaestro.
Registered: Oct 2002
Posts: 377 (0.04 al dì)
Location:
Corso: informatica
Anno:
Time Online: 4 Days, 7:49:11 [...]
Status: Offline
Edit | Report | IP: Logged |
si ho risolto co un
do{
...
}
while (p->next!=NULL);
|
|
16-02-2005 22:22 |
|
|
| |
|
| LjL |
| [QUOTE][i]Originally posted by wingzero [/i]
... |
16-02-2005 23:30 |
|
|
LjL |
.consigliere.
Registered: Dec 2003
Posts: 144 (0.02 al dì)
Location: Milano
Corso: Informatica
Anno: Primo
Time Online: 16:25:17 [...]
Status: Offline
Edit | Report | IP: Logged |
Originally posted by wingzero
La trovo un pò dispendiosa come cosa solo per controllare il prefisso della stringa in pratica.
Uhm... suggerimenti migliori?
Il testo dice che la lunghezza delle stringhe non dev'essere limitata. Quindi di sicuro un Stringa=malloc(UnNumeroCheMiPiace) non va bene. Si potrebbe usare realloc, d'accordo (oppure fare una lista di stringhe o varie altre cose piuttosto fastidiose).
Anche usando un realloc, però, rimangono due problemi, uno di tempo e uno di spazio:
1) come cercare gli automi che rispondono a un determinato prefisso (complessità @(n), con n uguale al numero totale di automi, nel caso in cui si usino liste dinamiche)
2) come rappresentare le stringhe con poco dispendio di spazio - infatti, mi sembra di fare un'ipotesi ragionevole supponendo che, nel caso medio, ci saranno "parecchi" automi con prefissi comuni
Per il problema 1), senza stare a fare un'analisi, penso che saremo d'accordo che usare un albero sia quantomeno più efficiente che usare una semplice lista. Certo, ci potrebbero essere altre possibilità.
Per il problema 2), mi pare a occhio e croce che la rappresentazione ad albero sia asintoticamente efficiente *almeno* tanto quanto quella a semplici stringhe, anche nel caso peggiore.
Infatti, se non esistessero automi con prefissi in comune, nella rappresentazione ad albero si "sprecherebbe" un nodo per ogni carattere di ogni stringa, se non vado errato. Nella rappresentazione a semplici stringhe si "sprecherebbe" un bit (o più probabilmente, in C, un char) per ogni carattere di ogni stringa.
Chiaramente per un basso numero di automi e/o una bassa lunghezza delle stringhe la rappresentazione ad albero "spreca" molto più spazio, non c'è dubbio - ma asintoticamente no, se quello che ho scritto è vero.
__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
|
|
16-02-2005 23:30 |
|
|
| |
|
| LjL |
| [QUOTE][i]Originally posted by Skilotto83 [/i]
... |
16-02-2005 23:44 |
|
|
LjL |
.consigliere.
Registered: Dec 2003
Posts: 144 (0.02 al dì)
Location: Milano
Corso: Informatica
Anno: Primo
Time Online: 16:25:17 [...]
Status: Offline
Edit | Report | IP: Logged |
Originally posted by Skilotto83
si..ma se faimkome dice lui teorikamente alloki memoria(fai una calloc) per ogni automa che inserisci(nel caso della lista ma anche nel caso dell'albero) e tieni konto ke quando kiedi al coompilatore di darti 2byte in realta' te ne da un macello in piu'...e soprattutto te li da' sparsi in giro per lo stack...
tenendo conto di questo e del tempo che impiega per allocare memoria ogni volta...alla fine sekondo me è meglio allocare direttamente..volendo posso allocare solo 5posizioni e fargli fare continuamente la realloc..nn cambia nulla...
Se il compilatore/OS alloca [molto] più heap (non stack ;-) di quanto ne hai chiesto, fondamentalmente è colpa sua. Non ritengo che sia una cosa di cui si debba preoccupare molto il programmatore.
Il fatto che ti dia roba "sparsa in giro" non vedo perché dovrebbe essere un problema.
Il fatto che ci mette del tempo ad eseguire l'operazione è vero, ma considera che ci vuole del tempo anche per eseguire la realloc() -- e si tratta di *parecchio* tempo, nel caso in cui il sistema sia costretto a copiare tutto il tuo blocco di memoria da un'altra parte.
A volte usare array che possono crescere di dimensione (realloc()) non è una cattiva idea, quindi se tu ritieni che nel tuo caso sia una buona idea, fallo - può darsi che tu abbia ragione. Io ci penserei su un paio di volte però.
__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
|
|
16-02-2005 23:44 |
|
|
| |
|
| LjL |
| [QUOTE][i]Originally posted by mattcobain [/i]
... |
16-02-2005 23:59 |
|
|
LjL |
.consigliere.
Registered: Dec 2003
Posts: 144 (0.02 al dì)
Location: Milano
Corso: Informatica
Anno: Primo
Time Online: 16:25:17 [...]
Status: Offline
Edit | Report | IP: Logged |
Originally posted by mattcobain
scusami, ma in questo modo tu con le liste di adiacenza rappresenti tutti i nodi contenuti nel "rettangolo dei cammini minimi" avente come estremi opposti la sorgente e l'automa vero?!
fra i comandi del prof compare un "e -10000 6 11" e l'automa 11 si trova in (-3,6)....questo significa che la sorgente si trova nel punto (-10000,6), cioè "in linea" con l'automa, ma spostato piu a sinistra lungo le x di ben 9997 nodi (o celle/punti che dir si voglia)....quindi tu costruisci altrettanti nodi nella lista di adiacenza!?!?
e questo caso è "moderato" perché il rettangolo che collega sorgente-automa in realtà è solo un segmento, ma se fosse stato il famoso "rettangolo dei cammini minimi" figurati quanti altri nodi ci sarebbero stati in mezzo.....
cioè, tu stai andando avanti cosi!?....se ho capito male potresti spiegarmi un po come hai agito?!
ti ringrazio.....
io non capisco che dannazione fare!!!!!
Io sono d'accordo con te - costruire una matrice (o un ancora più enorme grafo a liste di adiacenza!) di dimensioni |x0-x|*|y0-y| equivale a trattare il piano come un array, nel caso (caso peggiore) in cui automa e richiamo siano collocati a estremi opposti del piano.
Peccato che trattare il piano come un'array sia esplicitamente vietato dal testo ;-)
[Il piano *non ha* estremi, almeno secondo le specifiche... ma di fatto degli estremi dovremo pur imporli, dato che un long int più di quei 32, massimo 64 bit non tiene. In ogni caso, estremi o non estremi, se c'è un automa in (10000, 10000) e il richiamo è in (0, 0) la matrice da costruire sarà di 10'000*10'000=100'000'000. Sai che bello.]
Neanch'io ho ancora trovato una soluzione alternativa che mi piaccia, ma sono assolutamente convinto che ne esistano, e ne ho anche trovate una o due che fanno abbastanza schifo ma dovrebbero essere comunque meglio di un'enorme matrice gigante brutta e cattiva.
Una roba che ho in mente non è nemmeno ricorsiva: provate a considerare gli *archi* del grafo e non i nodi -- ok, no, non sto dicendo di usare i grafi adesso, dico solo, invece di concentrarvi sulle coordinate del piano, concentratevi sui passi che uniscono tra loro queste coordinate.
Esempio: per ogni arco/passo verticale, che tortuosità avremo "accumulato" quando saremo arrivati lì? Be', dato che ci possiamo arrivare o dall'arco verticale precedente, o dall'arco orizzontale precedente (ma in quel caso la tortuosità aumenterà)......
__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
|
|
16-02-2005 23:59 |
|
|
| |
|
| Polsy |
| [ot]
... |
17-02-2005 00:36 |
|
|
Polsy |
.arcimaestro.
Registered: Dec 2003
Posts: 477 (0.06 al dì)
Location:
Corso: Info phd
Anno:
Time Online: 17 Days, 17:11:50 [...]
Status: Offline
Edit | Report | IP: Logged |
Off-Topic:
ma stralooool!
ho iniziato a scrivere un po' di codice (giusto le funzioni x gestire gli automi) e l'ho mandato al mio ragazzo, lui l'ha compilato sul suo portatile e subito dopo il suo touchpad (ke non dava + segni di vita ormai da settimane) ha ripreso a funzionare!!!
oh, il mio programma non troverà la tortuosità ma resuscita i touchpad
|
|
17-02-2005 00:36 |
|
|
| |
|
| superfabius |
| [QUOTE][i]Originally posted by p2p [/i]
... |
17-02-2005 05:43 |
|
|
superfabius |
.grande:maestro.
Registered: Nov 2002
Posts: 1519 (0.18 al dì)
Location:
Corso:
Anno:
Time Online: 37 Days, 15:58:19 [...]
Status: Offline
Edit | Report | IP: Logged |
Originally posted by p2p
si ho risolto co un
do{
...
}
while (p->next!=NULL);
mi devi una birra
|
|
17-02-2005 05:43 |
|
|
| |
|
| p2p |
| [QUOTE][i]Originally posted by superfabius [/i]
... |
17-02-2005 08:08 |
|
|
p2p |
.arcimaestro.
Registered: Oct 2002
Posts: 377 (0.04 al dì)
Location:
Corso: informatica
Anno:
Time Online: 4 Days, 7:49:11 [...]
Status: Offline
Edit | Report | IP: Logged |
Originally posted by superfabius
mi devi una birra
mitico
|
|
17-02-2005 08:08 |
|
|
| |
|
| All times are GMT. The time now is 23:18. |
|
|
 |
|
 |
|
|
| |
Forum Rules:
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
|
HTML code is OFF
vB code is ON
Smilies are ON
[IMG] code is ON
|
|
|
|
|
|
wingzero
