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

Pages (17): « 1 2 [3] 4 5 6 7 » ... 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 Simeon on 08-02-2006 18:49:

Originally posted by MaurizioL
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????)

Ok, grazie anche a te

In effetti come chiave si devono usare le coordinate per forza...

Posted by Diuzza on 08-02-2006 19:17:

Ricominciamo dal principio se non vi spiace

Ricevo con c m n nome i valori di ciascun punto del piano.

Ciascun punto lo metto in un albero di ricerca. Il primo punto andrà come radice, il secondo come figlio destro o sinistro a seconda della chiave data dalle sue coordinate così la ricerca avrà costo log n se n è il numero dei punti.
Ci sono?
Se poi devo modificare il valore di un punto lo ricerco attraverso l'albero.

M come fa a non essere dunque presente nel piano? Li ho inseriti tutti i punti con crea

Posted by tyzer on 08-02-2006 20:13:

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.

Domanda per Ornati: nel progetto Mappe2 si dice che con la funzione crea(m,n,nome) bisogna assegnare ad ogni punto del piano i valori come prescritto nella nota 3. Non capisco allora quello che avevi detto prima...i punti devo memorizzarli per forza...
Il Piano lo si deve rappresentare con un albero di ricerca binaria?
Oppure un albero red-black? (che è assai più incasinato credo...)

Altra domanda: le mappe in che struttura si mettono? Cioè mi spiego, una mappa la implementerei così:

code:struct Mappa{
   char *nome;
   Punto origine;
   char *specifica;
}

//Punto lo definirei così piu o meno

struct Punto{
   int x;
   int y;
   int val;
}

Ora la domanda è questa...quando continuo a creare mappe, dove le emtto? Creaiamo una lista di mappe? Oppure un albero di ricerca binaria di mappe (magari ordianto per nome della mappa...)?
Spero di aver spiegato la domanda in modo chiaro, se no mandatemi insulti

Grazie a tutti quelli che collaborano...

P.S.

.yomo. tu sei quello di Piacenza?

Posted by Simeon on 08-02-2006 20:15:

Originally posted by Diuzza
Ricominciamo dal principio se non vi spiace

Ricevo con c m n nome i valori di ciascun punto del piano.

Ciascun punto lo metto in un albero di ricerca. Il primo punto andrà come radice, il secondo come figlio destro o sinistro a seconda della chiave data dalle sue coordinate così la ricerca avrà costo log n se n è il numero dei punti.
Ci sono?
Se poi devo modificare il valore di un punto lo ricerco attraverso l'albero.

La penso come te, fino a questo punto.

M come fa a non essere dunque presente nel piano? Li ho inseriti tutti i punti con crea

Ma il piano ipotetico e' infinito, quando usi "crea" inserisci solo alcuni punti; le coordinate e valori di questi punti ti vengono forniti dal file che dai in input con crea(m,n,nome) secondo le specifiche della nota 3.

O no ? :look:

(sto diventando insicuro persino ad inizializzare le variabili)

Posted by ornati on 08-02-2006 21:16:

Originally posted by tyzer
Domanda per Ornati: nel progetto Mappe2 si dice che con la funzione crea(m,n,nome) bisogna assegnare ad ogni punto del piano i valori come prescritto nella nota 3. Non capisco allora quello che avevi detto prima...i punti devo memorizzarli per forza...
Il Piano lo si deve rappresentare con un albero di ricerca binaria?
Oppure un albero red-black? (che è assai più incasinato credo...)

Altra domanda: le mappe in che struttura si mettono? Cioè mi spiego, una mappa la implementerei così:
code:struct Mappa{
   char *nome;
   Punto origine;
   char *specifica;
}

//Punto lo definirei così piu o meno

struct Punto{
   int x;
   int y;
   int val;
}
Ora la domanda è questa...quando continuo a creare mappe, dove le emtto? Creaiamo una lista di mappe? Oppure un albero di ricerca binaria di mappe (magari ordianto per nome della mappa...)?
Spero di aver spiegato la domanda in modo chiaro, se no mandatemi insulti

Grazie a tutti quelli che collaborano...

P.S.

.yomo. tu sei quello di Piacenza?

Oh, che casino!

Ma non fai prima a scaricare il mio progetto "Mappe" (sezione Filez) e vedere come sono implementate le cose che mi chiedi? Tanto questa parte è IDENTICA a quella del vecchio progetto...

PS: sto seramente pensando di implementare Mappe2 e venderlo al miglior offerente

Posted by Simeon on 08-02-2006 21:22:

Originally posted by ornati

PS: sto seramente pensando di implementare Mappe2 e venderlo al miglior offerente

Nessun sano di mente te lo comprerebbe :asd:

Presentarsi a Fiorentini con quel codice li, magari senza averci capito niente... non conviene. Meglio capire e fare da soli.

Comunque la nota 3 è abbastanza ostica da interpretare, mon riesco a capire cosa bisogna ricavare dai valori nei file primo.txt etc.

Nel "secondo.txt" ad esempio c'e' un unico valore, che è -1.

Che ci ricavo di bello ?

Forse bisogna davvero scorrere i punti da 1,1 a m,n e assegnare i valori se l'indice risultante rientra da 1 a mn... Vabbè per oggi chiudo che son stanco di scrivere fregnacce :asd:

Posted by Diuzza on 09-02-2006 07:19:

Io cmq avevo capito che il piano era di dimensione m*n non infinito... mah adesso lo riguardo

Posted by ornati on 09-02-2006 07:57:

Originally posted by Diuzza
Io cmq avevo capito che il piano era di dimensione m*n non infinito... mah adesso lo riguardo

In effetti ho fatto un po' di confusione... parlavo del nuovo progetto pensando a quella vecchio

Cmq adesso ho letto meglio il testo e il piano è sempre "infinito".

Per quanto riguarda i valori dei punti, la relazione:
"Se a = x mod m e b = y mod n allora V al(x, y) = v[a+mb] ."

ti dice il valore di ogni punto del piano a meno che non sia stato "sovrascritto" da un comando "valore (x,y,val)".

Quindi il tutto si può implementare così:

1) i valori dei punti settati esplicitamente (con "v x y val") sono memorizzati in una apposita struttura (albero, albero bilanciato, hash table, lista... quello che preferite)

2) se serve il valore di un punto che non è stato settato esplicitamente, e quindi non si trova nella struttura, lo si ricava mediante la relazione di prima.

Ovvero:
valore = ArrayValori[ modulo(x,M) + M * modulo(y, N) ];

Facile, no?

Posted by Nosferatu on 09-02-2006 10:19:

Qualcuno mi sa dire come memorizzare una stringa di lunghezza arbitraria (ad esempio la specifica) senza usare un vettori di char di dimensioni esagerate.

Posted by MaurizioL on 09-02-2006 10:28:

Originally posted by Nosferatu
Qualcuno mi sa dire come memorizzare una stringa di lunghezza arbitraria (ad esempio la specifica) senza usare un vettori di char di dimensioni esagerate.

C'è una funzione apposta chiamata realloc;

if usi linux:
man realloc (per leggere la guida)

else if usi windows{
cerca su internet || scarica il progetto di ornati e guarda lì
}

else{
Usa il mio codice:

char* get_string(char end){
char input;
int len=0;
int mem=100;
char *string=(char*)malloc(mem*sizeof(char));
while((input=getchar())!=end){
if(len>mem-1){
mem*=2;
string=(char*)realloc(string,mem);
}
string[len++]=input;
}
string[len]=0x0;
return string;
}

}

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

Posted by Diuzza on 09-02-2006 10:30:

Per la specifica io pensavo di usare semplicemente una lista perchè non devi ricercare una lettera o cose simili, devi semplicemente scorrerla, quindi che problema c'è? Ci impiegheresti o(n) cmq perchè devi leggere ogni singolo carattere

Posted by Diuzza on 09-02-2006 10:37:

Originally posted by ornati
In effetti ho fatto un po' di confusione... parlavo del nuovo progetto pensando a quella vecchio

Cmq adesso ho letto meglio il testo e il piano è sempre "infinito".

Per quanto riguarda i valori dei punti, la relazione:
"Se a = x mod m e b = y mod n allora V al(x, y) = v[a+mb] ."

ti dice il valore di ogni punto del piano a meno che non sia stato "sovrascritto" da un comando "valore (x,y,val)".

Quindi il tutto si può implementare così:

1) i valori dei punti settati esplicitamente (con "v x y val") sono memorizzati in una apposita struttura (albero, albero bilanciato, hash table, lista... quello che preferite)

2) se serve il valore di un punto che non è stato settato esplicitamente, e quindi non si trova nella struttura, lo si ricava mediante la relazione di prima.

Ovvero:
valore = ArrayValori[ modulo(x,M) + M * modulo(y, N) ];

Facile, no?

Io pensavo di implementarlo così.
I valori li metto in un albero rb. (non i punti, badate, ma i valori)
Dopodichè quando mi passa le coordinate di un punto e mi serve il suo valore mi faccio il calcolino e lo cerco nell'albero.
In caso si ripresentassero più volte gli stessi punti e non voglio ricercare il valore nell'albero si potrebbero mettere in un hash table. Quindi, se mi viene dato un punto di cui voglio sapere il valore, prima guardo se è presente nell'hash table, se non c'è cerco nell'albero rb.
Potrebbe funzionare?

Posted by MaurizioL on 09-02-2006 10:39:

Originally posted by Diuzza
Per la specifica io pensavo di usare semplicemente una lista perchè non devi ricercare una lettera o cose simili, devi semplicemente scorrerla, quindi che problema c'è? Ci impiegheresti o(n) cmq perchè devi leggere ogni singolo carattere

Se tu rappresenti la specifica con una lista ogni nuovo carattere deve essere inserito in coda....
Quindi o ci impieghi O(n^2) per compiere O(n) operazioni di inserimento oppure utilizzi una variabile globale che punta alla fine della lista, ma le variabili globali non sono consentite!

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

Posted by ornati on 09-02-2006 10:52:

Originally posted by Diuzza
Io pensavo di implementarlo così.
I valori li metto in un albero rb. (non i punti, badate, ma i valori)
Dopodichè quando mi passa le coordinate di un punto e mi serve il suo valore mi faccio il calcolino e lo cerco nell'albero.
In caso si ripresentassero più volte gli stessi punti e non voglio ricercare il valore nell'albero si potrebbero mettere in un hash table. Quindi, se mi viene dato un punto di cui voglio sapere il valore, prima guardo se è presente nell'hash table, se non c'è cerco nell'albero rb.
Potrebbe funzionare?

Non capisco tutta questa complessità...

In altre parole: se usi la hash table non ti serve il Red-Black e vice versa.

Inoltre se usi il Red-Black (o un qualsiasi albero di ricerca) devi memorizzare in ogni nodo 2 cose:
1) la chiave (che è costituita dalle 2 coordinate x, y)
2) il valore corrispondente

Per quanto riguarda i punti non settati con "v x y val" non capisco perchè vuoi usare le liste... fai semplicemente così:

code:
int *ArrayValory = malloc(sizeof(int) * M * N);

for (i=0; i < M*N; i++) {
	fscanf(file_input, "%d", &ArrayValori[i]);
}

e poi recuperi il valore associato ad un punto (x,y) con l'espressione:

code:
valore = ArrayValori[ modulo(x,M) + M * modulo(y, N) ];

Posted by Nosferatu on 09-02-2006 11:01:

Grazie dell'info MaurizioL

All times are GMT. The time now is 10:06.

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