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:

Originally posted by xeon
Il percorso, se non viola le 3 condizioni iniziali, è permesso.

Soluzione (penso l'unica) al problema di colonia: provare tutte le configurazioni.
Partendo da un punto, si creano tutti i cammini che non violano le 3 regole.
Quando si crea un ciclo (un nodo con due collegamenti) si calcola l'energia richiesta dal cammino, e se è la minore trovata finora si memorizza il cammino come quello di costo minore.

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

marcomaria

User info:

Registered: Apr 2005
Posts: 78 (0.01 al dì)
Location:
Corso: Informatica
Anno: all over.done!
Time Online: 18:43:38 [...]
Status: Offline

Post actions:

Originally posted by Polsy

per l'ordine lessicografico invece credo che l'albero sia la soluzione migliore (soprattutto se lo si rende bilanciato)

Last edited by marcomaria on 15-04-2006 at 21:45

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 marcomaria
stavo pensando ad una tabella hash, dovrebbe essere estremamente performante per ricerca/ins/cancellazione in base al nome che sembra il caso primario;

ero al primo turno e con goldwurm non si fanno le tabelle hash, quindi non ti saprei dire...

mentre per coordinate, che e' il caso secondario, usare una semplice lista...ma queste servono per gli algoritmi e forse e' meglio avere un albero bilaciato

dipende tutto da che tipo di algoritmo usi, se scandisci i punti sempre da sx a dx (o viceversa) senza cercare una x in particolare ti conviene una lista, mentre se fai una cosa del tipo "voglio i punti compresi tra a e b" ti conviene un albero (magari a intervalli)

ps: per la funzione genera() con il coefficiente angolare del segmento creato si potrebbe definire se si intersecano pti oppure no...boh...riflessioni da tarda sera

+ semplice
fai conto di avere A in (x1,y1) e B in (x2,y2)
se trovi x=|x2-x1| e y=|y2-y1| ti accorgi che A e B non possono generare solo se sono coprimi
se invece trovi i divisori comuni trovi anche i punti in cui possono generare (con un po' di matematica in realtà basta l'mcd)

Last edited by Polsy on 15-04-2006 at 23:18

tandrea85

User info:

Registered: Sep 2004
Posts: 95 (0.01 al dì)
Location:
Corso: informatica
Anno: 1
Time Online: 18:21:48 [...]
Status: Offline

Post actions:

Originally posted by maynard80
se ti calcoli tutti i cammini il tuo sistema avrà complessità esponeniale...

miles

User info:

Registered: Aug 2005
Posts: 18 (0.00 al dì)
Location:
Corso:
Anno:
Time Online: 7:36:46 [...]
Status: Offline

Post actions:

io per genera ho usato l'equazione della retta y=mx+q calcolo m e q in base ai due micro (x1,y1), (x2,y2) poi uso l'equazione e se y è un intero allora posso generare un nuovo micro. avete invece suggerimenti per la colonia vitale perche come l'ho implementata io in alcuni casi non trova la soluzione migliore ad esempio come nell'ultimo C dell'esempio.

miles

User info:

Registered: Aug 2005
Posts: 18 (0.00 al dì)
Location:
Corso:
Anno:
Time Online: 7:36:46 [...]
Status: Offline

Post actions:

dimenticavo...........ma perchè l'output dell'ultimo stampa non è ordinato lessicograficamente???????????

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:

dunque se invece di un algo (che per questo prob è sicuramente esponenziale) usiamo un'Euristica è normale che non sempre trovi il cammino migliore ma ci vada vicino.

http://it.wikipedia.org/wiki/Proble...sso_viaggiatore

io la penso così, o siamo veloci ma non sempre esatti o siamo a complessità esagerate, io tendo per la prima. di più non so

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

miles

User info:

Registered: Aug 2005
Posts: 18 (0.00 al dì)
Location:
Corso:
Anno:
Time Online: 7:36:46 [...]
Status: Offline

Post actions:

sì ok ma se non funziona sugli input del prof il progetto non è accettato...........provare per credere.................quindi come c.zzo si implementa sto colonia esisterà una soluzione anche perchè implementare un algoritmo basato sul commesso viaggiatore è un lavoro spaventoso! che palle sto progetto!

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:

Originally posted by miles
sì ok ma se non funziona sugli input del prof il progetto non è accettato...........provare per credere.................quindi come c.zzo si implementa sto colonia esisterà una soluzione anche perchè implementare un algoritmo basato sul commesso viaggiatore è un lavoro spaventoso! che palle sto progetto!

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

mapenzi81

User info:

Registered: Feb 2005
Posts: 233 (0.03 al dì)
Location: Milano
Corso: Informatica
Anno: 3.....456789....
Time Online: 6 Days, 1:18:40 [...]
Status: Offline

Post actions:

concordo.....

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

miles

User info:

Registered: Aug 2005
Posts: 18 (0.00 al dì)
Location:
Corso:
Anno:
Time Online: 7:36:46 [...]
Status: Offline

Post actions:

invece per quanto riguarda l'output dell'ultimo censimento che non è ordinato lessico.... ho mandato una mail al prof per sentire che mi dice........domani provo a modificare il mio colonia e poi vi faccio sapere.....spero di non riprendere a imprecare visto che sono già tre anni che ho smesso!!!!!!!!!!!

mapenzi81

User info:

Registered: Feb 2005
Posts: 233 (0.03 al dì)
Location: Milano
Corso: Informatica
Anno: 3.....456789....
Time Online: 6 Days, 1:18:40 [...]
Status: Offline

Post actions:

ma no dai...nn cè bisogno di imprecare...qui cè proprio bisgno di bestemmiare!!!!

cmq al di la di cio.....

nell input del problema cè
m epsilon 0 -10

che nn corrisponde allo standard del problema....

qualcuno ha già chiesto ai prof come il programma deve "ragire" in questo caso?

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

miles

User info:

Registered: Aug 2005
Posts: 18 (0.00 al dì)
Location:
Corso:
Anno:
Time Online: 7:36:46 [...]
Status: Offline

Post actions:

penso che lì sia un errore del prof

mapenzi81

User info:

Registered: Feb 2005
Posts: 233 (0.03 al dì)
Location: Milano
Corso: Informatica
Anno: 3.....456789....
Time Online: 6 Days, 1:18:40 [...]
Status: Offline

Post actions:

correzioni in :

http://homes.dsi.unimi.it/~fiorenti/labalg05.html

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

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:

miles puoi spiegarmi come si fa a trovare m e q nell'equazione della retta passante per i 2 micro (x1,y1), (x2,y2) ... la matematica non è il mio forte