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

Pages (33): « First ... « 10 11 12 13 [14] 15 16 17 18 » ... 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 15-02-2005 15:12:

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

Sull'input di esempio c'è il comando per calcolo tortuosità , coordinate 1000,2000 per automa 01 (che è su x=8,y=-4). Sono la bellezza di 992*1996 celle di rettangolo da scansionare. Neanche ho provato a simulare l'input su carta per vedere esattamente dove sono gli ostacoli, tuttavia gli algoritmi devono funzionare anche in casi estremi con decine di ostacoli sovrapposti nell'area...

Il tempo rimasto è veramente poco per trovare una soluzione valida ed anche per provare a programmarne una alla meno peggio.

Posted by Skilotto83 on 15-02-2005 15:13:

mi sorge un dubbio...
Io ho utilizzato le liste per fare l'inserimento degli automi, e presumibilmente(anche se ho semi-pronta una versione ad albero)vorrei usare una lista anche per gli ostacoli....
Il problema è ke per una serie di motivi...abbastanza lungo da spiegare..io la lista non la creo allocando ogni volta lo spazio di una strutture e poi muovendo i puntatori...
Ma creando un array di dimensione fissa contenente per ogni cella la struttura automa(e quindi alloco tutto lo spazio subito, tanto lo so quant'è)..poi assegnando valori di testa e coda all'array la gestisco come se fosse una lista....e nel caso ci fosse bisogno alloca nuovo spazio automatikamente....
Dite ke c'è qualke problema??
semplicemente nn uso pratikamente nulla delle strutture viste a lezione..o almeno uso le liste ma non come intende lui...visto ke nn sono di dimensione infinita....

__________________
"Why, Sir, you find no man at all intellectual who is willing to leave London.
No, Sir, when a man is tired of London, he is tired of life; for there is in London all that life can afford."
(DR SAMUEL JOHNSON 1777)

MSN andrea.poretti(at)hotmail.it

Posted by elpampero on 15-02-2005 15:28:

Scusa lino ma sei riuscito a implementare esistePercorso()??

Posted by mattcobain on 15-02-2005 17:23:

Originally posted by Skilotto83
mi sorge un dubbio...
Io ho utilizzato le liste per fare l'inserimento degli automi, e presumibilmente(anche se ho semi-pronta una versione ad albero)vorrei usare una lista anche per gli ostacoli....
Il problema è ke per una serie di motivi...abbastanza lungo da spiegare..io la lista non la creo allocando ogni volta lo spazio di una strutture e poi muovendo i puntatori...
Ma creando un array di dimensione fissa contenente per ogni cella la struttura automa(e quindi alloco tutto lo spazio subito, tanto lo so quant'è)..poi assegnando valori di testa e coda all'array la gestisco come se fosse una lista....e nel caso ci fosse bisogno alloca nuovo spazio automatikamente....
Dite ke c'è qualke problema??
semplicemente nn uso pratikamente nulla delle strutture viste a lezione..o almeno uso le liste ma non come intende lui...visto ke nn sono di dimensione infinita....

secondo me non è una cosa molto saggia implementare una lista con un array....cmq oramai secondo me è gia tanto se si riesce a fare il progetto funzionante....quindi il fine giustifica i mezzi, fai come pensi/trovi meglio, l'importante è che alla fine funzioni!!!!
ma una cosa mi ha lasciato perplesso:

... creando un array di dimensione fissa contenente per ogni cella la struttura automa(e quindi alloco tutto lo spazio subito, tanto lo so quant'è)...

tu dici di sapere quanto è lo spazio da allocare....ma scusa come fai a saperlo!?!? a priori non sai quanti automi ci saranno nel piano!!!!

Posted by Novalis on 15-02-2005 18:07:

(non ho letto le pagine centrali del thread, perdonate eventuali scoperte dell'acqua calda)

Nessuno ha pensato di utilizzare gli alberi di ricerca per gli ostacoli?

Pensavo di utilizzare il valore di ascissa come chiave, ordinare gli elementi in base a questo, e inserire come dato satellite il valore di ordinata.
Una volta individuato il "rettangolo di cammino", possiamo eliminare immediatamente gli ostacoli che non ne fanno parte semplicemente non considerando i sottoalberi che non contengono chiavi comprese tra i due estremi del rettangolo di cammino.

In questo modo, teniamo traccia di tutte le caselle occupate. Quello che non fa parte della nostra "lista nera", è libero e percorribile.

Lo stesso discorso vale per gli automi... un albero di ricerca (e possono essere inseriti in una sola posizione) ci consente di individuare quelli sensibili al richiamo perchè, una volta percorso l'albero seguendo la stringa del messaggio, tutti gli automi presenti nel sottoalbero sono candidati a raggiungere la sorgente.

Ho detto qualcosa di sensato, o avevate già vagliato e scartato l'ipotesi?

Posted by Skilotto83 on 15-02-2005 18:08:

Originally posted by mattcobain
tu dici di sapere quanto è lo spazio da allocare....ma scusa come fai a saperlo!?!? a priori non sai quanti automi ci saranno nel piano!!!!

se leggi piu' avanti capirai che infatti è prevista una funzione di rialloco automatico della memoria nel caso servisse per piu' automi dei previsti(kmq l'arrai è inizializzato a 100)...

Posted by mattcobain on 15-02-2005 18:13:

Originally posted by Skilotto83
se leggi piu' avanti capirai che infatti è prevista una funzione di rialloco automatico della memoria nel caso servisse per piu' automi dei previsti(kmq l'arrai è inizializzato a 100)...

si avevo visto la parte del rialloco....però non mi sembra cmq la scelta migliore....anche perché tu inizializzi l'array con 100 automi, e magari ne vengono inseriti solo 2....capisci che c'è spreco!!!
cmq come ti ho detto....ormai l'importante è riuscire a fare qlcosa di funzionante!!!!!

Posted by wingzero on 15-02-2005 18:51:

Originally posted by Novalis
(non ho letto le pagine centrali del thread, perdonate eventuali scoperte dell'acqua calda)

Lo stesso discorso vale per gli automi... un albero di ricerca (e possono essere inseriti in una sola posizione) ci consente di individuare quelli sensibili al richiamo perchè, una volta percorso l'albero seguendo la stringa del messaggio, tutti gli automi presenti nel sottoalbero sono candidati a raggiungere la sorgente.

Non dipende dalla posizione in cui si trovano quali automi rispondono al messaggio. La posizione determina rispetto al segnale se poi possono raggiungerlo o meno in base alle condizioni.

Posted by maurozaninelli on 15-02-2005 19:05:

Qualcuno ha provato a dare in input l'esempio del tema d'esame? Il mio risultato corrisponde a meno di un comando: e 7 1 10. Nell'esempio è riportato un No a me viene un Si.
Qualcuno ha avuto lo stesso problema???

Posted by luca8684 on 15-02-2005 19:27:

Originally posted by maurozaninelli
Qualcuno ha provato a dare in input l'esempio del tema d'esame? Il mio risultato corrisponde a meno di un comando: e 7 1 10. Nell'esempio è riportato un No a me viene un Si.
Qualcuno ha avuto lo stesso problema???

Hai già finito????

Che strutture dati hai usato??
:help:

__________________
{¯`·._)-•°o.O`·._.·´¯`•¸·´¯).·´¯`·-> IN DA EEKS <-·´¯`·.(¯`·¸•´¯`·._.·´O.o°•–(¯`·._}

Posted by mattcobain on 15-02-2005 19:29:

Originally posted by maurozaninelli
Qualcuno ha provato a dare in input l'esempio del tema d'esame? Il mio risultato corrisponde a meno di un comando: e 7 1 10. Nell'esempio è riportato un No a me viene un Si.
Qualcuno ha avuto lo stesso problema???

questo significa che hai finito!?!?
complimenti, ma penso che nessuno qui sia al punto di poter provare l'output del programma!!!!!

Posted by Skilotto83 on 15-02-2005 22:01:

Originally posted by mattcobain
si avevo visto la parte del rialloco....però non mi sembra cmq la scelta migliore....anche perché tu inizializzi l'array con 100 automi, e magari ne vengono inseriti solo 2....capisci che c'è spreco!!!
cmq come ti ho detto....ormai l'importante è riuscire a fare qlcosa di funzionante!!!!!

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

Posted by p2p on 15-02-2005 22:26:

:sad:

Posted by Novalis on 16-02-2005 02:21:

Originally posted by wingzero
Non dipende dalla posizione in cui si trovano quali automi rispondono al messaggio. La posizione determina rispetto al segnale se poi possono raggiungerlo o meno in base alle condizioni.

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

Posted by mark on 16-02-2005 07:26:

Originally posted by maurozaninelli
Qualcuno ha provato a dare in input l'esempio del tema d'esame? Il mio risultato corrisponde a meno di un comando: e 7 1 10. Nell'esempio è riportato un No a me viene un Si.
Qualcuno ha avuto lo stesso problema???

a me viene NO in quanto non riesce ad arrivare a destinazione in soli 7 passi; hai di mezzo l'ostacolo (o 3 2 7 6)

sempre che abbia capito il problema

__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....

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

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