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

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:D)

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.

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

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

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

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

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

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

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

Originally posted by wingzero
La trovo un pò dispendiosa come cosa solo per controllare il prefisso della stringa in pratica.

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

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

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 :D

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

Originally posted by superfabius
mi devi una birra :D

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

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

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à?:? :? :?

Originally posted by superfabius
int main (void) ?!

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.

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.

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

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.

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.

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

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.

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.

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.

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.

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.

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

Originally posted by wingzero
http://www2.latech.edu/~box/ds/chap4.ppt

[url]http://en.wikibooks.or...ructures:Arrays [/url]

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.

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!??! :D

Originally posted by Novalis
insisto, secondo me sbagliate nel fatto di voler memorizzare delle informazioni su tutti i punti del piano... :roll:

Originally posted by superfabius
malloc?

Originally posted by superfabius
secondo me è calloc

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.

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

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

Originally posted by Skilotto83
ho finito....!!!!!!:D:D:D:D:D
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??

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

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?

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?

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

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?

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

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

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]

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?

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.