 |
| |
|
 Simeon |
| [QUOTE][i]Originally posted by MaurizioL [/i]
... |
08-02-2006 18:49 |
|
 |
Simeon |
:D
Registered: Aug 2004
Posts: 984 (0.13 al dì)
Location: Milano
Corso: Informatica
Anno: IT IS OVER!
Time Online: 14 Days, 19:29:42 [...]
Status: Offline
Edit | Report | IP: Logged |
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...
|
|
08-02-2006 18:49 |
|
|
| |
|
| Diuzza |
| Ricominciamo dal principio se non vi spiace
... |
08-02-2006 19:17 |
|
|
Diuzza |
.illuminato.
Registered: Aug 2004
Posts: 169 (0.02 al dì)
Location:
Corso: Informatica
Anno: 2
Time Online: 1 Day, 8:30:45 [...]
Status: Offline
Edit | Report | IP: Logged |
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
|
|
08-02-2006 19:17 |
|
|
| |
|
| tyzer |
| [QUOTE]Guarda che NON devi assolutamente memorizza ... |
08-02-2006 20:13 |
|
|
tyzer |
.illuminato.
Registered: Sep 2004
Posts: 227 (0.03 al dì)
Location: Novara
Corso: Ticom
Anno: Laureato ^_^
Time Online: 3 Days, 18:31:58 [...]
Status: Offline
Edit | Report | IP: Logged |
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?
|
|
08-02-2006 20:13 |
|
|
| |
|
| Simeon |
| [QUOTE][i]Originally posted by Diuzza [/i]
... |
08-02-2006 20:15 |
|
|
Simeon |
:D
Registered: Aug 2004
Posts: 984 (0.13 al dì)
Location: Milano
Corso: Informatica
Anno: IT IS OVER!
Time Online: 14 Days, 19:29:42 [...]
Status: Offline
Edit | Report | IP: Logged |
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 ?  (sto diventando insicuro persino ad inizializzare le variabili)
|
|
08-02-2006 20:15 |
|
|
| |
|
| ornati |
| [QUOTE][i]Originally posted by tyzer [/i]
... |
08-02-2006 21:16 |
|
|
ornati |
.primate.
Registered: Apr 2005
Posts: 78 (0.01 al dì)
Location:
Corso: Informatica
Anno: 3
Time Online: 21:49:35 [...]
Status: Offline
Edit | Report | IP: Logged |
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
|
|
08-02-2006 21:16 |
|
|
| |
|
| Simeon |
| [QUOTE][i]Originally posted by ornati [/i]
... |
08-02-2006 21:22 |
|
|
Simeon |
:D
Registered: Aug 2004
Posts: 984 (0.13 al dì)
Location: Milano
Corso: Informatica
Anno: IT IS OVER!
Time Online: 14 Days, 19:29:42 [...]
Status: Offline
Edit | Report | IP: Logged |
Originally posted by ornati
PS: sto seramente pensando di implementare Mappe2 e venderlo al miglior offerente
Nessun sano di mente te lo comprerebbe 
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
|
|
08-02-2006 21:22 |
|
|
| |
|
| Diuzza |
| Io cmq avevo capito che il piano era di dimensione ... |
09-02-2006 07:19 |
|
|
Diuzza |
.illuminato.
Registered: Aug 2004
Posts: 169 (0.02 al dì)
Location:
Corso: Informatica
Anno: 2
Time Online: 1 Day, 8:30:45 [...]
Status: Offline
Edit | Report | IP: Logged |
Io cmq avevo capito che il piano era di dimensione m*n non infinito... mah adesso lo riguardo
|
|
09-02-2006 07:19 |
|
|
| |
|
| ornati |
| [QUOTE][i]Originally posted by Diuzza [/i]
... |
09-02-2006 07:57 |
|
|
ornati |
.primate.
Registered: Apr 2005
Posts: 78 (0.01 al dì)
Location:
Corso: Informatica
Anno: 3
Time Online: 21:49:35 [...]
Status: Offline
Edit | Report | IP: Logged |
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?
|
|
09-02-2006 07:57 |
|
|
| |
|
| Nosferatu |
| Qualcuno mi sa dire come memorizzare una stringa d ... |
09-02-2006 10:19 |
|
|
Nosferatu |
.simpatizzante.
Registered: Oct 2004
Posts: 10 (0.00 al dì)
Location:
Corso: Informatica
Anno: 1
Time Online: 12:10:30 [...]
Status: Offline
Edit | Report | IP: Logged |
Qualcuno mi sa dire come memorizzare una stringa di lunghezza arbitraria (ad esempio la specifica) senza usare un vettori di char di dimensioni esagerate.
|
|
09-02-2006 10:19 |
|
|
| |
|
| MaurizioL |
| [QUOTE][i]Originally posted by Nosferatu [/i]
... |
09-02-2006 10:28 |
|
|
MaurizioL |
.simpatizzante.
Registered: Feb 2006
Posts: 17 (0.00 al dì)
Location: Omegna
Corso: Informatica
Anno: 2
Time Online: 3:44:01: [...]
Status: Offline
Edit | Report | IP: Logged |
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
-----------------------
|
|
09-02-2006 10:28 |
|
|
| |
|
| Diuzza |
| Per la specifica io pensavo di usare semplicemente ... |
09-02-2006 10:30 |
|
|
Diuzza |
.illuminato.
Registered: Aug 2004
Posts: 169 (0.02 al dì)
Location:
Corso: Informatica
Anno: 2
Time Online: 1 Day, 8:30:45 [...]
Status: Offline
Edit | Report | IP: Logged |
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
|
|
09-02-2006 10:30 |
|
|
| |
|
| Diuzza |
| [QUOTE][i]Originally posted by ornati [/i]
... |
09-02-2006 10:37 |
|
|
Diuzza |
.illuminato.
Registered: Aug 2004
Posts: 169 (0.02 al dì)
Location:
Corso: Informatica
Anno: 2
Time Online: 1 Day, 8:30:45 [...]
Status: Offline
Edit | Report | IP: Logged |
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?
|
|
09-02-2006 10:37 |
|
|
| |
|
| MaurizioL |
| [QUOTE][i]Originally posted by Diuzza [/i]
... |
09-02-2006 10:39 |
|
|
MaurizioL |
.simpatizzante.
Registered: Feb 2006
Posts: 17 (0.00 al dì)
Location: Omegna
Corso: Informatica
Anno: 2
Time Online: 3:44:01: [...]
Status: Offline
Edit | Report | IP: Logged |
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
-----------------------
|
|
09-02-2006 10:39 |
|
|
| |
|
| ornati |
| [QUOTE][i]Originally posted by Diuzza [/i]
... |
09-02-2006 10:52 |
|
|
ornati |
.primate.
Registered: Apr 2005
Posts: 78 (0.01 al dì)
Location:
Corso: Informatica
Anno: 3
Time Online: 21:49:35 [...]
Status: Offline
Edit | Report | IP: Logged |
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) ];
|
|
09-02-2006 10:52 |
|
|
| |
|
| Nosferatu |
| Grazie dell'info MaurizioL ... |
09-02-2006 11:01 |
|
|
Nosferatu |
.simpatizzante.
Registered: Oct 2004
Posts: 10 (0.00 al dì)
Location:
Corso: Informatica
Anno: 1
Time Online: 12:10:30 [...]
Status: Offline
Edit | Report | IP: Logged |
Grazie dell'info MaurizioL
|
|
09-02-2006 11:01 |
|
|
| |
|
| All times are GMT. The time now is 02:59. |
|
|
 |
|
 |
|
|
| |
Forum Rules:
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
|
HTML code is OFF
vB code is ON
Smilies are ON
[IMG] code is ON
|
|
|
|
|
|
Simeon
