Originally posted by maynard80
beh quanto è differente da mappe1?

Originally posted by Simeon
Ho guardato di sfuggita il testo e mi pare identico

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

Originally posted by Diuzza
Cmq io non so se è + o - uguale a quello passato perchè non l'ho guardato e ora mi sa che non c'è più il testo :-((
Passiensa

Originally posted by Diuzza
allora la mia calcolatrice è spastica?!? A mè da -40

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

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

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

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

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

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.

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

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

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

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

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

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

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

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.

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

//Punto lo definirei così piu o meno

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

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.

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

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?

Originally posted by ornati

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

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

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.

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?

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

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?

code:

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

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

code:

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

Originally posted by MaurizioL
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;
}

}

Originally posted by Polsy
quanto sei nerd :asd:

Originally posted by Nosferatu
Una cosa ma il carattere end che gli passi come parametro, che carattere è

Originally posted by MaurizioL
Io nerd?

Leggi i sorgenti di Ornati e poi mi dici

http://www.dsy.it/forum/showthread....&threadid=24001

:-D

Originally posted by ornati
No, no... io non programmo mai a basso livello:

http://ornati.altervista.org/

;)

Originally posted by Polsy
si ma quanto te la meni :D

Originally posted by Simeon
_______________
E' come se ricoprisse il piano con tanti rettangoli adiacenti
della forma
............... [/B]

Originally posted by Diuzza
Mi chiedevo.
In crea il nome del file ha lunghezza che fisso io o può essere lungo quanto vuole. Perchè avrei dei problemini nella lettura del file. Nel senso che se non ho una lunghezza fissata non so che dimensione deve avere l'arrey che contiene la stringa

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

Originally posted by Diuzza
typedef struct nodolista{
char spec;
struct nodolista* next;
}nodo

typedef struct lista{
nodo* inizio;
nodo* fine;
}lista

typedef struct mappa{
lista* specifica;
int x,y;
char * nome;
}
no?

Originally posted by Diuzza
Ho visto il codice di prima ma creo un array char nome[100] per magari inserire solo 4 caratteri.

Originally posted by Diuzza
Ho visto il codice di prima ma creo un array char nome[100] per magari inserire solo 4 caratteri.

Originally posted by Diuzza
Mi chiedevo.
In crea il nome del file ha lunghezza che fisso io o può essere lungo quanto vuole. Perchè avrei dei problemini nella lettura del file. Nel senso che se non ho una lunghezza fissata non so che dimensione deve avere l'arrey che contiene la stringa

code:

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

char *read_token(FILE *f)
{
	char *buf;
	int size = 16;
	int len = 0;
	int c;

	buf = malloc(size);

	while ((c=getc(f)) != EOF) {
		if (!isalnum(c)) {
			if (len == 0)
				continue;
			break;
		}
		if (len+1 >= size) {
			size <<= 1;	/* size = size * 2 */
			buf = realloc(buf, size);
		}
		buf[len++] = c;
	}
	buf[len++] = '\0';
	buf = realloc(buf, len);
	return buf;
}

int main(void)
{
	char *x;
	int run = 1;
	
	while (run) {
		x = read_token(stdin);
		printf("letto token <%s>\n", x);
		if (strcmp("end", x) == 0)
			run = 0;
		free(x);
	};
	return 0;
}

Originally posted by Diuzza
Ho già risolto. Ma sarò gnucca ma ho un altro problema.

Possibile che quando cerco di accedere ad un file il mio sistema mi dice che si è verificato un errore, potrebbe esserci la perdita dei dati su cui sto lavorando... ?

Originally posted by Ari_85
Se creiamo un albero per le mappe e un albero per i punti dovremo creare due alberi separati nel senso che dovremo scrivere due volte il codice perchè ad es la f inserisci del primo albero è diversa da quella del secondo perchè lavorano su nodi diversi..Certo, ci si guadagna in tempo di calcolo...
Ciao Lomba!

Originally posted by Diuzza
ho un char* nome

faccio
int c;
FILE * valpunti;
valpunti=fopen(nome, "r");
fscanf(valpunti,"%d",&c);


magari ho fatto io qualche s....

code:

valpunti = fopen(nome, "r");
if (valpunti == NULL) {
	printf("Errore: impossibile aprire '%s'\n", nome);
	exit(1);
}

Originally posted by Dav83
in alternativa si può usare la 'fread' che legge parte del file(indicato dai parametri)...http://www.cplusplus.com/ref/cstdio/fread.html

Originally posted by Diuzza
il fatto è che la fopen mi sembra che vada anche se il file che gli passo come parametro non esiste. Non è che nn mi trova il file anche se il nome è corretto. Il file l'ho messo nella stessa directory del programmino che ho fatto, giusto?

Originally posted by Diuzza
il fatto è che la fopen mi sembra che vada anche se il file che gli passo come parametro non esiste. Non è che nn mi trova il file anche se il nome è corretto. Il file l'ho messo nella stessa directory del programmino che ho fatto, giusto?

code:

#include <assert.h>

...

file = fopen(nome ,"r");
assert (file != NULL);

Originally posted by Diuzza
il fatto è che la fopen mi sembra che vada anche se il file che gli passo come parametro non esiste. Non è che nn mi trova il file anche se il nome è corretto. Il file l'ho messo nella stessa directory del programmino che ho fatto, giusto?

Originally posted by maynard80
... quindi quale struttura può fare al caso nostro?

Originally posted by am445733
Scusate: ma qualcuno mi può spiegare come si riece ad associare ad un punto un Val negativo se: Val(x,y)=V(a+mb) ed i resti di a e b (come da definizione) non sono mai negativi?...qualcosa non torna!

Originally posted by ornati
Non è detto... guarda per esempio la mia Hash_Table, c'è una sola implementazione e viene usata per inserire cose diverse (perchè usa internamente puntatori "void*").

L'unico problema dei puntatori "void*" è che perdi il controllo sui tipi dato dal compilatore.

Originally posted by Ari_85
Già ma metti che creo una funzione che cerca un nodo all'interno di un albero. Per farlo dovrei accedere anche ai campi della struttura di cui sono composti i nodi. Se perdo il controllo sui tipi di dato posso fare ad es. ele->nome dove ele è il puntatore void a cui è stato associato un nodo? o forse dovrei vedere come la strutture viene fisicamente memorizzata e aggiungere al puntatore tot byte? In questo modo potrei risolvere il problema dei campi

code:

struct mia_struttura *m = ele;
m->nome = ...

Originally posted by marcomaria

...stavo pensando a Dijkstra per il cammino minimo con pesi per i valori dei punti....idea allo stato embrionale...da approfondire nel w-e
E' stato visto a lezione?

Originally posted by maynard80
dunque allora sono contento che la nota 3 sia ormai chiara (il file contiene semplicemente nxm dati utilizzati per riempire il piano), i punti del piano esistono chiaramente solo nella nostra testa e si concreatizzano solo se fanno parte di una (o più) mappe, se poi cambiamo valore ad un punto agiamo manualmente sul dato che esplica il valore del punto che precedentemente era stato calcolato automaticamente tramite la formulina della nota 3.

ora ci troviamo quindi con delle mappe che hanno un nome, un punto di partenza e un percorso definito dalla specifica, le mappe sono selezionate tramite il nome quindi definire una struttura unica per contenere tutti i punti è una cacchiata, meglio una struttura come insieme di mappe, e ogni mappa una struttura contenente tutti i punti della specifica.. ora è meglio creare tutti i punti di ogni mappa oppure mantenere semplicemente il punto di partenza e lavorare con le specifiche? in teoria ogni mappa è un grafo che può contenere cicli e dove ogni punto può prendere 4 direzioni, ottimizzarlo vuol dire prima di tutto eliminare i cicli, quindi quale struttura può fare al caso nostro?

Originally posted by YoMo
[B]Secondo me dei cicli te ne fotti (se no il nostro progetto include anche quello di gennaio?!?!?), data una mappa e la relativa specifica devi ricavare due cose: origine e destinazione. Questo è ciò che ti basta per calcolarti la riduzione.
Per quanto riguarda i grafi, tra src e dst si potrebbe costruire un grafo e poi utilizzare un algoritmo per trovare i cammini minimi, ma a questo punto sorge un problema: nel progetto sono i PUNTI che hanno un valore, non gli ARCHI. Soluzione: ad es. valore[arco(u,v)] = valore[punto(v)].

Originally posted by Nosferatu
Sarà una stupidata ma io non riesco proprio a permettere la lettura sulla stessa linea di interi e di stringhe, come ad esempio nel comando m qualcuno può aiutarmi?

Originally posted by Nosferatu
I miei problemi sono nel caso del comando m, quando devi permettere prima di inserire una stringa di lunghezza arbitraria, poi 2 interi e poi ancora una stringa

Originally posted by maynard80
allora io ho 2 quesiti:
1)Per il discorso dei valori alla fine come calcoliamo il modulo? nel senso che 7mod2 fa 1 e su questo non ci sono problemi, ma -7mod2 dovrebbe fare -7 ma nel nostro caso a quanto pare non possiamo avere risultati della funzione modulo negativi (chiaro visto che il risultato stesso è l'indice per trovare il valore nel file), ecco voi coe operate??

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