 | |
Il progetto dsy.it è l'unofficial support site dei corsi di laurea del Dipartimento di Scienze dell'Informazione e del Dipartimento di Informatica e Comunicazione della Statale di Milano. E' un servizio degli studenti per gli studenti, curato in modo no-profit da un gruppo di essi. I nostri servizi comprendono aree di discussione per ogni Corso di Laurea, un'area download per lo scambio file, una raccolta di link e un motore di ricerca, il supporto agli studenti lavoratori, il forum hosting per Professori e studenti, i blog, e molto altro...
In questa sezione è indicizzato in textonly il contenuto del nostro forum |
[Algoritmi] Progetto "RICHIAMI"
Clicca QUI per vedere il messaggio nel forum |
| elpampero |
| E' in uscita il nuovo progetto di algoritmi valido per l'appello dell'8 Febbraio 2005. In bocca al lupo |
| wingzero |
Vengono dati 3 giorni in meno rispetto all'appello di Gennaio a quanto sembra :sad:
Il che fa 15gg invece di 18gg disponibili. |
| elpampero |
| Sì, ho notato anch'io. Speriamo almeno sia più semplice :-) |
| wingzero |
Originally posted by elpampero
Sì, ho notato anch'io. Speriamo almeno sia più semplice :-)
Ho letto ora il progetto, il file è online.
A me sembra più difficile di quello di Gennaio. :sad:
Sinceramente speravo in qualcosa di diverso da problemi sugli automi questa volta. :sad:
Provo a scriverlo ma temo di non riuscire a completarlo in tempo e di dover saltare all'appello di Aprile. :sad: |
| mitnik |
| Da una prima lettura non sembra più semplice, anzi il calcolo delle tortuosità non mi sembra banale. Però vedremo! ciao |
| Skilotto83 |
e infatti anche a me nn sembra piu' semplice..direi che è kome il precedente ma on in piu' il calcolo della tortuosita'..che deve essere un bel macello...
speriamo...ora si vedra'... |
| Skilotto83 |
| io mi kiedo poi con quale fottutissima logica decida di dare 4 giorni in meno per un progetto che è molto piu' difficile del precedente... |
| fdecollibus |
| Già, perchè 4 giorni in meno? Perchè diavolo darci 4 giorni in meno? |
| Jacoposki |
progetto facile, vedo... esistePercorso e tortuosità già mi mettono in difficoltà al solo pensiero...
ma più che altro davvero si aspettano che nel modo in cui abbiamo fatto il C a lezione noi si sia in grado di fare un progetto del genere? bah. |
| Jacoposki |
tra l'altro, cominciamo bene... qualcuno si ricorda le operazioni per far funzionare gcc? :D
C'era un "gocs - qualcosa" da mettere da qualche parte nel prompt... non ricordo il "qualcosa" e dove andava scritto... nella cartella che contiene il codice? in C:\? Da qualsiasi parte? Nella cartella del compilatore? 'iuto! |
| elpampero |
| Gli automi come li organizzate? io direi in un albero binario di ricerca... |
| elpampero |
| Come lo creiamo un piano? |
| mitnik |
il piano direi che è l'ultima cosa da fare nel senso che crei una struttura che contiene gli automi e gii ostacoli e tutto cio che serve. La funzione crea praticamente svuota tutto il contenuto delle strutture ottenendo quindi un "piano" vuoto.
Una domanda: come mai all'istruzione e -10000 6 11 da come output SI ? |
| mitnik |
Ho capito, pensavo la stringa -10000 fossa la stringa binaria. (che pirla)
Ciao |
| elpampero |
| Perchè esiste un percorso libero che l'automa P(11) puo' fare verso il punto(-10000,6) |
| elpampero |
| Gli automi li gestisci con un albero binario di ricerca? |
| mitnik |
| io pensavo semplicemente di metterli in una lista, così come gli ostacoli. Non sarà la cosa più efficiente ma sicuramente da implementare è molto semplice. |
| mitnik |
| bisogna fare attenzione anche al nome dell'automa e al segnale. il testo dice che è una stringa finita ma non dice che è anche limitata superiormente. Con questo voglio dire che non si può memorizzare in un semplice array anche se molto grande. O no? |
| elpampero |
| Non puoi metterla in un array perchè non sai a priori quanto è grande l'array..devi per forza allocare memoria dinamica...Io comunque metto gli automi in un albero. E' più difficile da implementare ma è sicuramente più efficiente |
| mitnik |
| Ok allora uso la realloc per l'input, metto gli automi in una lista, gli ostacoli in un' altra lista. Fin qui ok, ora devo capire come calcolare la tortuosità. |
| Faquets |
| Scusate, qualcuno sa se per il progetto c'e' bisogno di iscriversi al sifa (per il fatto dei registri elettronici)? |
| elpampero |
| Sì, bisogna iscriversi una settimana prima dell'uscita del progetto |
| Skilotto83 |
cavolo..ma la storia della tortuosita' è allucinante...
in pratica dalla posizione in cui è l'automa deve fare tutte le possibili combinazioni di movimenti..perchè per evitare l'ostacolo potrebbe dover fare 50 volte a zig zag....
e ogni tentativo che ha successo(cioè l'automa ariva a destinazione senza aver trovato ostacoli)deve essere memorizzato con il num di cambi di direzione(tortuosita')in modo da poter poi scegliere il percorso con minor cambi...
senza dimenticare che prima di tutto cio' deve aver scelto di muovere solo gli automi a distanza minima dalla destinazione...quindi bisogna tener traccia di tutte le distanze di tutti gli automi dalla destinazione...per poi scegliere solo quelli con distanza minore...
La vedo dura.... |
| mattcobain |
Originally posted by Skilotto83
io mi kiedo poi con quale fottutissima logica decida di dare 4 giorni in meno per un progetto che è molto piu' difficile del precedente...
e pensa che se non sbaglio il progetto dell'11 gennaio era già online la sera del 9 gennaio, oppure la mattina del 10 se non ricordo male....
cmq è da tutto il giorno che penso a sto coso e ancora l'unica cosa che ho fatto è una specie di main come i classici che faceva anche a lezione....e poi basta, non saprei proprio da dove cominciare....ogni volta che penso a qualcosa di buono poi mi viene in mente che bisogna tenere conto anche di altre cose e mi perdo tutto il ragionamento....
e soprattutto....non capisco come sia possibile che dopo quel "corso" di laboratorio del prof fiorentini (se corso lo si può chiamare) esca un progetto del genere....considerando che a meno di un mese dalle fine delle lezioni stava ancora spiegando le stringhe!!!!!
mah...
e per fortuna che già avevo un minimo di conoscenze del c e del java....chissà se mi basteranno!!! |
| mark |
Originally posted by mitnik
io pensavo semplicemente di metterli in una lista, così come gli ostacoli. Non sarà la cosa più efficiente ma sicuramente da implementare è molto semplice.
magari è meglio usare le strutture ed allocarne 'n' dinamicamente
p.s.
il progetto dura solo per un appello ? |
| lino |
| Beh il main è la cosa piu' facile da fare, voi costruite un albero binario di ricerca?Secondo me è la cosa piu efficiente... 2 strutture per automa ed ostacolo. |
| maurozaninelli |
| scusate la domanda, ma, continuo a vedere proposte relative ad alberi di ricerca binari, ma ancora non riesco a capire quale sia la chave che vorreste usare per l'ordinamento del nodo: il nome comvertito in decimale? tenuto in binario? e se gli automi sono solo due: 01, 0000000001??? |
| ZeroByte |
| Scusate, ma nel testo viene specificato che un passo unitario orizzontale è un segmento della forma {(x,y0) | x0 <= x <= xo + 1}, così come un passo unitario verticale è un segmento della forma {(x0,y) | y0 <= y <= yo + 1}, e che un percorso è una successione di tali movimenti. Dalla forma, intuisco che siano ammessi solo spostamenti nel senso positivo delle ascisse e delle ordinate (ossia spostamenti "verso l'alto" e "verso destra"). Come è possibile che l'automa 11 dell'esempio possa raggiungere la sorgente spostandosi nel verso negativo delle ordinate? |
| superfabius |
Originally posted by ZeroByte
Scusate, ma nel testo viene specificato che un passo unitario orizzontale è un segmento della forma {(x,y0) | x0 <= x <= xo + 1}, così come un passo unitario verticale è un segmento della forma {(x0,y) | y0 <= y <= yo + 1}, e che un percorso è una successione di tali movimenti. Dalla forma, intuisco che siano ammessi solo spostamenti nel senso positivo delle ascisse e delle ordinate (ossia spostamenti "verso l'alto" e "verso destra"). Come è possibile che l'automa 11 dell'esempio possa raggiungere la sorgente spostandosi nel verso negativo delle ordinate?
ti dice che x0, y0 sono interi....non specifica interi positivi quindi si possono muovere dove vuoi |
| Skilotto83 |
| si possono muovere solo in positivo...altrimenti nn vedo dove sia il problema per raggiungere una destinazione..basterebbe girare intorno a tutti gli ostacoli... |
| p2p |
comunque a proposito del nome dell' automa anch io avevo pensato all' uso della realloc e effettivamente funziona, pero' agli orali scorsi Fiorentini aveva detto che questa soluzione non gli paceva molto e che preferiva usare getchar e scanf in un ciclo.
Pero' se funziona,amen, al limite mi dira' che avrei potuto fare diversamente. |
| superfabius |
Bhè ma se fosse come dite voi allora gli automi 10 11 100 101 si sposterebbero tutti in senso negativo. O sbaglio? Il problema di aggirare gli ostacoli è dato dal fatto che gli automi devono fare un percorso pari alla distanza minima. Gli automi considerati hanno infatti distanza 8 e 9 dal punto x e nei percorsi che poi vengono considerati rispettano tale distanza. Invece l'automa 110 ad esempio ha distanza minima 8. Per arrivare a x pero' deve aggirare l'ostacolo prima spostandosi in alto di uno (+1) successivamente a sinistra di 8 (+8) e poi in giu' di 1....va a finire che il percorso che deve fare è lungo 10 caselle...>8 e quindi non puo' spostarsi
io lo intendo cosi' |
| wingzero |
Originally posted by superfabius
Bhè ma se fosse come dite voi allora gli automi 10 11 100 101 si sposterebbero tutti in senso negativo. O sbaglio? Il problema di aggirare gli ostacoli è dato dal fatto che gli automi devono fare un percorso pari alla distanza minima. Gli automi considerati hanno infatti distanza 8 e 9 dal punto x e nei percorsi che poi vengono considerati rispettano tale distanza. Invece l'automa 110 ad esempio ha distanza minima 8. Per arrivare a x pero' deve aggirare l'ostacolo prima spostandosi in alto di uno (+1) successivamente a sinistra di 8 (+8) e poi in giu' di 1....va a finire che il percorso che deve fare è lungo 10 caselle...>8 e quindi non puo' spostarsi
io lo intendo cosi'
Non può spostarsi per via della tortuosità, perchè aggirando l'ostacolo deve "ruotare", cioè cambiare direzione ed il percorso minimo è quello con tortuosità 0 ma impossibile per via dell'ostacolo.
101 e 100 raggiungono X e si spostano in direzione negativa. 101 ha più di un percorso per raggiungere X con distanza 8 ma la decisione di quale usare dipende dalla tortuosità. |
| elpampero |
| Per P2P. Non ti seguo molto sul nome dell'automa...Cosa centra il ciclo? |
| elpampero |
| Intendi un ciclo while con all'interno uno switch-case? |
| p2p |
Originally posted by elpampero
Per P2P. Non ti seguo molto sul nome dell'automa...Cosa centra il ciclo?
fai un
while( c = getchar() != '\n') /*cioe' finchè non si va a capo*/
scanf ("%d",&num)
.... poi qui metti i valori c e num in una struttura
... cioe' continui a leggere da input e memorizzi in una struttura a tua scelta a esempio una lista
PS. Tks LoneWolf :) |
| elpampero |
| ah ok...Direi poero' che più che per l'intero va fatto per il char... |
| elpampero |
| Mi sta venendo un altro dubbio: il nome dell'automa lo trattate come intero o come una stringa. Nel caso dell'intero diventa tutto più semplice anche per la creazione della struttura |
| elpampero |
| Mi sta venendo un altro dubbio: il nome dell'automa lo trattate come intero o come una stringa. Nel caso dell'intero diventa tutto più semplice anche per la creazione della struttura |
| p2p |
| come stringa, io uso un *char per memorizzarlo |
| elpampero |
| Perfetto, anch'io uso char* ma nella lettura dello standard input non mi trovo.... |
| p2p |
scusate ma cosa vuol dire nella prima pagina, qunado dice che un percorso è una successione di passi p1...pk tali che pi η pi+1 contiene un solo punto??
che cè un solo punto tra un passo e l altro? |
| elpampero |
| E' un modo complicato per dire che quando esegui più passi il punto finale del passo precedente è il punto iniziale del successivo. Cioè sono passi unitari consecutivi |
| mitnik |
| E' una brutta gatta da pelare questa tortuosità. |
| elpampero |
| Beati voi che vi preoccupate della tortuosità io sono in difficoltà con lo standard input |
| p2p |
| idee per il calcolo del percorso libero?? che è qui il cuore di tutto... |
| faxmaister |
Originally posted by p2p
idee per il calcolo del percorso libero?? che è qui il cuore di tutto...
Mmm io stavo pensando di prendere spunto dal percorso minimo, controllando poi la presenza di eventuali ostacoli. Nel caso in cui trova un ostacolo mi ricalcolo un cammino minimo dal punto in cui mi trovo alla sorgente e via |
| maurozaninelli |
| Scusate l'insistenza, ma... se usarte un albero binario di ricerca per memorizzare gli automi, quale chiave utilizzate??? |
| mitnik |
Io ho risolto con la realloc anche se prima si diceva che fiorenti non l'ha apprezzata, ma sinceramnete creare una lista per contenere un nome di un automa non mi va.
gli ostacoli li metto in una lista
il segnale lo leggo sempre con la realloc.
la funzione posizione è abbastanza semplice.
esistePercorso e tortuosità mi fanno diventare matto; voi avete qualche idea a proposito? |
| elpampero |
| La chiave dei nodi dell'albero di ricerca è il nome |
| p2p |
concordo.. anche se non gli piace funziona quindi io uso realloc (ho fatto una funzione apposita che richiamo ogni volta che devo leggere il nome di un automa, quindi la uso anche per la stampa dei prefissi, per esempio)
strutture: uso un RB-Albero per gli automi perchè è bilanciato... ma soprattutto, anche qui, xchè lo avevo gia' pronto dallo scorso progetto, altrimenti avrei usato un normalissmo albero di ricerca... anche se si puo' sbilanciare una cifra... amen;
uso una lista per gli ostacoli .
per il movimento sto cercando di pensare a qualcosa... |
| mattcobain |
ragazzi...una domanda....
io alloco memoria per un puntatore ad una struttura...inizializzo i campi di questa struttura....poi per vedere se funziona li ho stampati a video....e si vede tutto come dovrebbe essere
poi ho usato free per deallocare lo spazio puntato dal puntatore che avevo creato....ho riprovato ad accedere ai campi della struttura che prima era puntata da tale puntatore, e non so perché ma riesco ancora ad accedervi, sia per modificarli, sia per visualizzarli!!!
è normale!?!?
cioè, se uso free quel puntatore non dovrebbe perdere la traccia della struttura che li ho fatto puntare?!!?
mah....la vedo sempre piu grigia!!! |
| Skilotto83 |
Originally posted by mitnik
esistePercorso e tortuosità mi fanno diventare matto; voi avete qualche idea a proposito?
premettendo che secondo me non si diskute sul fatto che l'automa si possa muovere solo in positivo...e quindi le ascisse e le ordinate possono solo aumentare(come si vede dal testo dove spiega che x è compreso tra x0 e x0+1)....
Io pensavo a due cicli innestati che aumentano una varibaile in ogni ciclo...
In via teorika...l'automa deve provare sikuramente due mosse sempre....aumentare x e aumentare y....
quando aumentando una delle due arriva a pareggiare il livello di x o y..allora significa che è sulla perpendicolare giusta...aumenta l'altro valore e giunge a destinazione...
se invece incontra un ostaolo in questo percorso..allora le cose si complicano...
perkè se anche tento tutti i possibili movimenti dell'automa(è una mazzata paurosa) e trovo un percorso...poi devo tener traccia di tutti gli altri percorsi andati a segno...cosi' da scegliere quello con tortuosita' minima....
stavo perfino pensando che bisogna usare un algoritmo tipo quello di dijkstra per il calcolo del cammino minimo...tipo la visita in ampiezza o qlks di simile...sto sfasando vero??? |
| p2p |
Originally posted by Skilotto83
premettendo che secondo me non si diskute sul fatto che l'automa si possa muovere solo in positivo...e quindi le ascisse e le ordinate possono solo aumentare(come si vede dal testo dove spiega che x è compreso tra x0 e x0+1)....
e qui scusate ma secondo me cè un errore...
se fosse vero com è possibille che nell esempio a pag.2 l automa 11 e 101 si spostino verso la sorgente?se si dovesse solo aumentare le x e le y non sarebbe possibile, giusto? |
| Skilotto83 |
ma allora perchè il 110 e il 111 nn possono ragg X???basta che salgono di un tot, vanno a sx e riscendono...
e perkè 1 nn puo'??? basta che ci gira attorno!!!....nn ha senso!!!!!! |
| Skilotto83 |
io nn posso calcolare tutte i possibili percorsi anche per aggirare l'ostacolo.....
Altrimenti diventa un massacro! |
| Polsy |
Originally posted by Skilotto83
io nn posso calcolare tutte i possibili percorsi anche per aggirare l'ostacolo.....
Altrimenti diventa un massacro!
esattamente per questo motivo 1, 111 e 110 non possono raggiungere X
mi sembra di aver capito che il cammino di un automa non dev'essere + lungo della distanza tra l'automa e la sorgente (cioè la distanza tra le x + la distanza tra le y)
per intenderci, immagina di tracciare un rettangolo ke ha come vertici l'automa e la sorgente, il cammino non deve uscire da quel rettangolo |
| mattcobain |
Originally posted by Skilotto83
ma allora perchè il 110 e il 111 nn possono ragg X???basta che salgono di un tot, vanno a sx e riscendono...
e perkè 1 nn puo'??? basta che ci gira attorno!!!....nn ha senso!!!!!!
110 e 111 e 1 non possono perché facendo i percorsi alternativi detti da te (salire di un tot, andare a sx e riscendere, oppure aggirare tutto l'ostacolo) raggiungerebbero la sorgente del segnale facendo un percorso più lungo di D (che è la distanza minima, sgombra da ostacoli)
possono raggiungere il segnale solo quegli automi che lo raggiungono con un percorso libero (cioè senza passare sopra gli ostacoli) della stessa lunghezza di D (cioè la distanza sgombra da ostacoli)...e fra questi solo quelli che hanno D più piccola....
infatti, sempre dall'esempio, possono raggiungere il segnale 10 con D=8, 11 con D=8, 100 con D=9 e 101 con D=8....fra questi, quelli con D piu piccola sono 10, 11, 101 (la loro D=8, nessun'altro automa ha una D piu bassa) e quindi ecco spiegato il tuo dubbio....spero di essere stato chiaro |
| Jacoposki |
Originally posted by Polsy
per intenderci, immagina di tracciare un rettangolo ke ha come vertici l'automa e la sorgente, il cammino non deve uscire da quel rettangolo
Polsy ha colto il punto, credo... mi sono reso conto di questa cosa stanotte verso le 5 e credo sia piuttosto importante da sapere. |
| Skilotto83 |
infatti l'avevo capito anhe io circa 10min fa...
il pecorso è quello del rettangolo inscitto tra i due vertici che sono dest e pos automa...
ora basta che riesko a dimostrare analitikamente un'ideuzza che ho per la tortuosita' e sono a cavallo... |
| Skilotto83 |
Originally posted by mattcobain
110 e 111 e 1 non possono perché facendo i percorsi alternativi detti da te (salire di un tot, andare a sx e riscendere, oppure aggirare tutto l'ostacolo) raggiungerebbero la sorgente del segnale facendo un percorso più lungo di D (che è la distanza minima, sgombra da ostacoli)
possono raggiungere il segnale solo quegli automi che lo raggiungono con un percorso libero (cioè senza passare sopra gli ostacoli) della stessa lunghezza di D (cioè la distanza sgombra da ostacoli)...e fra questi solo quelli che hanno D più piccola....
infatti, sempre dall'esempio, possono raggiungere il segnale 10 con D=8, 11 con D=8, 100 con D=9 e 101 con D=8....fra questi, quelli con D piu piccola sono 10, 11, 101 (la loro D=8, nessun'altro automa ha una D piu bassa) e quindi ecco spiegato il tuo dubbio....spero di essere stato chiaro
no..il problema nn è quello...il problema è ke l'atoma 110 si puo' muovere solo in linea retta..anke se forse è la stessa kosa che dici tu...boh.. |
| p2p |
si, ma x il fatto che ho postato prima che mi dite??
com è possibile che ad esempio l automa 11 arrivi alla sorgente se un passo unitario fa incrementare la y???l 11 la raggiinge decrementandolo e non viceversa! |
| mattcobain |
Originally posted by p2p
si, ma x il fatto che ho postato prima che mi dite??
com è possibile che ad esempio l automa 11 arrivi alla sorgente se un passo unitario fa incrementare la y???l 11 la raggiinge decrementandolo e non viceversa!
il fatto che il passo unitaio faccia incrementare la y non significa che la y si incrementa è se ne va oltre l'automa 11....puoi vedere il percorso come se parte dalla sorgente, vedi che cmq il percorso alla fine unisce in ogni caso automa e sorgente, considerando solo passi che vanno verso l'alto
cmq, in definitiva, per come il prof ha descritto i passi unitari, non vedo la limitazione che ogni passo deve seguire l'altro in senso incrementale....puoi anche tornare indietro facendo passi di uno e inserendo un altro passo 2 posizioni in negativo piu in la...insomma ,non riesco a spiegartelo però il fatto che x0 e y0 siano interi a scelta non ti limita a fare solo passi o verso l'alto o verso destra....puoi benissimo vederli anche verso il basso e verso sinistra, affiancando i singoli passi nel modo giusto....
che casino ho scritto!!! |
| Skilotto83 |
a questo punto credo che la regola che da lui sia generale..avrebbe potuto mettere X0<X<X0 +/- 1....
puo' essere no?? |
| p2p |
Originally posted by mattcobain
il fatto che il passo unitaio faccia incrementare la y non significa che la y si incrementa è se ne va oltre l'automa 11....puoi vedere il percorso come se parte dalla sorgente, vedi che cmq il percorso alla fine unisce in ogni caso automa e sorgente, considerando solo passi che vanno verso l'alto
cmq, in definitiva, per come il prof ha descritto i passi unitari, non vedo la limitazione che ogni passo deve seguire l'altro in senso incrementale....puoi anche tornare indietro facendo passi di uno e inserendo un altro passo 2 posizioni in negativo piu in la...insomma ,non riesco a spiegartelo però il fatto che x0 e y0 siano interi a scelta non ti limita a fare solo passi o verso l'alto o verso destra....puoi benissimo vederli anche verso il basso e verso sinistra, affiancando i singoli passi nel modo giusto....
che casino ho scritto!!!
:? scusa ma non ho capito nulla:?
se un intero è + o - se gli aggiungi 1 vai o verso l alto o verso destra, a seconda se sia la x o la y.... |
| mattcobain |
vediamo, magari mi spiego meglio
se da un automa non puoi raggiungere la sorgente perché si trova al di sotto o alla sinistra dell'automa stesso (e quindi dovresti muoverti per decrementi secondo il tuo ragionamento) allora in questo caso vedi il percorso come se parta dalla sorgente....
cmq ripeto, non è scritto da nessuna parte che l'automa si muove solo in positivo verso l'alto e verso destra....
se devi scendere vedila come una sequenza di passi, si incrementali per definizione, ma uno successivo all'altro partendo di volta in volta da una x0 (o y0 a seconda del caso) negativa di 2 volte rispetto la precedente....ok, ho fatto ancora casino, non riesco a spiegartelo!!!! :D |
| Skilotto83 |
Originally posted by mattcobain
vediamo, magari mi spiego meglio
se da un automa non puoi raggiungere la sorgente perché si trova al di sotto o alla sinistra dell'automa stesso (e quindi dovresti muoverti per decrementi secondo il tuo ragionamento) allora in questo caso vedi il percorso come se parta dalla sorgente....
cmq ripeto, non è scritto da nessuna parte che l'automa si muove solo in positivo verso l'alto e verso destra....
se devi scendere vedila come una sequenza di passi, si incrementali per definizione, ma uno successivo all'altro partendo di volta in volta da una x0 (o y0 a seconda del caso) negativa di 2 volte rispetto la precedente....ok, ho fatto ancora casino, non riesco a spiegartelo!!!! :D
esatto..incrementare una posizione nn è per forza in positivo...
anche da -2 a -3 incrementi di uno..ma in negativo..
kapito?? |
| p2p |
Originally posted by Skilotto83
esatto..incrementare una posizione nn è per forza in positivo...
anche da -2 a -3 incrementi di uno..ma in negativo..
kapito??
si.. capito, pero' se ho y = 11 e incremento ottengo y =12 e mi allonatno dalla sorgente .... boh scusate ma sono duro di capoccia:sad: |
| mattcobain |
forse ora ce la faccio....
consideriamo il percorso che collega "11" alla sorgente
il percorso è formato solo da passi unitari verticali...la sequenza potrebbe essere questa:
ricordando che un P.U.V è della forma y0 <= Y <= y0 + 1 con y0 scelto fra i numeri interi...la sequenza di passi che da "11" da arrivare alla sorgente è:
P1 : 10 <= Y <= 11 (quindi y0=10)
P2 : 9 <= Y <= 10 (quindi y0=9)
P3 : 8 <= Y <= 9 (quindi y0=8)
P4 : 7 <= Y <= 8 (quindi y0=7)
...
...
...
P8 : 3 <= Y <= 4 (quindi y0=3)
i passi infatti sono 8 in tutto...e ogni passo ha solo un punto in comune con il successivo (come richiesto da progetto)....
ora spero di essermi spiegato....vedi che il percorso si forma alla fine!!!
il prof ha dato quella definizione "matematica" solo per rappresentare un passo, ma non ha detto che l'automa si muove in quel modo!!! l'automa si muove poi seguendo il percorso finale..... |
| p2p |
Originally posted by mattcobain
forse ora ce la faccio....
consideriamo il percorso che collega "11" alla sorgente
il percorso è formato solo da passi unitari verticali...la sequenza potrebbe essere questa:
ricordando che un P.U.V è della forma y0 <= Y <= y0 + 1 con y0 scelto fra i numeri interi...la sequenza di passi che da "11" da arrivare alla sorgente è:
P1 : 10 <= Y <= 11 (quindi y0=10)
P2 : 9 <= Y <= 10 (quindi y0=9)
P3 : 8 <= Y <= 9 (quindi y0=8)
P4 : 7 <= Y <= 8 (quindi y0=7)
...
...
...
P8 : 3 <= Y <= 4 (quindi y0=3)
i passi infatti sono 8 in tutto...e ogni passo ha solo un punto in comune con il successivo (come richiesto da progetto)....
ora spero di essermi spiegato....vedi che il percorso si forma alla fine!!!
il prof ha dato quella definizione "matematica" solo per rappresentare un passo, ma non ha detto che l'automa si muove in quel modo!!! l'automa si muove poi seguendo il percorso finale.....
grande, ho capito, grazie 1000! |
| mattcobain |
woooh, ce l'abbiamo fatta! :ola:
;) bella, ora però stacco, simpson e poi dinuovo al lavoro!!! |
| ZeroByte |
| Dall'esempio del prof. si deduce che sono ammissibili anche i movimenti nel senso negativo delle ascisse e delle ordinate, anche se secondo me al riguardo la spiegazione del prof. lascia molto discutere. |
| maurozaninelli |
Forse avete già risolto il problema del cammino minimo tra sorgente ed automa, ma volevo comunque sottoporvi la mia idea:
1. si costruisce un grafo fatto da tutti e soli gli spostamenti ammissibili tra sorgente e automa, in pratica, solo quelli inscritti nel rettangolo che ha per vertici la Sorg. e l'Aut. e senza i punti occupati da eventuali ostacoli.
2. si visita ricorsivamente il grafo alla ricerca di un cammino libero.
3. la condizione d'uscita è: puntatore figlio SX e DX = Null e distanza = Distanza minima.
4. Per la tortuosità si potrebbe pensare ad un ipotesi greedy per la quale, se si arriva ad un nodo come figlio SX, prima si tenta di proseguire verso il suo Filgio SX verso la sorgente, altrimenti, si tenta un'altra strada. Questo dovrebbe contenere la tortuosità...
Cosa ne pensate???
Io mi sono comunque già arenata nella scrittura della ricorsione... se qulcuno ritiene l'idea buona ed ha suggerimenti... grazie.
Se pensate sia sbagliato... grazie per il tempo che mi farete risparmiare!!! |
| Polsy |
- ostacolo (x0; y0; x1; y1)
Se i punti nel rettangolo R(x0; y0; x1; y1) non contengono alcun automa, inserisce l’ostacolo rappresentato
da R(x0; y0; x1; y1), altrimenti non compie alcuna operazione.
qualke dubbio:
quando creo l'ostacolo devo assicurarmi ke in quell'area non ci siano automi, dato ke memorizzo gli automi ordinandoli per nome, per vedere se un automa è presente in quell'area come faccio? qualcuno ha un'idea migliore di una ricerca esaustiva? dovrei crearmi un'altra struttura che ordina gli automi per posizione? :shock:
e se in quell'area è presente un altro ostacolo? possono sovrapporsi? |
| p2p |
Originally posted by Polsy
- ostacolo (x0; y0; x1; y1)
Se i punti nel rettangolo R(x0; y0; x1; y1) non contengono alcun automa, inserisce l’ostacolo rappresentato
da R(x0; y0; x1; y1), altrimenti non compie alcuna operazione.
qualke dubbio:
quando creo l'ostacolo devo assicurarmi ke in quell'area non ci siano automi, dato ke memorizzo gli automi ordinandoli per nome, per vedere se un automa è presente in quell'area come faccio? qualcuno ha un'idea migliore di una ricerca esaustiva? dovrei crearmi un'altra struttura che ordina gli automi per posizione? :shock:
e se in quell'area è presente un altro ostacolo? possono sovrapporsi?
no, se le coordinate dell' automa non sono chiave devi per forza fare una ricerca completa.
gli ostacoli possono sovrapporsi. |
| faxmaister |
| Ho un problemino con la struct per memorizzare gli automi. Come me lo dichiaro il campo contente il nome? Per ora ho messo un bel char nome[100], ma non va proprio benone eh... se uso un bel char *nome potrebbe andare? Ho paura che mi faccia casino quando alloco dello spazio per aggiungere un'altro automa... |
| luca8684 |
Originally posted by faxmaister
Ho un problemino con la struct per memorizzare gli automi. Come me lo dichiaro il campo contente il nome? Per ora ho messo un bel char nome[100], ma non va proprio benone eh... se uso un bel char *nome potrebbe andare? Ho paura che mi faccia casino quando alloco dello spazio per aggiungere un'altro automa...
No facendo come hai fatto tu non va bene perchè non sai quanto è grossa la stinga del nome dell'automa!! Devi utilizzare il puntatore così puoi allocare quanta memoria vuoi dinamicamente.
Quindi usa char *nome!! |
| Polsy |
Originally posted by maurozaninelli
Forse avete già risolto il problema del cammino minimo tra sorgente ed automa, ma volevo comunque sottoporvi la mia idea:
1. si costruisce un grafo fatto da tutti e soli gli spostamenti ammissibili tra sorgente e automa, in pratica, solo quelli inscritti nel rettangolo che ha per vertici la Sorg. e l'Aut. e senza i punti occupati da eventuali ostacoli.
2. si visita ricorsivamente il grafo alla ricerca di un cammino libero.
3. la condizione d'uscita è: puntatore figlio SX e DX = Null e distanza = Distanza minima.
4. Per la tortuosità si potrebbe pensare ad un ipotesi greedy per la quale, se si arriva ad un nodo come figlio SX, prima si tenta di proseguire verso il suo Filgio SX verso la sorgente, altrimenti, si tenta un'altra strada. Questo dovrebbe contenere la tortuosità...
Cosa ne pensate???
Io mi sono comunque già arenata nella scrittura della ricorsione... se qulcuno ritiene l'idea buona ed ha suggerimenti... grazie.
Se pensate sia sbagliato... grazie per il tempo che mi farete risparmiare!!!
ci avevo pensato ank'io, il problema è ke per creare quel grafo devi prima di tutto individuare i punti liberi confrontando le coordinate DI OGNI PUNTO con quelle degli ostacoli (e se questi sono memorizzati in una lista auguri...) e poi se io ho l'automa in 1,1 e la sorgente in 10,30 e non ho ostacoli in mezzo dovrei mantenere già un grafo con 300 nodi... :shock: |
| Sephirot |
grafo da 300 nodi  |
| maurozaninelli |
| Ma se non conviene usare un grafo, ne quindi una matrice 10x30, come fate seguire e provare i possibili cammini tra due punti??? se avete suggerimenti sono MOLTO ben accetti!!! |
| Skilotto83 |
io ci sto pensando da un kasino..
il problema è ke per una ricerca esaustiva bisogna per forza controllare tutte le posizioni del rettangolo che ha vertici in posiz automa e sorgente....è l'uniko modo....
Pero' è un kasino....
se contiamo 10msec per ogni ricerca di nodo se il rettangolo ha lato 1000 x 1000 sono 1000000 di celle...a voi il calcolo di quanto ci vuole per visitare tutte le celle....
l'uniko vantaggio è ke una volta che ho un percorso con tortuosita' 0 o 1 posso fermarmi perkè menoi di cosi' nn si puo' fare... |
| Skilotto83 |
Originally posted by maurozaninelli
Ma se non conviene usare un grafo, ne quindi una matrice 10x30, come fate seguire e provare i possibili cammini tra due punti??? se avete suggerimenti sono MOLTO ben accetti!!!
sono una cifra di for innestati...come un puntatore che si sposta in tutte le posizioni possibili... |
| p2p |
Originally posted by Skilotto83
sono una cifra di for innestati...come un puntatore che si sposta in tutte le posizioni possibili...
io ho provato 3 diversi algoritmi ma ancora non sono riuscito a farne uno che funzioni con "tutti" i possibili casi... quindi a parte il grafo credo che non ci siano molte altre soluzioni |
| p2p |
scusate, qualcuno è riuscito ad implementare l' idea dei grafi?
come fate a capire quali archi inserire nel grafo?
forse potrei inserire tutti gli archi possibili tra sorgente e automa eliminando i punti coperti da ostacoli.. giusto? pero' come? |
| virtual |
| Forse dico una stupidata.... ma se si facesse backtrack? |
| p2p |
Originally posted by virtual
Forse dico una stupidata.... ma se si facesse backtrack?
sarebbe? |
| virtual |
è un po lunghina da spiegare, comunque è l'algoritmo delle mosse del cavallo che ha spiegato a lezione(lo trovi sulle slide).
Praticamente usi una funzione ricorsiva che ogni volta che incontra un ostacolo torna indietro di uno e cambia direzione.
Sto provando a farla... per ora è ancora in fase embrionale ma credo che l'idea ci sia.... |
| p2p |
Originally posted by virtual
è un po lunghina da spiegare, comunque è l'algoritmo delle mosse del cavallo che ha spiegato a lezione(lo trovi sulle slide).
Praticamente usi una funzione ricorsiva che ogni volta che incontra un ostacolo torna indietro di uno e cambia direzione.
Sto provando a farla... per ora è ancora in fase embrionale ma credo che l'idea ci sia.... ok capiot, su quali slide lo trovo per favore?torelli, fiorentini,aguzzoli?
io stavo cercando di fare una cosa simile, ma ancora ho qualche problema su come stabilire se un automa è bloccato o meno.... |
| virtual |
Lo trovi sulle slide di aguzzoli, pagina 206 del file lucidi04.pdf
Se ci arrivi prima di me fammi un fischio n'è!
..... :-) |
| Granito |
Sto portando avanti anch'io l'idea backtracking. Per adesso sono ancora in fase di adattamento. Comunque dovrebbe essere quella.
Granito. |
| vlaste |
Originally posted by elpampero
La chiave dei nodi dell'albero di ricerca è il nome
Ma se il nome è memorizzato in un char*, come si comparano due nomi al fine di posizionarli correttamente nell'albero?? |
| mark |
Originally posted by luca8684
No facendo come hai fatto tu non va bene perchè non sai quanto è grossa la stinga del nome dell'automa!! Devi utilizzare il puntatore così puoi allocare quanta memoria vuoi dinamicamente.
Quindi usa char *nome!!
ma allora cosa intende con:
Ogni automa è identificato univocamente da un nome , che è una stringa finita sull'alfabeto {0,1}
io ho interpretato che i possibili nomi siano
00
01
10
11 |
| p2p |
in parole povere il nome puo' essere una sequenza di 1 o 0 lunga quanto si vuole.
puo' essere 1
oppure 0
oppure 10101001010100000010110010101010101010101010000001
1
oppure 11111111111111111111111111111111111111111111
........
capito? |
| luca8684 |
Originally posted by mark
ma allora cosa intende con:
Ogni automa è identificato univocamente da un nome , che è una stringa finita sull'alfabeto {0,1}
io ho interpretato che i possibili nomi siano
00
01
10
11
Questa frase dice che il nome è una stringa finita formata da 0 e 1, ma non dice quanto deve essere lunga. Facendo come dici tu potrai mettere solamente 4 automi perchè ogni automa ha un nome diverso quindi limiti il numero di automi. |
| luca8684 |
Mi hai anticipato!!
:( |
| mark |
Originally posted by p2p
in parole povere il nome puo' essere una sequenza di 1 o 0 lunga quanto si vuole.
puo' essere 1
oppure 0
oppure 10101001010100000010110010101010101010101010000001
1
oppure 11111111111111111111111111111111111111111111
........
capito?
peccato, la fscanf() era comodissima :( |
| mark |
| a questa stregua, quando si legge una stringa dal file, è meglio allocare un buffer dinamicamente per ogni parametro, o no ? |
| p2p |
Originally posted by mark
a questa stregua, quando si legge una stringa dal file, è meglio allocare un buffer dinamicamente per ogni parametro, o no ?
quale file? devi leggere da tastiera... |
| mark |
Originally posted by p2p
quale file? devi leggere da tastiera...
da tastiera ?
ma tutte le coordinate degli ostacoli e degli atomi etc... vengono inseriti a mano da chi testerà il nostro programma ?
io sto lavorando con i file
cavolo, non ditemi che sto lavorando per niente |
|
|
|
|
