YoMo

User info:

Registered: Oct 2004
Posts: 96 (0.01 al dì)
Location: Placentia
Corso: Info triennale
Anno: laureato
Time Online: 2 Days, 0:18:13 [...]
Status: Offline

Post actions:

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)]. Altro problema: ATTENZIONE, l'algoritmo di Dijkstra non è utilizzabile in quanto calcola il cammino minimo in un grafo nel caso in cui tutti i pesi degli archi siano positivi. Nel progetto (secondo la notazione di prima) un arco può avere valori negativi. Soluzione: sul Cormen due pagine dopo Dijkstra c'è l'algoritmo di Bellman-Ford che fa al caso nostro, ma cavolo, tra pseudocodice e C ci passa un mare!!!!
Cmq se volete qualche implementazione dei grafi guardatevi l'ultima lezione di Aguzzoli, proprio le ultime slide, altrimenti provate su http://www.algoteam.dsi.unimi.it/

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?

lfn

***La Femme Nikita***

User info:

Registered: Nov 2004
Posts: 171 (0.02 al dì)
Location: Milano
Corso: TICOM
Anno: 2° anno
Time Online: 1 Day, 12:50:30 [...]
Status: Offline

Post actions:

niente lasciate stare ho risolto, non fate caso a quello che ho scritto T_T sono proprio fusa
lfn

__________________
an arrow from the sun

ornati

.primate.

User info:

Registered: Apr 2005
Posts: 78 (0.01 al dì)
Location:
Corso: Informatica
Anno: 3
Time Online: 21:49:35 [...]
Status: Offline

Post actions:

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

Nosferatu

User info:

Registered: Oct 2004
Posts: 10 (0.00 al dì)
Location:
Corso: Informatica
Anno: 1
Time Online: 12:10:30 [...]
Status: Offline

Post actions:

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?

Diuzza

.illuminato.

User info:

Registered: Aug 2004
Posts: 169 (0.02 al dì)
Location:
Corso: Informatica
Anno: 2
Time Online: 1 Day, 8:30:45 [...]
Status: Offline

Post actions:

Chissà come mai oggi ho riprovato a leggere il file s funzia.... mah

Diuzza

.illuminato.

User info:

Registered: Aug 2004
Posts: 169 (0.02 al dì)
Location:
Corso: Informatica
Anno: 2
Time Online: 1 Day, 8:30:45 [...]
Status: Offline

Post actions:

prima fai un getchat e leggi il carattere che identificherebbe l'istruzione. Poi usi uno switch per riconoscere l'istruzione ed eseguire le relative operazioni. Dopodichè (in caso di c), gai un fscanf per leggere i valori o quel che sono.
E' questo che intendevi? o ho capito male?

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?

Nosferatu

User info:

Registered: Oct 2004
Posts: 10 (0.00 al dì)
Location:
Corso: Informatica
Anno: 1
Time Online: 12:10:30 [...]
Status: Offline

Post actions:

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

Polsy

.arcimaestro.

User info:

Registered: Dec 2003
Posts: 477 (0.06 al dì)
Location:
Corso: Info phd
Anno:
Time Online: 17 Days, 17:11:50 [...]
Status: Offline

Post actions:

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

maynard80

.novellino.

User info:

Registered: Jul 2007
Posts: 3 (0.00 al dì)
Location: Milano (e non interland, tendo a precisare)
Corso: informatica
Anno: SESTO
Time Online: 12 Days, 14:28:38 [...]
Status: Offline

Post actions:

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

2)stavo pensando che alla fine ogni mappa potrebbe essere una piccola lista di adiacenze, e ad essa applicare gli algoritmi per gli shortest path, no? unica cosa come si fa a modificare Dijkstra per il caso dei pesi negativi?

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

ornati

.primate.

User info:

Registered: Apr 2005
Posts: 78 (0.01 al dì)
Location:
Corso: Informatica
Anno: 3
Time Online: 21:49:35 [...]
Status: Offline

Post actions:

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

Polsy

.arcimaestro.

User info:

Registered: Dec 2003
Posts: 477 (0.06 al dì)
Location:
Corso: Info phd
Anno:
Time Online: 17 Days, 17:11:50 [...]
Status: Offline

Post actions:

Originally posted by maynard80

2)stavo pensando che alla fine ogni mappa potrebbe essere una piccola lista di adiacenze, e ad essa applicare gli algoritmi per gli shortest path, no? unica cosa come si fa a modificare Dijkstra per il caso dei pesi negativi?

tyzer

.illuminato.

User info:

Registered: Sep 2004
Posts: 227 (0.03 al dì)
Location: Novara
Corso: Ticom
Anno: Laureato ^_^
Time Online: 3 Days, 18:31:58 [...]
Status: Offline

Post actions:

Non credo che ci sia bisogno di scomodare i grafi.

Per la riduzione, usando la programmazione dinamica, si può fare in tempo O(dx * dy). Dove dx = |src.x - dst.x| e dy = |src.y - dst.y|.

Non penso che si possa fare di meglio... nel caso generico. Poi magari si può velocizzare nel caso medio con qualche euristica, boh!

Spero proprio che non ci sia da scomodare i grafi, e concordo col tempo che hai detto, ma l mia domanda è come si può implementare questo algoritmo? Come fai con la programmazione dinamica? Col backtracking? io ho riguardato il problema del cavallo (quello sulla scacchiera che devi andare su tutte le caselle eccetera..) però li non c'era da tenere conto dei pesi dei punti come qui...se qualcuno ha idee...

Simeon

User info:

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

Post actions:

Avanzo un problema che magari per voi sarà scemo ma mi sta mandando in confusione.

Voi QUANDO invocate la funzione che calcola il valore totale di una mappa?

Nell'esempio del prof lui inizia con

c 4 4 primo.txt
m mappa1 4 3 blablabla
s mappa1
...

E stampando mappa1 viene visualizzato:

...
mappa1 4 7 1 EEESSSEENWWWWWWWSSEENNNWSSSSSWW
...

Il valore di mappa1 con quella specifica e' "1", quindi in quelle 3 istruzioni la in alto è gia stato calcolato.

Allora ho pensato :"bene, invoco la funzione di calcolo del valore della mappa quando la inserisco con m mappa1 etc...".

Poi sono andato avanti a leggere l'esempio e ho trovato sto passaggio:

...
s alfa
v -3 3 100
s alfa
...

Che in output produce

...
alfa -6 3 11 NEEEN
alfa -6 3 94 EEENN
...

E questo mi manda in crisi. Quello che facciamo noi tra le due stampe è soltanto inserire un nuovo valore. Com'è possibile che la seconda stampa abbia gia a disposizione il valore nuovo della mappa alfa? E la specifica "NEEEN" cambia in "EEENN"... ma perchè?!?!

Boh se qualcuno riesce a capire qualcosa del mio problema e mi da una risposta lo ringrazio tantissimo, può darsi che mi sfugga qualcosa di molto molto importante.



p.s Polsy ma la rappresentazione con la matrice non è inefficiente? Almeno a quanto dice il progetto si...

YoMo

User info:

Registered: Oct 2004
Posts: 96 (0.01 al dì)
Location: Placentia
Corso: Info triennale
Anno: laureato
Time Online: 2 Days, 0:18:13 [...]
Status: Offline

Post actions:

Originally posted by Simeon

...

Poi sono andato avanti a leggere l'esempio e ho trovato sto passaggio:

...
s alfa
v -3 3 100
s alfa
...

Che in output produce

...
alfa -6 3 11 NEEEN
alfa -6 3 94 EEENN
...

E questo mi manda in crisi. Quello che facciamo noi tra le due stampe è soltanto inserire un nuovo valore. Com'è possibile che la seconda stampa abbia gia a disposizione il valore nuovo della mappa alfa? E la specifica "NEEEN" cambia in "EEENN"... ma perchè?!?!

...

Simeon

User info:

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

Post actions:

Originally posted by YoMo
Se l'esempio dice che

r alfa
s alfa
v -3 3 100
s alfa

sputa fuori

alfa -6 3 11 NEEEN
alfa -6 3 94 EEENN

può significare solo una cosa: se riduco una mappa VOGLIO che quella mappa sia SEMPRE ridotta, qualsiasi cosa succeda (es. modifico il valore di un punto).
Ciò mi fa venire i brividi....

Oddio, sentiamo che dicono gli altri...

E che mi dici della prima parte invece? La funzione valore la calcoli quando fai "m mappa1 etc" oppure quando... la stampi?

p.s : ho mandato una mail al prof per chiarire un altro dubbio: "i valori che noi settiamo esplicitamente (tramite valore(x,y,n) valgono per un solo piano o per tutti quelli che creiamo?"

Se qualcuno avesse lo stesso dilemma domani dovrei ricevere la risposta, saluti