.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- [Algoritmi] Progetto "RICHIAMI" (http://www.dsy.it/forum/showthread.php?threadid=17192)
Posted by mattcobain on 18-02-2005 13:23:
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
e come output ho ottenuto questo:
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
)
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! 
Posted by LjL on 18-02-2005 13:51:
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...
Appunto, è questo che intendevo. Usando un albero non hai mai bisogno di usare la realloc() -- basta che ogni volta che leggi un carattere dall'input discendi l'albero di un nodo (a destra o a sinistra a seconda del carattere), eventualmente creando il nodo se non esiste già.
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...
Ok, ogni caso è a sé e sicuramente non c'è *un* modo ottimo per implementare il progetto... e anche se ci fosse, io non l'ho ancora trovato, quindi non posso certo criticare a priori le idee degli altri.
Quando però mi dici (ad esempio) che certe operazioni su un array le puoi fare "direttamente" (tempo costante) e invece non è vero, allora sì che posso criticare ;-)
[/QUOTE]
Per la cronaca, ricordati che la strcmp() *non* si esegue in tempo costante, ma la sua complessità dipende dalla lunghezza delle stringhe.__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Posted by LjL on 18-02-2005 14:18:
Originally posted by wingzero
http://www2.latech.edu/~box/ds/chap4.ppt
E questo direi che conferma palesemente l'URL che avevo citato io.
Un ADT è una "scatola nera" su cui puoi eseguire solo determinate operazioni definite da un'interfaccia. Di un ADT ti importa sapere *cosa* fa, e non ti deve interessare sapere *come* lo fa.
E infatti il tuo URL dice che, in un ADT, "[there is] no concern on implementation details" (slide 2).
Nella slide 3, si parla di pile e di code (che vengono classificate, giustamente, come ADT) e di array (che non vengono classificate come ADT).
Si dice che una pila è un ADT poiché è un contenitore che permette di eseguire due operazioni (e solo quelle, aggiungo io!) denominate "push" e "pop". Allo stesso modo, una pila è un ADT poiché è un contenitore che permette di eseguire "queue" e "dequeue".
E poi di nuovo di ripete, "no concern on implementation details". Che sarebbe a dire che una pila o una coda la puoi implementare usando un array, una lista, un albero o quel cavolo che ti pare (purché sia una scelta un minimo intelligente...); quello che importa sono le operazioni che puoi eseguirci sopra (push e pop, queue e dequeue), mentre *non ti deve importare* della struttura interna.
Tutto ciò è perfettamente coerente con la definizione data dal mio URL:
"A type whose internal form is hidden behind a set of access functions."
La "forma interna" è *nascosta* (e quindi può essere modificata trasparentemente - array, lista, albero...), e l'unico modo con cui si accede ai dati è tramite delle "funzioni di accesso" -- cioè operazioni come push, pop, enqueue, dequeue...
Il mio URL va avanti a dire:
"A classic example of an ADT is a stack data type for which functions might be provided to create an empty stack, to push values onto a stack and to pop values from a stack."
Ergo, una pila è un ADT. Una coda è un ADT. Un array non è un ADT. Una lista dinamica non è un ADT.
[url]
[url]http://en.wikibooks.org/wiki/Computer_Science
ata_Structures:Arrays[/url] [/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.
Bene, quindi gli array finiscono tipicamente in locazioni di memoria contigue. Questo li rende una struttura "naturale" per molti linguaggi di alto livello. Ebbene?
Non mi sembra che "naturale" sia il contrario di "astratto" -- "concreto" è il contrario di "astratto".
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.
Quindi il fatto che il BASIC non abbia i puntatori e ti costringa a far tutto cogli array dimostra che gli array sono concreti e il resto del mondo è astratto?
Tra l'altro, dov'è che gli array sono la base per *la maggior parte* delle strutture dati? Forse lo sono in quei linguaggi tipo il BASIC che ti costringono a fare in modo che lo siano 
Per il resto, io non vedo così tanti array in giro. Fammi controllare... no, sotto il letto non ce ne sono. Piuttosto vedo parecchie cose che assomigliano più o meno ad elementi di liste dinamiche (i nodi di un albero, i vertici di un grafo rappresentato in liste di adiacenza...). La prima struttura che mi viene in mente effettivamente basata sull'array è la tabella di hash.
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.
Ah, solo la linked list è un'eccezione di questo genere? Gli alberi e compagnia bella no?
Il fatto che sia possibile implementare una lista dinamica in un array, e non viceversa, è l'unico argomento che mi pare possa essere effettivamente valido per affermare che le liste sono più astratte degli array. Ci penserò.__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Posted by mattcobain on 18-02-2005 18:06:
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!??!
Posted by LjL on 18-02-2005 20:08:
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?!!?
Uh... cosa?! No, assolutamente no! 
....e magari controllare l'output del programma dando in input i comandi che ho postato poco sopra!??!
Be' prima dovrei avere uno straccio di programma che in un modo o nell'altro funzioni ;-) Comunque sì, suppongo che a questo punto mi convenga scriverne uno piuttosto a star qui a rimuginare su algoritmi che probabilmente non farei in tempo a implementare...__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Posted by Novalis on 18-02-2005 21:27:
insisto, secondo me sbagliate nel fatto di voler memorizzare delle informazioni su tutti i punti del piano... 
Posted by superfabius on 18-02-2005 21:39:
malloc?
Posted by LjL on 18-02-2005 21:50:
Originally posted by Novalis
insisto, secondo me sbagliate nel fatto di voler memorizzare delle informazioni su tutti i punti del piano...
E chi ne ha intenzione? Ovviamente non bisogna assolutamente memorizzare informazioni su tutti i punti del piano, altrimenti si crea, di fatto, un array grande almeno quanto il piano (cioè potenzialmente infinito).
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.__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Posted by superfabius on 18-02-2005 21:50:
Originally posted by superfabius
malloc?
secondo me è calloc
Posted by LjL on 18-02-2005 22:38:
Originally posted by superfabius
secondo me è calloc
Ma che cosa?!__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Posted by Novalis on 19-02-2005 02:32:
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.
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.
In questo modo, se devo muovermi da (-75, 10) a (-74,10), esamino l'albero per cercare tutti gli elementi con chiave -74, e se ce ne sono controllo che nessuno di questi abbia un valore di ordinata di 10.
Qualcuno vuole discuterne con me, oppure il mio ragionamento è folle?
Posted by LjL on 19-02-2005 16:26:
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.
Sì, questo è vero, e almeno fino a ieri era la cosa che più mi preoccupava.
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.
Questa è un'idea... solo di idee del genere me ne sono venute un bel po', ma purtroppo nessuna che funzionasse veramente (magari solo perché non sono riuscito a svilupparle fino in fondo).
Adesso ho implementato un'idea che mi pare effettivamente funzionare ed essere piuttosto efficiente... purtroppo descriverla bene vorrebbe dire spiattellare l'algoritmo dall'inizio alla fine, cosa che suppongo di non poter fare.
Posso dire questo: per ogni ostacolo, considera le quattro rette parallele a ogni lato dell'ostacolo e distanti 1 da tale lato.
Considera poi tutti i punti in cui tutte queste tue rette si intersecano.
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.
Io sto usando una struttura un tantino difficile da gestire ma che mi sembra piuttosto funzionale almeno per il mio algoritmo: una lista *quadruplamente* linkata. Ogni nodo ha due coppie di puntatori "precedente" e "successivo" rispettivamente per la direzione orizzontale e verticale.
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.
O un hash di qualche genere con chiavi le ascisse e satelliti le ordinate... sono tutte soluzioni più che valide, ma che a me non sono mai piaciute molto perché "privilegiano" arbitrariamente una direzione (orizzontale o verticale) piuttosto che l'altra.
Il fatto che a me non piaccia però non significa che non sia un modo tra i più usati per gestire le matrici sparse (sempre che in italiano si dica così), e quello che noi abbiamo - almeno dopo un'opportuna semplificazione - è proprio una matrice sparsa, o se preferisci un array sparso bidimensionale.__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Posted by Skilotto83 on 20-02-2005 19:07:
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
Posted by LjL on 20-02-2005 21:32:
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??
Direi proprio di sì.__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Posted by Jacoposki on 20-02-2005 21:58:
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
Powered by: vBulletin Version 2.3.1
Copyright © Jelsoft Enterprises Limited 2000 - 2002.
