Show 150 posts per page
|
Pages (4): « 1 [2] 3 4 » 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)
Ok p2p! Cosa intendi però per punti doppi? Come lo costruiamo un grafo?
Originally posted by elpampero
Forse mi sono espresso male. Noi non dobbiamo trovare il cammino minimo tra i due punti in quanto tale cammino è banalmente data da |x0-x1|+|y0-y1|. Quindi lo visita del nostro grafo non serve per trovare questa distanza rispetto ad altre (in quanto sappiamo già quanto debba essere) ma serve per capire se esite un percorso
Sì, wingzero. Ma la distanza minima si trova con un semplice calcolo! Il problema è stabilire se tra i vari percorsi minimi (tutti con tortuosità diversa) ne esiste almeno uno che arriva a destinazione!
Originally posted by elpampero
Sì, wingzero. Ma la distanza minima si trova con un semplice calcolo! Il problema è stabilire se tra i vari percorsi minimi (tutti con tortuosità diversa) ne esiste almeno uno che arriva a destinazione!
Questo non lo so in quanto non so bene come implementare un grafo orientato.
Se lo implementassimo con una lista di adiacenza saremmo noi a decidere i vertici collegati da archi e il percorso minimo è implicito
Ho pensato a questo piccolo esempio per dimostrare come possa esistere, in presenza di ostacoli, un percorso libero che possa consentire ad un automa a tot coordinate di raggiungere una sorgente in determinate coordinate, ma che essendo un percorso superiore alla distanza minima non debba essere seguito. Tuttavia per saperlo uno deve per forza verificare le combinazioni disponibili dei percorsi liberi.
Intendo questo.
Mappa:
Automa a coordinate iniziali (0,0)
Sorgente a coordinate (6,-7)
[quindi rettangolo 6x7 fra i due punti]
Ostacolo #1, rettangolo da (5,2) a (9,-3)
Ostacolo #2, rettangolo da (-4,-2) a (3,-3)
Ostacolo #3, rettangolo da (4,-5) a (11,-6)
Un percorso libero per automa per raggiungere la sorgente, spostandosi il più possibile verso di essa potrebbe essere:
(0,0) -> destra di 4
(4,0) -> basso di 4
(4,-4) -> sinistra di 1
(3,-4) -> basso di 3
(3,-7) -> destra di 3
(6,-7) RAGGIUNTA LA SORGENTE
Totale distanza : 4+4+1+3+3 = 15
Se l'ostacolo/rettangolo #3 fosse partito da (5,-5) a (11,-6) , allora l'automa avrebbe avuto un percorso di lunghezza equivalente alla distanza minima che è |6-0|+|-7+0|=13. Questo:
(0,0) -> destra di 4
(4,0) -> basso di 7
(4,-7) -> destra di 2
(6,-7) RAGGIUNTA LA SORGENTE
Totale distanza : 4+7+2 = 13
Spero di non aver sbagliato qualche coordinata nell'esempio, altrimenti diventa difficile da riprodurre. 
La presenza degli ostacoli cambia necessariamente le combinazioni esistenti ed in più bisogna calcolarsi il numero di cambi direzione. Il che non rende la distanza minima tanto banale come può sembrare.
Originally posted by wingzero
Mappa:
Automa a coordinate iniziali (0,0)
Sorgente a coordinate (6,-7)
[quindi rettangolo 6x7 fra i due punti]
Ostacolo #1, rettangolo da (5,2) a (9,-3)
Ostacolo #2, rettangolo da (-4,-2) a (3,-3)
Ostacolo #3, rettangolo da (4,-5) a (11,-6)
Un percorso libero per automa per raggiungere la sorgente, spostandosi il più possibile verso di essa potrebbe essere:
(0,0) -> destra di 4
(4,0) -> basso di 4
(4,-4) -> sinistra di 1
(3,-4) -> basso di 3
(3,-7) -> destra di 3
(6,-7) RAGGIUNTA LA SORGENTE
Totale distanza : 4+4+1+3+3 = 15
Se l'ostacolo/rettangolo #3 fosse partito da (5,-5) a (11,-6) , allora l'automa avrebbe avuto un percorso di lunghezza equivalente alla distanza minima che è |6-0|+|-7+0|=13. Questo:
(0,0) -> destra di 4
(4,0) -> basso di 7
(4,-7) -> destra di 2
(6,-7) RAGGIUNTA LA SORGENTE
Totale distanza : 4+7+2 = 13
Metti che un segnale fosse a (10,0)
Spostamento diretto a destra sarebbe distanza 10.
Ma un percorso per raggiungerlo libero aggirando l'ostacolo, e sempre spostandosi verso il segnale: (4,0) -> (4,3) -> (10,3) -> (10,0) = 16
Metti che un segnale fosse a (0,-4)
Spostamento diretto in basso di 4 : impraticabile per ostacolo.
L'automa (0,0) potrebbe raggiungerlo da entrambe le direzioni aggirando l'ostacolo in quella mappa....
sia destra -> basso -> sinistra come movimento
che sinistra -> basso -> destra
Ed in tale caso specifico cosa consideri come congiunzione fra il punto del segnale e l'automa ? Il rettangolo degenerato di larghezza zero e lunghezza 4 o l'altro rettangolo poi ?
Ma soprattutto come fai ragionando così a tenere conto di tutti questi parametri per calcolarti il percorso libero minimo con tortuosità minore ?
Quindi non è detto che esista un solo modo per raggiungere un segnale per un automa, spostandosi sempre verso di esso. Dipende dalle configurazioni della mappa e degli ostacoli....
scusate ma voi non avete per caso trovato un errore nel output del testo..per quanto riguarda il segnale..secondo me sia l'automa 1 sia 0 raggiungono il segnale..ho disegnato su carta il piano con gli automi gli ostacoli..
l'output del prof dice che rimangono fermi, secondo me no..infatti esiste chiaramente il passaggio..bho..ho mandato un'email al prof ma non mi ha risposto..spero in un suo chiarimento
Originally posted by wingzero
Metti che un segnale fosse a (10,0)
Spostamento diretto a destra sarebbe distanza 10.
Ma un percorso per raggiungerlo libero aggirando l'ostacolo, e sempre spostandosi verso il segnale: (4,0) -> (4,3) -> (10,3) -> (10,0) = 16
Metti che un segnale fosse a (0,-4)
Spostamento diretto in basso di 4 : impraticabile per ostacolo.
L'automa (0,0) potrebbe raggiungerlo da entrambe le direzioni aggirando l'ostacolo in quella mappa....
sia destra -> basso -> sinistra come movimento
che sinistra -> basso -> destra
Ed in tale caso specifico cosa consideri come congiunzione fra il punto del segnale e l'automa ? Il rettangolo degenerato di larghezza zero e lunghezza 4 o l'altro rettangolo poi ?
Ma soprattutto come fai ragionando così a tenere conto di tutti questi parametri per calcolarti il percorso libero minimo con tortuosità minore ?
Quindi non è detto che esista un solo modo per raggiungere un segnale per un automa, spostandosi sempre verso di esso. Dipende dalle configurazioni della mappa e degli ostacoli....
Originally posted by nothingman7
scusate ma voi non avete per caso trovato un errore nel output del testo..per quanto riguarda il segnale..secondo me sia l'automa 1 sia 0 raggiungono il segnale..ho disegnato su carta il piano con gli automi gli ostacoli..
l'output del prof dice che rimangono fermi, secondo me no..infatti esiste chiaramente il passaggio..bho..ho mandato un'email al prof ma non mi ha risposto..spero in un suo chiarimento
Polsy, tu come stai implementando il tutto? con un grafo o altro?
Originally posted by Polsy
ragazzi, qui il problema non è trovare il cammino minimo visto ke se poniamo come condizione ke l'automa si debba spostare sempre e solo verso la sorgente...[cut]
come gia' detto da polsy la distanza o lunghezza di ogni percorso è uguale!!!Non puo' essere altrimenti...
Il discorso è che se con il comando alfa=01 si possono muovere 10 automi con distanza 8 e 10 con distanza 9 si muovono solo quelli con distanza 8...
L'unika kosa che conta è la tortuosita'...
io sto facendo un algoritmo per quello...
Solo che il problema è che devo kmq sbattere la testa sull'ostacolo per capire che ho sbagliato...la cosa perfetta sarebbe di saperlo ancor prima di sbatterci...
Ci sto pensando..kazzo...
__________________
"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
Originally posted by p2p
Polsy, tu come stai implementando il tutto? con un grafo o altro?
comunque per il grafo basterebbe crearne uno con le liste di adiacenza eliminando i punti occupati da ostacoli, e poi fare una passata di bfs, no?certo bisogna anche vedere, come diceva virtual di tener traccia dei cambi di direzione
Originally posted by Polsy
come avevo scritto prima ho pensato a una matrice, ma poi il backtracking esaustivo è molto brutto come tempi...diciamo ke quella è proprio l'ultima spiaggia
ora stavo pensando a un grafo di intervalli, di modo da non avere tanti nodi quanti sono i punti, ma tanti nodi quante sono le "strade" (x intenderci, se posso arrivare da A a B in linea retta con n passi, non mi interessa avere n nodi, ma solo 1 nodo di intervallo <posizione di A> - <posizione di B> ) cmq questa idea è ancora in fase embrionale, se riesco a cavarci fuori qualcosa di buono magari lo posto
altre proposte?
io direi di fare un ciclo per ogni nodo e in ogni nodo prendiamo il puntatore alla struttura nodo e ci mettiamo i nodi collegati
io di esistePercorso non ho capito cosa vuole
- ho le coordinate dell'automa
- mi vengono passate delle nuove coordinate più nome automa
da queste due, posso calcolarmi la distanza con la formula indicata nelle PDF
e mo che si fa ?
si prova a spostare l'automa della distanza D calcolata in tutte le direzioni possibili per vedere se non entra in collisione con nessun ostacolo ?
__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....
Ti devi costruire un grafo con liste di adiacenza. Il grafo ha tanti nodi quanto sono i punti del rettangolo inscritto tra l'automa e i punti passati come parametro
Originally posted by elpampero
Ti devi costruire un grafo con liste di adiacenza. Il grafo ha tanti nodi quanto sono i punti del rettangolo inscritto tra l'automa e i punti passati come parametro
__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....
grazie polsy, non avevo capito che c'era da calcolare la distanza minima..
altro dubbio...
nel testo il prof dice che se vogliamo inserire un ostacolo su un automa, NON COMPIE NESSUNA OPERAZIONE..
io mi chiedo..ma neanche una printf per avvertire l'utente??
strano..chi mette l'input dovrà pur sapere se l'inserimento dell'ostacolo ha avuto buon fine o no..
illuminatemi..
Originally posted by nothingman7
altro dubbio...
nel testo il prof dice che se vogliamo inserire un ostacolo su un automa, NON COMPIE NESSUNA OPERAZIONE..
io mi chiedo..ma neanche una printf per avvertire l'utente??
strano..chi mette l'input dovrà pur sapere se l'inserimento dell'ostacolo ha avuto buon fine o no..
illuminatemi..
__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....
Domani fiorentini riceve... io gli vado a parlare ma in realtà non so bene cosa chiedergli visto che finora ci ho capito ben poco. Dopo le 10 nel suo ufficio in Comelico, comunque.
__________________
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
riprovo, casomai qualche volenteroso ha voglia di rispondere a questo mio dubbio
Originally posted by mark
io di esistePercorso non ho capito cosa vuole
- ho le coordinate dell'automa
- mi vengono passate delle nuove coordinate più nome automa
da queste due, posso calcolarmi la distanza con la formula indicata nelle PDF
e mo che si fa ?
si prova a spostare l'automa della distanza D calcolata in tutte le direzioni possibili per vedere se non entra in collisione con nessun ostacolo ?
__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....
una volta fatte le liste di adiacenza e usato il bfs so se è raggiungibile con il percorso minimo la sorgente dal mio automa, e fin qui ok. ma per la totuosita'?? con l uso dei grafi e del bfs so solo se è raggiungibile ma non quale strada è stata fatta! idee?? suggerimenti? soldi?
ragazzi, qualcuno è cosi gentile da accennarmi un minimo cosa siano le liste di adiacenza ed il bfs!?!?
le liste di adiacenza sarebbe delle liste concatenate!?!?
io mi sono perso...ho fatto tutto tranne segnale, esiste percorso e tortuosità perché non so dove sbattere la testa...
ok, mi sono risposto da solo
ora so cosa intende per distanza cammino minimo, tortuosità etc...
certo che siete pigri a rispondere 
__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....
le liste di adiacenza sono liste puntate in testa una cella di un array
grazie...si in effetti stupidamente non avevo neanche aperto il libro prima di chiedere...ho trovato tutto sul libro scusatemi...anche se ancora sto macinando per capire cosa fare
Originally posted by Jacoposki
ma possibile che nessuno abbia bisogno di uno con cui lavorare, da prendere a calci e da cui farsi prendere a calci a mo' di sprone al lavoro?
Io da solo 'sto progetto non lo riesco a fare... insisto: nessuno nessuno nessuno al silab? ;(
Originally posted by vlaste
Raga, io sto cadendo nello sconforto, ho difficoltà anche col comando Crea, non so da dove cominciare, nonostante abbia seguito quasi tutto il corso e abbia fatto un anno di C alle superiori!!!
Un aiuto sarebbe gradito
Originally posted by Polsy
hai pensato a delle strutture in cui organizzare gli automi e gli ostacoli? queste strutture avranno un puntatore all'inizio (root se è un albero, testa se è una lista, etc...), la funzione crea fa questo: se le strutture non sono ancora state create le crea inizializzando i puntatori, se sono già presenti dealloca la memoria occupata da esse (cioè cancella gli automi e gli ostacoli del campo precedente) lasciando solo i puntatori iniziali (ke rappresentano un nuovo campo vuoto)
nota come in tutto ciò non crei il campo, ma quello che sta dentro al campo
__________________
"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
ops...sbagliato....
skusa...
si'...inizializza le strutture di memorizzazione...
devo sistemarlo...
__________________
"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
la funzione crea io l'ho fatta che crea due puntatori, come hai detto tu... uno a NodoRobot, l'altro a NodoOstacolo, e li inizializza a NULL. Non che sia sicuro che si possa fare... mi è sembrata la cosa più sensata, ma sto combattendo con errori di compilazione senza senso.
Oltre a non aver la benchè minima idea di come mettere giù esistePercorso e Tortuosità....
__________________
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
Originally posted by p2p
una volta fatte le liste di adiacenza e usato il bfs so se è raggiungibile con il percorso minimo la sorgente dal mio automa, e fin qui ok. ma per la totuosita'?? con l uso dei grafi e del bfs so solo se è raggiungibile ma non quale strada è stata fatta! idee?? suggerimenti? soldi?
Sinceramente non vedo altro modo....
quindi come intende lui è quello che ho detto io!?!...cioè memorizza tutti i nodi contenuti fra la sorgente e l'automa!?.....ommioddio è una cosa troppo dispendiosa, anzi, troppo è dire poco (scusatemi il gioco di parole)....deve assolutamente esserci almeno un'altra soluzione decisamente più efficente!!!!
anche perché cosi facendo tutti i nodi compresi nel rettangolo fra l'automa e la sorgente vengono "memorizzati" nella/e liste di adiacenza, ma tutti quei nodi non hanno informazioni "utili" per noi....è uno spreco davvero vistoso di spazio, ed il caso che avevo citato dell'esempio del prof è anche abbastanza contenuto, e sono almeno 9997 nodi....figuriamoci se anziché essere sulla stessa ordinata i 2 elementi si fossero trovati in posti completamente opposti e molto distanti....
odddiooooooo 
OK. Chi si prende la briga di scrivere a Fiorentini? Ci darà una dritta o no?
sono passato stamattina da fiorentini.... oltre ad avermi fatto capire che non so una ceppa di C, che sono un coglione, che non ho speranze, che prima di fare il progetto devo affrontare i problemi elementari ecc ecc (simpatico come al solito, insomma), mi ha fatto capire che una soluzione possibile sarebbe l'uso di un algoritmo ricorsivo... vedo come è messa la sorgente rispetto al robot (esempio a destra in basso), allora mi muovo di uno a destra e di uno in basso e vedo se i punti che trovo sono validi, cioè non appartengono ad ostacoli. Se sono validi ripeto ricorsivamente il procedimento sui nuovi punti trovati. Se alla fine arrivo alla sorgente allora esiste un percorso minimo, se mi ritrovo a sbattere contro ostacoli o a uscire dal rettangolo automa-sorgente non esiste un percorso minimo.
Almeno è quanto posso capire io... ha fatto riferimento al capitolo sulla programmazione dinamica per ridurre il carico di lavoro evitando di calcolare più volte gli stessi percorsi.
Ovviamente scarse speranze di potere implementare questa cosa in modo sensato e in tempi ragionevoli... mai cercare di seguire C e Java contemporaneamente... sigh.
__________________
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
Originally posted by Jacoposki
...vedo come è messa la sorgente rispetto al robot (esempio a destra in basso), allora mi muovo di uno a destra e di uno in basso e vedo se i punti che trovo sono validi, cioè non appartengono ad ostacoli. Se sono validi ripeto ricorsivamente il procedimento sui nuovi punti trovati....
Originally posted by Jacoposki
...mai cercare di seguire C e Java contemporaneamente...
Off-Topic:
hai troppa ragione!
Originally posted by mattcobain
ma scusa in questo modo ad ogni passo aumenti di uno la tortuosità....non mi sembra molto furba come cosa....ma ha detto così il prof!?!?!?
__________________
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
qualcuno è riuscito ad implementate tortuosità?
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!!!!!
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
Scusa lino ma sei riuscito a implementare esistePercorso()??
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....
... creando un array di dimensione fissa contenente per ogni cella la struttura automa(e quindi alloco tutto lo spazio subito, tanto lo so quant'è)...
(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?
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!!!!
__________________
"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
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)...
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.
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???
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???
__________________
{¯`·._)-•°o.O`·._.·´¯`•¸·´¯).·´¯`·-> IN DA EEKS <-·´¯`·.(¯`·¸•´¯`·._.·´O.o°•–(¯`·._}
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!?!?
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!!!!!
__________________
"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
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.
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???
__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....
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
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
sono contento per voi che avete gia finito!!!
io sono ancora al main!!!!
__________________
lol
Originally posted by Petrik22
sono contento per voi che avete gia finito!!!
io sono ancora al main!!!!
__________________
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
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;
}
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;
}
solo che come faccio? se blocco prima il controllo l ultimo non viene confrontato.....
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
si ho risolto co un
do{
...
}
while (p->next!=NULL);
Originally posted by wingzero
La trovo un pò dispendiosa come cosa solo per controllare il prefisso della stringa in pratica.
__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
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...
__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
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!!!!!
__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
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
Originally posted by p2p
si ho risolto co un
do{
...
}
while (p->next!=NULL);
Originally posted by superfabius
mi devi una birra
mitico
ragazzi, voi operate su una lista x vedere tra tutti gli automi che raggiungono... bla bla quelli con distanza minima da spostare? o altre strutture??
altra domanda: ma esiste percorso e tortuosita' fanno il discorso del prefisso o prendono il nome di un automa??
Originally posted by p2p
...ma esiste percorso e tortuosita' fanno il discorso del prefisso o prendono il nome di un automa??
Originally posted by LjL
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ò.
__________________
"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
Originally posted by p2p
ragazzi, voi operate su una lista x vedere tra tutti gli automi che raggiungono... bla bla quelli con distanza minima da spostare? o altre strutture??
altra domanda: ma esiste percorso e tortuosita' fanno il discorso del prefisso o prendono il nome di un automa??
__________________
"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
Ciao please potete aiutarmi che sto diventando pazzo!!!!
ma avete trovato una soluzione per il Percorso e la tortuosità?
Originally posted by Skilotto83
il metodo dell'array che uso ha dei vantaggi enormi su tutte le altre strutture:
con un array si accede direttamente ad una posizione, proprio perchè nn sono sparse in memoria...
Quando calcolo se esiste un percorso se mi scontro su un ostacolo so quale ostacolo è, lo indicizzo, e poi ripeto la ricorsione solo su quello e non su tutti gli ostacoli della lista...
lo stesso vale per automa, ho trovato forse il modo di ordinare i nomi degli automi nell'array...quando mi viene chiesto il prefisso degli automi da considerare io accedo direttamente allla posizione corrsipondente al "path" dato..e da li' vado avanti...
Con una lista in tuti i casi devo scorrere dall'inizio, anche se poi il discorso una volta trovato il "path" è lo stesso che con array...
e se devo inserire un automa o un ostacolo devo controllare che la posizione/i nn siano occupate da automi o ostacoli...qui allora devo scorrere tutto l'array..ma scorrere tutto un array o tutta una lista, o tutto un albero è lo stesso..no??
Originally posted by Motomax
Ciao please potete aiutarmi che sto diventando pazzo!!!!
ma avete trovato una soluzione per il Percorso e la tortuosità?
int main (void) ?!
Originally posted by superfabius
int main (void) ?!
__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Originally posted by wingzero
Ma parli di un array di char? Perchè è nulla più di una stringa in pratica in C. Per avere una mappatura corretta con array devi averli multdimensionali. Oppure usare strutture con struct ed a quel punto si usano le liste di norma.
Il grosso problema con l'uso di array, multidimensionali poi (quindi matrici che il professore non vuole che si usino poichè si lavora con una mappa di dimensioni infinite), è che non c'è un modo tanto banale di crearne una rappresentazione compatta. In effetti non c'è neanche con le liste di adiacenza che per una mappa senza limiti (a parte gli interi a 32bit) ed oggetti sparsi ovunque nella mappa rappresenta un grosso problema.
__________________
"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
Originally posted by wingzero
Personalmente no. Ed inizio a rinunciare al fatto di poter consegnare il programma funzionante. Ho dei bei problemi a gestire le liste evitando memory leak di suo, ma poi ad usarle concatenate ancora peggio. E comunque non ho idea di come impostare il calcolo della tortuosità nelle combinazioni di liste di adiacenza, che viste le dimensioni infinite possono diventare onerose da gestire e tendere a crash del programma se il codice non è ben debuggato. E non ho il tempo materiale per debuggarlo.
Spero almeno di poter riusare buona parte delle funzioni che sto creando per il prossimo progetto, sperando sia qualcosa di più semplice.
__________________
"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
Originally posted by Skilotto83
se usi gli array come me risolvi il problema...
Originally posted by Skilotto83
uso un array in cui metto le strutture....
non è vero che si usano le liste di norma...questo è quello che ti ha fatto credere nel suo corso..
ripeto..con le liste allocate dinamicamente le singole celle della lista sono sparse in memoria e non vi si puo' accedere direttamente senza ripetere tutta la ricerca..io invece accedo direttamente a ogni singolo automa o ostacolo che mi serve per il calcolo della tortuosita'...e ti garantisko ke il mio tempo di esecuzione su un metodo come "segnale" (dove senza array ripassi la stessa lista di ostacoli per migliaia di volte) è ottimo...
Originally posted by Skilotto83
il metodo dell'array che uso ha dei vantaggi enormi su tutte le altre strutture:
con un array si accede direttamente ad una posizione, proprio perchè nn sono sparse in memoria...
Quando calcolo se esiste un percorso se mi scontro su un ostacolo so quale ostacolo è, lo indicizzo, e poi ripeto la ricorsione solo su quello e non su tutti gli ostacoli della lista...
lo stesso vale per automa, ho trovato forse il modo di ordinare i nomi degli automi nell'array...
quando mi viene chiesto il prefisso degli automi da considerare io accedo direttamente allla posizione corrsipondente al "path" dato..e da li' vado avanti...
Con una lista in tuti i casi devo scorrere dall'inizio, anche se poi il discorso una volta trovato il "path" è lo stesso che con array...
e se devo inserire un automa o un ostacolo devo controllare che la posizione/i nn siano occupate da automi o ostacoli...qui allora devo scorrere tutto l'array..ma scorrere tutto un array o tutta una lista, o tutto un albero è lo stesso..no??
__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Qualcuno di voi ha un'idea diversa da alberi o liste di adiacenza per implementare esistePercorso? A me sembrano le due uniche strutture accettabili per una cosa simile. Ma soprattutto, c'è qualcuno che è in grado di consegnare in tempo questo progetto? E' solo una mia impressione ma il tempo concesso è davvero poco?
__________________
Un computer ti fa fare più errori e più velocemente di qualunque altra invenzione dell'uomo - con l'eccezione forse delle armi da fuoco e della tequila (Mitch Ratcliffe)
Originally posted by wingzero
[snip]
Scusa ma qui non è che dipenda da come il professore abbia impostato il corso, basta leggersi qualsiasi libro sugli algoritmi come Dijkstra per vedere che si usano le liste di adiacenza. Oppure matrici di adiacenza.
__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Originally posted by ZeroByte
Qualcuno di voi ha un'idea diversa da alberi o liste di adiacenza per implementare esistePercorso? A me sembrano le due uniche strutture accettabili per una cosa simile. Ma soprattutto, c'è qualcuno che è in grado di consegnare in tempo questo progetto? E' solo una mia impressione ma il tempo concesso è davvero poco?
Originally posted by LjL
No, aspetta, a me non sembra così ovvio che *debbano* essere usate liste o matrici di adiacenza.
Infatti, in un grafo generico, si hanno nodi (che non sono [necessariamente] identificati da coordinate [cartesiane]) che possono essere adiacenti (cioè collegati da lati) ad un numero arbitrario di altri nodi.
Nel nostro caso, invece, abbiamo nodi identificati da coordinate cartesiane, che possono essere adiacenti ad al massimo altri quattro nodi. E aggiungendoci pure il fatto che ogni automa si può muovere solo *verso* il richiamo, potresti persino dire che ogni nodo è adiacente ad altri *due* nodi, e che il grafo è orientato.
Con questo non voglio dire che il nostro piano *non* va trattato come un grafo (con relative liste o matrici di adiacenza), solo che è un caso molto più specifico rispetto al caso "grafo generico", e che quindi è probabile che anche le strutture dati possano permettersi di essere più specifiche.
Prendi ad esempio il caso in cui abbiamo un automa in (0,0) e la sorgente in (9,9). Ci vien fuori un grafo con 10*10=100 nodi e 9*10+9*10=180 lati.
Ma se supponiamo che non ci siano ostacoli, per i nostri scopi (calcolo della tortuosità) questo grafo è perfettamente equivalente al semplice grafo con 4 vertici e 4 lati:
o----o
| |
o----X
Infatti di tutti gli altri lati e vertici non ci importa niente, dato che passarci causerebbe solo un aumento della tortuosità.
Certo, in questo caso è semplice, mentre con gli ostacoli di mezzo non riuscirei più a ridurre il grafo così semplicemente. Ma secondo me il punto sta proprio qui: bisognerebbe trovare un algoritmo capace di semplificare i nostri grafi *tenendo conto degli ostacoli*, o meglio ancora fare in modo che, ogni volta che viene creato un automa/ostacolo, questo sia *già* inserito in un grafo semplificato.
Come riuscirci non l'ho ancora capito, ma l'idea di base sarebbe: ogni volta che nel grafo non-semplificato c'è una sequenza di passi (lati) aventi tutti lo stesso orientamento (orizzontale vs verticale), tale sequenza può essere "condensata" (semplificata) in un unico lato con due vertici.
A questo punto, chiaramente, non esisterebbe più la garanzia che da ogni vertice partano al massimo quattro lati.
Ma proprio il fatto che cada questa garanzia potrebbe secondo me permetterci di usare un algoritmo "prefabbricato" a nostra scelta su un "normale" grafo molto più piccolo di quello iniziale.
Originally posted by LjL
No, aspetta, a me non sembra così ovvio che *debbano* essere usate liste o matrici di adiacenza.
Infatti, in un grafo generico, si hanno nodi (che non sono [necessariamente] identificati da coordinate [cartesiane]) che possono essere adiacenti (cioè collegati da lati) ad un numero arbitrario di altri nodi.
Nel nostro caso, invece, abbiamo nodi identificati da coordinate cartesiane, che possono essere adiacenti ad al massimo altri quattro nodi. E aggiungendoci pure il fatto che ogni automa si può muovere solo *verso* il richiamo, potresti persino dire che ogni nodo è adiacente ad altri *due* nodi, e che il grafo è orientato.
Originally posted by LjL
Il fatto è che non credo di aver veramente capito dove, come e quando usi array invece di liste. Vediamo un attimo...
Questo dipende. Si accede "direttamente" (cioè in tempo O(1)) se gli indici dell'array *sono la tua chiave di ricerca*. Se non lo sono, ti tocca o scandirti tutto l'array (esattamente come se fosse una lista) o, solo se gli elementi sono ordinati per chiave, fare qualcosa come una ricerca binaria.
Quindi, tu come indicizzi gli array? Nel caso degli automi,
- Se hai un array di automi in cui ogni indice corrisponde all'ascissa (o all'ordinata) dell'automa, sprechi un sacco di spazio.
- Se hai un array ordinato per ascissa (o per ordinata), puoi fare una ricerca binaria, ma una volta trovata l'ascissa che ti serve vedi comunque trovare l'ordinata. Cosa fai a questo punto, usi un array di array?
- Se hai un array ordinato per nome dell'automa, puoi fare una ricerca binaria per individuare gli automi col prefisso che ti interessa. Vero. Ma per far questo direi che il metodo dell'albero è migliore, anche perché tu così ogni volta che aggiungi un automa devi spostare tutti i successivi elementi dell'array (questo vale anche per il caso precedente!)
Ecco, qui non capisco. Stai dicendo che, oltre all'array di automi, hai anche un array di ostacoli, giusto?
Di nuovo, come sono ordinati gli ostacoli? Qui è anche un filino più complicato perché gli ostacoli hanno *due* coppie di coordinate.
Perché dici "se mi scontro su un ostacolo so quale ostacolo è"? Per *sapere* subito, a colpo sicuro, in tempo O(1), se c'è un ostacolo in un certo punto del piano, dovresti rappresentare il piano come matrice, cosa chiaramente non fattibile. Facendo in un altro modo (salvo cose strane tipo hash) non vedo modo di sapere "a colpo sicuro" se in un certo punto c'è un ostacolo.
O forse intendi dire che, quando ti scontri con un ostacolo (e comunque in che modo controlli se ti sei scontrato?) vai a vedere che punti del piano copre quell'ostacolo, e te li "segni da qualche parte"? È questo che intendi quando dici "lo indicizzo"?
Poi, cosa vuol dire che ripeti la ricorsione solo su quello? Dovrai pur considerare anche gli *altri* ostacoli inscritti nella zona di piano che ti interessa, no? (certo, dipende da cosa fa la tua ricorsione)
Ah, questo prima mi era sfuggito, e quindi la prima parte della mia risposta è inutile, ma l'ho lasciata giusto perché mi spiaceva cancellarla...
Rimane il fatto che mi pare che, per ogni nuovo automa, tu debba spostare tutti gli elementi dell'array successivi alla posizione che dovrà essere occupata dal nuovo automa.
Come fai ad accedere *direttamente* a quella posizione senza fare almeno una ricerchina binaria? Non vedo modo per cui tu, per *ogni* possibile prefisso, possa sapere qual è la posizione nell'array dove gli automi cominciano ad avere quel prefisso.
Si, con una lista devi sempre scorrere dall'inizio. Con un albero no però...
Sì, direi di sì. Credo che a questo sia molto, molto difficile scampare, a meno di non usare strutture piuttosto complesse che permettano una ricerca veloce di automi e ostacoli usando come chiavi le coordinate: ad esempio si potrebbe usare un hash di hash, ma anche volendo spararsi una roba del genere, come si farebbe a sapere se il punto (x,y) appartiene ad un ostacolo? Cerchi x nel primo hash, cerchi y nell'hash di x... e non trovi niente, perché l'ostacolo aveva coordinate (x-a, y-b), (x+c, y+d).
Comunque riguardando il tuo messaggio iniziale rimango piuttosto perplesso: lì dicevi che tu
- crei un array di dimensione fissa contenente, per ogni elemento, i dati di un automa. E ok.
- assegni valori di testa e coda all'array e lo gestisci come una lista. Questa mi sfugge proprio: posso ancora capire il valore di "coda" (più comunemente noto come "numero di elementi nell'array)... ma il valore di "testa"? O sono puntatori? E se sono puntatori, a che ti servono?
Dicevi che, in pratica, usi delle liste, ma non sono "liste dinamiche" nel senso comune del termine, ma "array trattati come liste". E qui non capisco cosa tu intenda con "trattare un array come una lista".
Ogni elemento dentro l'array per caso ha un puntatore all'elemento seguente? Se sì, allora forse ho capito cosa fai -- semplicemente usi delle liste dinamiche ma ti sei in pratica scritto il tuo allocatore di memoria personale invece di usare malloc(). Ma se è così, tu stai effettivamente usando delle liste e non degli array, con tutti i vantaggi e gli svantaggi che ne derivano -- compreso il *non* poter accedere "direttamente" agli elementi.
__________________
"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
Originally posted by Skilotto83
qui ti sei gia' risposto piu' aventi...ho trovato il modo di ordinarli...ma in effetti kmq devo partire dall'inizio...anche se alemno cosi' so' quando finire...il ke mi sembra pari all'uso di un alebro come soluzione...se ho tempo implemento una ricerca dicotomica cosi' da migliorare il tutto...anche se nn di molto...
questo nn lo puoi capire senza vedere il mio metodo di ricerca del percorso...
Kmq l'idea che ho avuto, ancora da sistemare è di dare un indice a ogni ostacolo nel piano, quando cerco il percorso(che nn faccio di una cella alla volta ma di segmenti di lunghezza n)arrivando a sbattare su un ostacolo so qual'è(perkè ha un indice)quindi memorizzo l'indice, lo cerco nel mio bell'array direttamente e poi in base a quello ne "capisco" la struttura cosi'0 da poterlo evitare...il tutto è complicato, ma svolgo una specie di indietreggiamento...
Spero di essere stato chiaro, altrimenti mi spingo troppo oltre...
in effetti oggi ho implementato la cosa e nn posso..ma nn rinuncio alla mia idea in quanto voglio usare la stessa struttura per ostacoli e automi...quindi posso migliorare la cosa con ricerca dicotomica che parte da meta'...ma le cose migliorano su numeri alti...tipo 10000 automi...altrimenti è pratikamente lo stesso..ma è per mostrare al prof che so' il problema e cerco di migliorarlo..
e invece si'...come fai a inserire un nodo senza aver prima guardato dove metterlo??
la testa che intendo è forse quella che tu chiami coda...
kmq semplicemente dopo aver inserito l'automa aumento la posizione dell'array e assegno alla posizione +1 il valore "testa"...mi serve ogni volta che inserisco...se la testa supera il max dim array allora vado in outlist e faccio la realloc...
Originally posted by Skilotto83
qui ti sei gia' risposto piu' aventi...
ho trovato il modo di ordinarli...ma in effetti kmq devo partire dall'inizio...anche se alemno cosi' so' quando finire...il ke mi sembra pari all'uso di un alebro come soluzione...
se ho tempo implemento una ricerca dicotomica cosi' da migliorare il tutto...anche se nn di molto...
questo nn lo puoi capire senza vedere il mio metodo di ricerca del percorso...
Kmq l'idea che ho avuto, ancora da sistemare è di dare un indice a ogni ostacolo nel piano, quando cerco il percorso(che nn faccio di una cella alla volta ma di segmenti di lunghezza n)arrivando a sbattare su un ostacolo so qual'è(perkè ha un indice)quindi memorizzo l'indice, lo cerco nel mio bell'array direttamente e poi in base a quello ne "capisco" la struttura cosi'0 da poterlo evitare...
il tutto è complicato, ma svolgo una specie di indietreggiamento...
Spero di essere stato chiaro, altrimenti mi spingo troppo oltre...
questo kmq lo fai anche con un albero...in tutti i casi per inserire devi scorrere e scegliere la posizione...
[snip]
e invece si'...come fai a inserire un nodo senza aver prima guardato dove metterlo??
la testa che intendo è forse quella che tu chiami coda...
kmq semplicemente dopo aver inserito l'automa aumento la posizione dell'array e assegno alla posizione +1 il valore "testa"...mi serve ogni volta che inserisco...se la testa supera il max dim array allora vado in outlist e faccio la realloc...
__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Originally posted by wingzero
Lo puoi anche dividere in centinaia di segmenti un array utilizzando dei puntatori, non otterrai lo stesso effetto. Se gli array fossero stati sufficienti come pensi tu nessuno avrebbe sviluppato gli ADT (Abstract Data Type) per risolvere i problemi. Gli array in pratica esistono nell'hardware e sono un'astrazione fittizia.
[snip]
Con un array monodimensionale è impossibile tenere traccia di oggetti su un piano bidimensionale. Il minimo possibile è usare una matrice che rappresenti la griglia, quindi un array bidimensionale. Ma non è efficiente ed il professore dice di non usarla.
[snip]
Non è così dispendiosa la cosa come puoi pensare quando si usano le reti con liste di adiacenza. Altrimenti non la userebbe nessuno.
__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Originally posted by wingzero
Sì, bhè, è un grafo orientato (digrafo = digraph dall'inglese = directed graph = grafo orientato), che è un modo per disegnare una rete con archi orientati.
Il grosso problema sta nell'impostare la tortuosità che non so come usarla per calcolare la minore.
Guarda gli archi del tuo grafo... prendi un arco qualsiasi, scegli tu se "orizzontale" (collega due vertici con la stessa y) o "verticale" (stessa y). Supponiamo che ne hai scelto uno verticale: qual è la tortuosità minima con cui puoi raggiungerlo?
Be', a quell'arco o ci arrivi dall'arco verticale precedente, o ci arrivi dall'arco orizzontale precedente, ma in quel caso la tortuosità aumenta.
Mi fermo qui; basti dire che l'algoritmo basato su quello che ho detto per trovare la tortuosità minima con cui puoi raggiungere un arco può facilmente *non essere ricorsivo*, e avere una complessità funzione della distanza in orizzontale e in verticale dell'automa dal richiamo -- che sarebbe a dire che ha una complessità schifosa, dato che ci mette *sempre* più tempo a calcolare la tortuosità per automi lontani dal richiami, anche se non ci sono ostacoli di mezzo. Ma direi che è sempre meglio di niente, e soprattutto è molto meglio dell'algoritmo ricorsivo più ovvio che mi viene in mente (che consiste in: 'sti percorsi provali tutti e vedi qual è il migliore).
[QUOTE]
Ed ho problemi a programmare senza memory leak delle liste di adiacenza...
non riuscirò mai a farle funzionare in tempo per la consegna.. e se anche ci riuscissi poi non saprei come usarle per risolvere il tutto al momento. Quindi ritengo di non essere in grado di consegnare, purtroppo per me.
__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Originally posted by wingzero
Puoi dirlo in caso di mappa priva da ostacoli magari, ma con gli ostacoli il discorso cambia perchè dei percorsi liberi bisognerà far scegliere all'automa quello con minore tortuosità.
Ciò non toglie che è comunque un grafo orientato.
__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Originally posted by LjL
Guarda che una lista o un albero non sono in sé e per sé dei tipi di dati astratti.
Vedi: http://www.swif.uniba.it/lei/foldop...tract+data+type
A mio avviso poi una lista o un albero è un'astrazione tanto quanto lo è un array. Al massimo sono astrazioni più complicate.
Gli array non esistono in hardware, a meno che l'hardware non supporti il concetto di array :-) (evviva la tautologia!)
Per indicizzare un array devi prendere l'indirizzo dove inizia l'array, sommarci l'indice moltiplicato per la dimensione in parole indirizzabili del tipo di dato di ogni elemento, e indirizzare il risultato.
Non so se 'sta roba che ho detto sia astratta o meno, ma mi sembra che lo sia né più né meno di quanto lo sarebbe l'equivalente per le liste o per gli alberi.
ata_Structures:Arrays [/url]Arrays guarantee constant time read and write access, however many lookup operations (find min, find max, find index of an instance of an element) are O(n). Arrays are very efficient in most languages, as lookup and access operations compute the address of an element via a simple formula based on the base address element index.
Arrays typically map directly to contiguous storage locations within your computers memory and are therefore the "Natural" storage structure for most higher level languages.
Simple linear arrays are the basis for most of the other data structures. Many languages do not allow you to allocate any structure except an array, everything else must be implemented on top of the array. The exception is the linked list, that is typically implemented as individually allocated objects, but it is possible to implement a linked list within an array.
se continuo cosi' butto ore per ripondere ai post...
Kmq mi sembra che wingzero sia abbastanza diffidente sulla mia soluzione mentre ljl ha capito il funzionamento e le motivazioni della mia idea di usare array....
kmq quando aggiungo un elemento devo effettivamente far scalare tutte le posizioni in basso di uno, a meno che l'automa debba essere gia' messo in cima alla lista...
Per la questione di come so la struttura dell'ostacolo....vi garantisko ke ho risolto...
se mi scontro su un ostacolo nell'asse x scorro la x finche nn ho piuu' l'ostacolo...lo stesso la y...
Nn vedo il problema...basta gestire la ovrapposizione degli ostacoli....
---------
| |
| | <---------------
---------
in un esempio simile io sbatto sulla parte y..mi basta scorrere y finchè nn è finita...e lo so per coordinate di vertici..analiticamente, in quanto nn ho inserito tutte le celle dell'ostacolo, ma solo i vertici...nn mi devo assolutamente preokkupare della profondita' di tale ostacolo...ragazzi, io ancora nn ho una versione precisissima, ma funziona...è solo questione di capire cosa si ha davanti e quindi deviare il percorso senza sbatterci tutte le volte....
All'inizio avevo pensato di fare una roba tipo che se sbatto su una serie di celle e da li capisco che nn trovo il percorso, le celle le segno come inutili, e quindi nei successivi tentativi nn le considero neanke...dovrebbe essere simile al backtracking..ma kmq nn si hanno miglioramenti notevoli rispetto a una ricerca esaustiva brute force...
__________________
"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
il disegno è venuto male....boh...
kmq è logico che la pate dove sbatto è inizio ostacolo e nn all'interno...
X LJL...
La storia della lunghezza del nome si risolve on una strlen, data questa poi alloco spazio per il nome...questo nella funzione...
In main invece devo usare le realloc per forza...quando leggo da tastiera nn posso farci nulla...
Secondo...uso una strcmp per ordinare i nomi...
Ragazzi..la soluzione magari nn è la migliore...ma mi risulta comoda primo perchè uso la stessa sia per automi che per ostacoli...e questo porta ad una semplicita' mdi lettura del codice...
e secondo perkè kosi' sembra ke mi venga la tortuosita' e il percorso libero....
Certo che se mi avanza tempo e utto funziona cerkero' di inserire automi in un alberello...
Ma gliu ostacoli nn si tokkano..sono in un array e vanno da power cosi'...
__________________
"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
i risultati del prof, mostrano che per l'automa (00) non esiste il percorso
e 12 11 00
a me invece pare proprio che esiste ed è di 36 passi
boh
__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....
ragazzi sono emozionato...ho finito!!!!! 
almeno il codice....ora c'è da fare la relazione, i costi, le prestazioni.....però il grosso è andato.....
io direi, per gli altri che hanno finito, perché non facciamo qualche prova con determinati input dati da noi e confrontiamo i risultati...sarebbe una verifica in più oltre all'output del prof....c'è qualcuno che ci sta?!
PROVIAMO L'OUTPUT
ciao ragazzi...allora, come avevo chiesto, qualcuno ha voglia di controllare l'output dando in input una sequenza comune a noi ma diversa da quella data da fiorentini sul testo del progetto?
io ho provato a dare in input questa sequenza:
code:
c a 2 1 1 a 2 8 10 a 5 11 11 a 8 9 100 a 10 6 101 a 13 3 110 a 12 2 111 e 2 8 1 t 2 8 1 e 5 11 1 t 5 11 1 e 8 9 1 t 8 9 1 e 10 6 1 t 10 6 1 e 13 3 1 t 13 3 1 e 12 2 1 t 12 2 1 o 1 3 4 6 o 3 2 4 7 o 3 0 15 1 o 6 0 10 3 o 6 5 7 8 e -10000 1 1 t -10000 1 1 o -10000 1 -10000 1 e -10000 1 1 t -10000 1 1 e 2 8 1 t 2 8 1 e 5 11 1 t 5 11 1 e 8 9 1 t 8 9 1 e 10 6 1 t 10 6 1 e 13 3 1 t 13 3 1 e 12 2 1 t 12 2 1 p 0 p 1 e 5 3 1 t 5 3 1 e 5 3 10 t 5 3 10 e 5 3 11 t 5 3 11 e 5 3 100 t 5 3 100 e 5 3 101 t 5 3 101 e 5 3 110 t 5 3 110 e 5 3 111 t 5 3 111 s 5 3 1 p 0 p 1 e 5 3 10 t 5 3 10 s 8 9 1 p 0 p 1 s 16 0 11 p 0 p 1 o 2 1 16 12 a 1 3 000 p 0 p 100 e 10000 10000 100 t 10000 10000 100 s 10000 10000 100 p 1 a 10 10 0 a 10 12 00 p 0 a 11 11 00 p 0 e 10 11 0 t 10 11 0 e 10 11 00 t 10 11 00 s 10 11 0 p 0 s 6 6 1 p 1 f
code:
SI 0 SI 1 SI 1 SI 1 SI 1 SI 1 SI 0 NO -1 NO -1 NO -1 NO -1 NO -1 NO -1 NO -1 ( ) ( 1: 2, 1 10: 2, 8 100: 8, 9 101: 10, 6 11: 5, 11 110: 13, 3 111: 12, 2 ) NO -1 SI 1 SI 0 SI 1 SI 2 NO -1 NO -1 ( ) ( 1: 2, 1 10: 5, 3 100: 8, 9 101: 5, 3 11: 5, 3 110: 13, 3 111: 12, 2 ) SI 0 ( ) ( 1: 2, 1 10: 5, 3 100: 8, 9 101: 5, 3 11: 5, 3 110: 13, 3 111: 12, 2 ) ( ) ( 1: 2, 1 10: 5, 3 100: 8, 9 101: 5, 3 11: 5, 3 110: 16, 0 111: 16, 0 ) ( ) ( 100: 8, 9 ) SI 1 ( 1: 2, 1 10: 5, 3 100: 10000, 10000 101: 5, 3 11: 5, 3 110: 16, 0 111: 16, 0 ) ( 0: 10, 10 00: 10, 12 ) ( 0: 10, 10 00: 11, 11 ) SI 0 SI 0 ( 0: 10, 11 00: 10, 11 ) ( 1: 2, 1 10: 5, 3 100: 10000, 10000 101: 5, 3 11: 5, 3 110: 16, 0 111: 16, 0 )
Originally posted by Skilotto83
[snip]
La storia della lunghezza del nome si risolve on una strlen, data questa poi alloco spazio per il nome...questo nella funzione...
In main invece devo usare le realloc per forza...quando leggo da tastiera nn posso farci nulla...
Secondo...uso una strcmp per ordinare i nomi...
Ragazzi..la soluzione magari nn è la migliore...ma mi risulta comoda primo perchè uso la stessa sia per automi che per ostacoli...e questo porta ad una semplicita' mdi lettura del codice...
__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Originally posted by wingzero
http://www2.latech.edu/~box/ds/chap4.ppt
[url]
[url]http://en.wikibooks.org/wiki/Computer_Science
Arrays typically map directly to contiguous storage locations within your computers memory and are therefore the "Natural" storage structure for most higher level languages.
Simple linear arrays are the basis for most of the other data structures. Many languages do not allow you to allocate any structure except an array, everything else must be implemented on top of the array.
The exception is the linked list, that is typically implemented as individually allocated objects, but it is possible to implement a linked list within an array.
__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
ragazzi, non per farmi i fattacci vostri, ma invece di scannarvi e perdere non poco tempo per fare queste divagazioni e ricerce in giro per la rete non potete pensare al progetto?!!?
....e magari controllare l'output del programma dando in input i comandi che ho postato poco sopra!??!
Originally posted by mattcobain
ragazzi, non per farmi i fattacci vostri, ma invece di scannarvi e perdere non poco tempo per fare queste divagazioni e ricerce in giro per la rete non potete pensare al progetto?!!?
....e magari controllare l'output del programma dando in input i comandi che ho postato poco sopra!??!
__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
insisto, secondo me sbagliate nel fatto di voler memorizzare delle informazioni su tutti i punti del piano... 
malloc?
Originally posted by Novalis
insisto, secondo me sbagliate nel fatto di voler memorizzare delle informazioni su tutti i punti del piano...
__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Originally posted by superfabius
malloc?
Originally posted by superfabius
secondo me è calloc
__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Originally posted by LjL
Al massimo mi pare che qui si stia pensando di memorizzare informazioni su tutti i punti di quel rettangolo di piano compreso tra l'automa che si sta considerando e il richiamo... e anche questo secondo me è uno spreco evitabile, ma io per ora non ho trovato un modo per evitarlo che non allunghi orrendamente i tempo di esecuzione.
Originally posted by Novalis
Neanche così può funzionare.
Se hai notato l'input di esempio, una riga dice
e -10000 6 11
quindi se un automa fosse in posizione (5,4) dovresti memorizzare comunque un numero improponibile di punti.
L'unica cosa da fare (secondo me), è quella di individuare il rettangolo, e memorizzare SOLO i punti non percorribili.
Banalmente, se un punto non è "non percorribile", è percorribile.
Resta da capire come tenere questo elenco di punti... magari con una lista, ma scorrere la lista per controllare il movimento di ogni punto non è certamente il massimo.
Potrebbe venirci in aiuto un albero binario di ricerca, dove le chiavi dei nodi sono (ad esempio) i valori di ascissa delle coordinate, e come dato satellite si inseriscono i valori di ordinata.
__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
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??
__________________
"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
Originally posted by Skilotto83
+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??
__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
io sono ancora in alto mare... c'è nessuno in condizioni simili alle mie che abbia voglia di fare in questi tre giorni altrettante sessioni di brainstorming in comelico? Io domani alle 12 ho un orale lì, per cui per essere in giro sono in giro.... e domattina controllo i pm prima di uscire, giuro
Fatevi sentire 
__________________
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
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
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!
__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
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??
A me viene come ha detto il prof..controllate bene anche l'input
S' 2p2 la funzione scritta così è corretta
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".
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
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?
).__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
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?
__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
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!
è 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);
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);
__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Grazie LjL tutto chiarito...mi era sfuggita sta cosa...il che significa riguardare tutta la funzione....consegnarlo entro giovedì è la mia impresa epica..
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
Re: Tirando le somme...
(deleted - scusate di nuovo, continuo a schiacciare Quote invece che Edit)
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?
__________________
"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
Originally posted by Skilotto83
ho risolto...
[snip]
Piu' ke altro mi kiedevo..ma kome fa il prof a cointrollare se quando mando "segnale" in effetti sto usando il percorso con tortuosita' minima...visto ke lui nn vuole come out la tortuosita' nel comando segnale????
__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
boh...
kmq basta che apre il codice e si accorge se nel momento in cui stai rispondendo al comando segnale usi la funzione per il calcolo della torutosita' minima o no...
__________________
"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
kmq a me viene diverso l'out...
nei comandi posizione gli automi 10 101 11 mi da 8,9...a voi sempre 5,3...kome mai??
__________________
"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
Originally posted by Skilotto83
boh...
kmq basta che apre il codice e si accorge se nel momento in cui stai rispondendo al comando segnale usi la funzione per il calcolo della torutosita' minima o no...
__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Originally posted by Skilotto83
kmq a me viene diverso l'out...
nei comandi posizione gli automi 10 101 11 mi da 8,9...a voi sempre 5,3...kome mai??
__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
ma guarda che nel testo dice che gli automi possono sovrapporsi....
__________________
"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
Originally posted by Skilotto83
kmq a me viene diverso l'out...
nei comandi posizione gli automi 10 101 11 mi da 8,9...a voi sempre 5,3...kome mai??
Originally posted by Skilotto83
ma guarda che nel testo dice che gli automi possono sovrapporsi....
__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Originally posted by mattcobain
ti stai riferendo all'output dato dalla sequenza in ingresso che ho postato io!?
cmq gli automi 10, 101, 11 sono in (5,3) perché viene inviato un segnale di prefisso 1 dal punto (5,3) e quelli sono gli automi che si spostano
[snip]
__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Originally posted by LjL
Sì, ma se non sbaglio prima che arrivi un comando 'p' viene lanciato un segnale anche da (8,9), e suppongo che sia quel segnale che a lui fa muovere quegli automi.
Ma dato che in (8,9) *c'è* un automa, chiaramente si muoverà solo lui essendo a distanza 0 dal segnale di richiamo -- tutto questo sempre se ho riprodotto le cose con carta&penna in maniera corretta.
Forse per qualche motivo il suo programma si dimentica di considerare gli automi che hanno distanza minima nulla...?!
Originally posted by Skilotto83
boh...
kmq basta che apre il codice e si accorge se nel momento in cui stai rispondendo al comando segnale usi la funzione per il calcolo della torutosita' minima o no...
Originally posted by p2p
e secondo te si legge il codice di tutti?
io allo scorso progetto avevo fatto un paio di errori correggibili con l' aggiunta di 1 riga di codice,era uno sbaglio su un controllo di stringhe ... beh, me l ha rifiutato!se l' avesse letto probabilmente si sarebbe accorto che l' output era errato per una banalita', non credi?
__________________
"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
Originally posted by LjL
Non era questo che intendevo dire.
Intendevo dire che, essendoci un automa in (8,9), il segnale emesso in (8,9) farà chiaramente muovere solo quell'automa, dato che è a distanza zero.
__________________
"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
Il problema era quello...
solo ke è un kaso limite..siete sikuri ke va konsiderato spostamento...??
Non è il kaso si mandare una mail al prof??
io il progetto lo faccio con aguzzoli e nn con fiorentini...il mio progetto nn dice nulla a riguardo...
__________________
"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
| All times are GMT. The time now is 20:18. | Pages (4): « 1 [2] 3 4 » Show all 482 posts from this thread on one page |
Powered by: vBulletin Version 2.3.1
Copyright © Jelsoft Enterprises Limited 2000 - 2002.