.dsy:it. - [PROGETTO] "Mappe 2"

Pages (17): « 1 [2] 3 4 5 6 » ... Last »
Show 150 posts per page

.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- [PROGETTO] "Mappe 2" (http://www.dsy.it/forum/showthread.php?threadid=23982)

Posted by darkAntAreS on 08-02-2006 10:55:

io sapevo che il modulo era il resto della divisione...
es.
1) -340 mod 60 = -40
-340 / 60 fa -5 (senza contare eventuali decimali) -> -5*60 = -300 -> mancano -40
2) -1 mod 4 = -1
-1 / 4 fa 0 (senza contare eventuali decimali) -> 0*4 = 0 -> manca -1
3) -7 mod 4 = -3
-7 / 4 = -1 (senza contare eventuali decimali) -> -1*4 = -4 -> manca -3

mi pare fosse spiegato da qualche parte sul libro di dscreta...

__________________
"Ash nazg durbatulûk, ash nazg gimbatul, ash nazg thrakatulûk agh burzum-ishi krimpatul"

Posted by Simeon on 08-02-2006 11:12:

Ragazzi io... non riesco a trovare una struttura dati adatta alla rappresentazione del piano. Suggerimenti? La matrice è da escludere come da testo...

Posted by Simeon on 08-02-2006 11:17:

Originally posted by Diuzza
-1 mod 4 fa -1. E' sbagliato l'esempio del prof sul modulo.
Il modulo puoi semplificarlo così:
x mod y :
X-(parteintera(x/y)*y)
nel tuo caso:
-1-(parteintera(-1/4)*4) = -1-(0*4)=-1

Anche io la sapevo così (parte intera inferiore per essere precisi). dove andremo a finire se non ci si può più fidare nemmeno del cormen

Posted by ornati on 08-02-2006 11:33:

Originally posted by Simeon
Ragazzi io... non riesco a trovare una struttura dati adatta alla rappresentazione del piano. Suggerimenti? La matrice è da escludere come da testo...

Puoi usare una hash table che mappa (x,y) --> val:
http://www.dsy.it/forum/showthread....&threadid=24001

Oppure un albero di ricerca (meglio se bilanciato).

L'alternativa peggiore è usare una lista.

Con un albero bilanciato ottieni le migliori prestazioni asintotiche nel caso peggiore, mentre in pratica le hash table sono le + efficienti (caso atteso).

Posted by YoMo on 08-02-2006 12:17:

Originally posted by darkAntAreS
io sapevo che il modulo era il resto della divisione...
es.
1) -340 mod 60 = -40
-340 / 60 fa -5 (senza contare eventuali decimali) -> -5*60 = -300 -> mancano -40
2) -1 mod 4 = -1
-1 / 4 fa 0 (senza contare eventuali decimali) -> 0*4 = 0 -> manca -1
3) -7 mod 4 = -3
-7 / 4 = -1 (senza contare eventuali decimali) -> -1*4 = -4 -> manca -3

mi pare fosse spiegato da qualche parte sul libro di dscreta...

E allora come me lo spieghi sul testo -2 mod 7 = 5 ?!?!?
Come ho scritto precedentemente, qual'è il più grande multiplo di 7 che sia minore o uguale a -2? E' -7, quindi -2 mod 7 = -2 - [(-7/7)*7] = -2 -[-1 * 7] = -2 - [-7] = -2 + 7 = 5
A quanto pare con il dividendo (-2) negativo è sbagliato dire che -2/7=0 ma bisogna prendere il più grande multiplo del divisore (7) che sia minore o uguale al dividendo (-2), cioè -7, quidni.... -2/7=-7/7=-1 con resto 5.

Il ragionamento quadra xro.....è un pò strano nn dite? Anche perchè in C printf("%d", -2 % 7) stampa -2.
Boh sinceramente spero che il prof si sia sbagliato.

Posted by Simeon on 08-02-2006 12:36:

Originally posted by ornati
Puoi usare una hash table che mappa (x,y) --> val:
http://www.dsy.it/forum/showthread....&threadid=24001

Oppure un albero di ricerca (meglio se bilanciato).

L'alternativa peggiore è usare una lista.

Con un albero bilanciato ottieni le migliori prestazioni asintotiche nel caso peggiore, mentre in pratica le hash table sono le + efficienti (caso atteso).

Mi sa che andrò per l'albero di ricerca... boh ci penserò, grazie comunque.

Con le liste mi vengono in mente robe aberranti tipo "liste di liste", o forse un'unica lista che scorre tutti i punti da 0 a m*n...

Posted by ornati on 08-02-2006 13:31:

Originally posted by Simeon
Mi sa che andrò per l'albero di ricerca... boh ci penserò, grazie comunque.

Con le liste mi vengono in mente robe aberranti tipo "liste di liste", o forse un'unica lista che scorre tutti i punti da 0 a m*n...

Guarda che NON devi assolutamente memorizzare TUTTI i punti possibili ma SOLO i punti che vengono settati esplicitamente. Tutti gli altri hanno un valore predefinito... qundi se il punto che cerchi non è nella lista (albero, hash table ...) allora sai già quanto vale.

Posted by Simeon on 08-02-2006 13:51:

Originally posted by ornati
Guarda che NON devi assolutamente memorizzare TUTTI i punti possibili ma SOLO i punti che vengono settati esplicitamente. Tutti gli altri hanno un valore predefinito... qundi se il punto che cerchi non è nella lista (albero, hash table ...) allora sai già quanto vale.

Ah allora stavo sbagliando, perche io pensavo di dover memorizzare tutte le coordinate da (1,1) a (m,n) e poi assegnare il valore di default a quelli che non erano settati esplicitamente...

Cioe, una 4x4 avrebbe costituito una lista di punti (1,1)... (4,4) ognuno con val(p) determinato (se preso dal file o settato successivamente tramite valore(x,y,z) ) o di default altrimenti.

Cercherò di ragionarci a fondo per comprendere anche queste banalità ( era piu bello il progetto di JAVA :asd:

)

Posted by ornati on 08-02-2006 13:56:

Confusione sul modulo...

Ecco una spiegazione alla faccenda del modulo:
http://en.wikipedia.org/wiki/Modulo_operation

Da notare questa parte:
"Some programming languages, such as ANSI C, don't define a result if either of n or a is negative. a modulo 0 is undefined in the majority of systems, although some do define it to be a."

Posted by ornati on 08-02-2006 14:10:

Originally posted by Simeon
Ah allora stavo sbagliando, perche io pensavo di dover memorizzare tutte le coordinate da (1,1) a (m,n) e poi assegnare il valore di default a quelli che non erano settati esplicitamente...

Cioe, una 4x4 avrebbe costituito una lista di punti (1,1)... (4,4) ognuno con val(p) determinato (se preso dal file o settato successivamente tramite valore(x,y,z) ) o di default altrimenti.

Cercherò di ragionarci a fondo per comprendere anche queste banalità ( era piu bello il progetto di JAVA )

Seguendo il tuo vecchio ragionamento, se inerisco 4 punti di coordinate:
(-2 miliardi, -2 miliardi)
(-2 miliardi, +2miliardi)
(+2 miliardi, -2miliardi)
(+2 miliardi, +2miliardi)

ho un piano di 4 miliardi x 4 miliardi di punti circa... quindi 16 miliardi di punti.

Volendo scrivere da qualche parte il valore di ognuno di questi punti (assumiamo che sia un int di 4 byte) hai bisogno di almeno 64 miliardi di byte.

Ovvero circa 60 GB di memoria... il tutto per memorizzare 4*4 = 16 byte di informazione utile.

L'inefficienza di Java deve averti contagiato... cerca di disintossicarti!

Posted by silver on 08-02-2006 15:05:

ciao,
scusate ma non ho capito bene utilizziamo l'esempio del prof:

c 4 4 primo.txt dove primo.txt --> -1 -3 2 -2 2 1 0 2 -2 3 2 -1 0 -2 1 -2
questi sono i valori dei punti da P0........P15 oppure le coordinate ?

oppure il valore dei punti si calcola come nella nota 3 ??

es della prima coppia -1 -3

Vla(x,y) = v(a+mb) ossia v vale da v0......v15 giusto ?

a= x mod m = A
b= y mod n = B

il valore del punto è ??

val(-1,-3)=v(A+4*B) ossia il valore corrispondente a ??

sono mooolto confuso

Posted by YoMo on 08-02-2006 15:17:

Originally posted by silver
ciao,
scusate ma non ho capito bene utilizziamo l'esempio del prof:

c 4 4 primo.txt dove primo.txt --> -1 -3 2 -2 2 1 0 2 -2 3 2 -1 0 -2 1 -2
questi sono i valori dei punti da P0........P15 oppure le coordinate ?

oppure il valore dei punti si calcola come nella nota 3 ??

es della prima coppia -1 -3

Vla(x,y) = v(a+mb) ossia v vale da v0......v15 giusto ?

a= x mod m = A
b= y mod n = B

il valore del punto è ??

val(-1,-3)=v(A+4*B) ossia il valore corrispondente a ??

sono mooolto confuso

Il valore del punto (x,y) si calcola così:

a = x mod m
b = y mod n
dove m ed n sono i parametri di crea(m, n, nome).

Una voltra trovati questi "resti" eseguendo l'operazione i = a+mb trovo l'indice del valore da assegnare a val(x,y), dove per indice intendo l'indice relativo a v0, v1,...., v(m*n+1) che trovi nel file nome.
Cioè devo assegnare l'i-esimo valore nel file a val(x,y).

Ditemi se sbaglio....

Posted by ornati on 08-02-2006 15:46:

Re: Confusione sul modulo...

Originally posted by ornati
Ecco una spiegazione alla faccenda del modulo:
http://en.wikipedia.org/wiki/Modulo_operation

Da notare questa parte:
"Some programming languages, such as ANSI C, don't define a result if either of n or a is negative. a modulo 0 is undefined in the majority of systems, although some do define it to be a."

Tradotto in "C":

code:
int modulo(int a, int b)
{
	int x;

	if (a < 0) {
		x = -a + b - 1;
		a += x - x % b;
		return a;
	}
	return a % b;
}

Posted by Simeon on 08-02-2006 18:07:

Meglio continuare qua....

Originally posted by MaurizioL
L'hash non serve a rappresentare un piano.
Dato che i punti che cambiano valore sono pochi puoi usare un albero per memorizzare quei punti il cui valore è stato cambiato.
Gli altri avranno un valore predefinito

Sto pensando di utilizzare un albero binario di ricerca con come chiavi le coordinate x e y e il valore come dato satellite... e' una buona idea? Non son sicuro se vada bene binario e nemmeno se utilizzare le coordinate come chiave...

E poi non ho capito questo: la funzione "valore (x,y,n)" va a porre a n il valore di un punto... questo punto si da per scontato che sia gia presente nel piano? Se non lo fosse andrebbe aggiunto all'interno dell'albero...

Posted by MaurizioL on 08-02-2006 18:39:

Originally posted by Simeon
Meglio continuare qua....

Sto pensando di utilizzare un albero binario di ricerca con come chiavi le coordinate x e y e il valore come dato satellite... e' una buona idea? Non son sicuro se vada bene binario e nemmeno se utilizzare le coordinate come chiave...

E poi non ho capito questo: la funzione "valore (x,y,n)" va a porre a n il valore di un punto... questo punto si da per scontato che sia gia presente nel piano? Se non lo fosse andrebbe aggiunto all'interno dell'albero...

La funzione v x y n pone a n il valore del punto.
Quindi devi inserire nell'albero il punto il cui valore è stato modificato.
Io ho usato un albero binario di ricerca per memorizzare i punti, le coordinate le usavo come chiave, il valore è un dato satellite.
Se non trovi un punto nell'albero significa che ha un valore "predefinito" (quello che hai inserito usando il comando "c n".
Devi usare per forza le coordinate come chiave; (oltretutto un punto è determinato univocamente dalle sue coordinate.... quale migliore chiave è possibile????)

__________________
Maurizio Lombardi
Linux 2.6.14.2
-----------------------

All times are GMT. The time now is 13:54.

Pages (17): « 1 [2] 3 4 5 6 » ... Last »
Show all 246 posts from this thread on one page