.dsy:it. - Progetto "DIE HARD"

Pages (13): « First ... « 5 6 7 8 [9] 10 11 12 13 »
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 "DIE HARD" (http://www.dsy.it/forum/showthread.php?threadid=39661)

Posted by palaz on 22-01-2010 10:57:

beh deve raggiungere esattamente k...
raggiungibile è la stessa cosa di esiste sol oche si controlla tutta la configurazione invece che un campo alla volta..

Posted by ste182 on 23-01-2010 12:23:

ragazzi non riesco a capire sta funzione:

code:
- pericolosa(a)
  Dato un vettore a = (a1 , a2 , . . . , an ) di interi positivi, dichiara “pericolosa” la configurazione 
in cui il contenitore i ha livello ai . Questo implica che questa configurazione 
non potrà più essere utilizzata nel calcolo di altre operazioni (quali ad esempio contenenti(k) o mosse(k)) 
fino a quando non sia nuovamente dichiarata come innocua con l’operazione innocua(a) descritta sotto. 
In particolare se una operazione elementare trasforma la configurazione attuale in una configurazione pericolosa,
l’operazione non deve essere eseguita, e deve essere stampato il messaggio OPERAZIONE PERICOLOSA.

e fin qui ok, poi c'è l'esempio:

code:
>w 2
(3[3],2[5])
(0[3],2[5])
(2[3],0[5])
(2[3],5[5])
>p 2 0
>w 2
(2[3],5[5])

dopo p 2 0, il comando w 2 stampa solo 2[3] 5[5].. ma scusate: la configurazione 3[3] 2[5] ad esempio può essere raggiunta facendo 0[3] 0[5] -> 0[3] 5[5] -> 3[3] 2[5] che non passa per 2[3] 0[5] !!!
non capisco

ho mandato una mail al prof e ha risposto:

code:
le configurazioni pericolose al momento di eseguire il secondo w 2
sono:
    (0[3],5[5])
    (3[3],5[5])
    (2[3],0[5])

Quindi tre delle quattro configurazioni contenenti un 2 non
sono piu' raggiungibile, mentre rimane raggiungibile,
attraverso una strada che non passa per (2[3],0[5]),
la configurazione (2[3],5[5]).

__________________
Live Fast, Die Fun

Posted by gek on 23-01-2010 16:17:

scusate qualcuno è riuscito a implementare la funzione mosse(k) in tempo accettabile? più ci penso e più mi sembra np-completo...
grazie

Posted by ste182 on 23-01-2010 18:15:

Originally posted by gek
scusate qualcuno è riuscito a implementare la funzione mosse(k) in tempo accettabile? più ci penso e più mi sembra np-completo...
grazie

np-completo?? ma no: se implementi tutto con un grafo, ogni arco avrà peso 1, quindi una visita in ampiezza ti fornisce il sottografo(albero) dei cammini minimi...

__________________
Live Fast, Die Fun

Posted by francescoo on 24-01-2010 10:53:

per ste182:

non so se hai gia risolto..
comunque ha ragione il prof..
perche prima di arrivare li tu hai gia dichiarato altre configurazioni come pericolose..che sono appunto
p 0 5
p 3 0(che pero poi togli facendo - i 3 0)
p 3 5
p 2 0

Posted by gek on 24-01-2010 11:50:

Originally posted by ste182
np-completo?? ma no: se implementi tutto con un grafo, ogni arco avrà peso 1, quindi una visita in ampiezza ti fornisce il sottografo(albero) dei cammini minimi...

cosa intendi con implementare con un grafo °?° salvare tutte le configurazioni possibili in memoria non è certo accettabile.
Illuminami plx!

Posted by palaz on 24-01-2010 12:46:

beh.. se non ti crei tutte le soluzioni non puoi fare nulla.. io mi sono creato tutte le possibili soluzioni e da li facevo i calcoli...

Posted by gek on 24-01-2010 13:25:

Originally posted by palaz
beh.. se non ti crei tutte le soluzioni non puoi fare nulla.. io mi sono creato tutte le possibili soluzioni e da li facevo i calcoli...

esatto...l'uso di memoria non è accettabile.Il problema mosse(k) è np-completo, non capisco perchè sia presente all'interno del progetto....
ma il progetto per essere valutato deve contenere tutte le funzioni accettabili per tempo e spazio e funzionanti??

Posted by palaz on 24-01-2010 13:53:

ma no.. non è cosi malato.. a me ha dato 26 in questo progetto solo perche creavo le soluzioni mano a mano che svolgevo le funzioni.. mentre lui avrebbe voluto che rimanessero sempre in memoria per non sprecare il tempo dedicato a generarle dato che son sempre quelle... è impossibile non occupare della memoria... l'importante è non occuparla a cazzo...

Posted by gek on 24-01-2010 13:59:

Originally posted by palaz
ma no.. non è cosi malato.. a me ha dato 26 in questo progetto solo perche creavo le soluzioni mano a mano che svolgevo le funzioni.. mentre lui avrebbe voluto che rimanessero sempre in memoria per non sprecare il tempo dedicato a generarle dato che son sempre quelle... è impossibile non occupare della memoria... l'importante è non occuparla a cazzo...

ah! bhè allora complimenti per il voto! mi metto subito all'opera per un bell'algoritmo non accettabile!
grazie.

Posted by palaz on 24-01-2010 14:02:

ahahh in ogni caso il prof è flessibile l'importante è che fai le cose con criterio e cerci almeno teoricamente una seconda opzione che possa essere migliore.... buon lavoro

Posted by gek on 24-01-2010 14:17:

Dato che ci sono ne approffitto pe farti un'altra domanda dato che hai già consegnato, nel file pdf cosa hai messo?
grazie

Posted by palaz on 24-01-2010 14:48:

beh ho messo tutto il codice commentato... e una veloce relazione di 4 paginette dove descrivo come prendo l'input come gestisco i comandi e molto sommariamente alcuni costi.. tipo usavo una coda e dicevo che le operazioni costano 1.... ma non me ne ha manco parlato il prof....

Posted by gek on 24-01-2010 15:01:

Originally posted by palaz
beh ho messo tutto il codice commentato... e una veloce relazione di 4 paginette dove descrivo come prendo l'input come gestisco i comandi e molto sommariamente alcuni costi.. tipo usavo una coda e dicevo che le operazioni costano 1.... ma non me ne ha manco parlato il prof....

grazie caro...

Posted by ste182 on 24-01-2010 17:27:

Originally posted by francescoo
per ste182:

non so se hai gia risolto..
comunque ha ragione il prof..
perche prima di arrivare li tu hai gia dichiarato altre configurazioni come pericolose..che sono appunto
p 0 5
p 3 0(che pero poi togli facendo - i 3 0)
p 3 5
p 2 0

argh, è vero! :oops:

__________________
Live Fast, Die Fun

All times are GMT. The time now is 15:34.

Pages (13): « First ... « 5 6 7 8 [9] 10 11 12 13 »
Show all 185 posts from this thread on one page