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

Pages (33): « First ... « 11 12 13 14 [15] 16 17 18 19 » ... Last »
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] Progetto "RICHIAMI" (http://www.dsy.it/forum/showthread.php?threadid=17192)

Posted by wingzero on 16-02-2005 08:05:

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.

Posted by elpampero on 16-02-2005 11:08:

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

Posted by Petrik22 on 16-02-2005 15:01:

sono contento per voi che avete gia finito!!!
io sono ancora al main!!!! :sighsob: :please:

__________________
lol

Posted by Petrik22 on 16-02-2005 15:07:

:climb: :pccrash: :wall: :ueee:

Posted by Alececk84 on 16-02-2005 16:22:

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

Posted by p2p on 16-02-2005 16:23:

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;
}

Posted by p2p on 16-02-2005 17:54:

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

Posted by Jacoposki on 16-02-2005 18:36:

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

Posted by p2p on 16-02-2005 22:22:

si ho risolto co un
do{
...
}
while (p->next!=NULL);

Posted by LjL on 16-02-2005 23:30:

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

Posted by LjL on 16-02-2005 23:44:

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

Posted by LjL on 16-02-2005 23:59:

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

Posted by Polsy on 17-02-2005 00:36:

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

Posted by superfabius on 17-02-2005 05:43:

Originally posted by p2p
si ho risolto co un
do{
...
}
while (p->next!=NULL);

mi devi una birra

Posted by p2p on 17-02-2005 08:08:

Originally posted by superfabius
mi devi una birra

mitico

All times are GMT. The time now is 07:42.

Pages (33): « First ... « 11 12 13 14 [15] 16 17 18 19 » ... Last »
Show all 482 posts from this thread on one page