.dsy:it. - Progetto "DIE HARD"

Pages (2): « 1 [2]
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 willyrs on 27-01-2010 21:38:

Originally posted by ste182
orientato? quindi duplichi i nodi contenenti configurazioni uguali?
in quanto ai pesi non servono, ogni arco ha peso 1, quindi il cammino minimo si trova con una visita in ampiezza che ti genera il sottografo dei cammini

No, non duplico. Metti che sono nella configurazione A e facendo un'operazione ottengo la B. Se la B non c'è già nel grafo la aggiungo aggiungendo anche l'arco da A a B, invece se c'è già aggiungo solo quest'ultimo.
Quindi risolvo la cosa creando l'albero di copertura con la visita?

__________________
Nel mondo esistono 10 tipi di persone: quelle che conoscono il linguaggio binario e quelle che non lo conoscono

Posted by francescoo on 28-01-2010 07:55:

Originally posted by ste182
sinceramente non so dirti se si può considerare un grafo in quel modo.. però credo di no perchè un grafo per definizione è un insieme di vertici collegati fra loro con archi.
mettendo tutto su un unica lista è un pò come se dicessi che il primo nodo è adiacente direttamente a tutti gli altri.. però potrebbe anche andare bene eh.. non saprei..

quindi dici di implementarlo tramite liste di adiacenza?
o come?
perchè come l'ho fatto io è una lista concatenata effettivamente..
e non riesco a capire ad es come l'ho fatta io il costo quale sarebbe?
n perchè nel caso peggiore la devo scorrere tutta?

Posted by ste182 on 28-01-2010 10:44:

Originally posted by francescoo
quindi dici di implementarlo tramite liste di adiacenza?
o come?
perchè come l'ho fatto io è una lista concatenata effettivamente..
e non riesco a capire ad es come l'ho fatta io il costo quale sarebbe?
n perchè nel caso peggiore la devo scorrere tutta?

bè il costo dipende dalle operazioni che ci fai e da come le fai.. ad esempio se devi fare una visita di tutti i nodi, le prestazioni saranno uguali sia su liste, che grafi che alberi.. perchè devi in ogni caso scorrere tutti i nodi.. se invece devi fare ricerche, allora una lista è lenta nel caso peggiore

__________________
Live Fast, Die Fun

Posted by asterix07 on 28-01-2010 21:48:

Torno un attimo sull argomento configurazioni.
Ho la configurazione di partenza memorizzata in una lista bidirezionale:

struct intlist {
struct contenitore c;
struct intlist *next, *prev;
};

(La struttura contenitore è formata da 3 campi int ovvero ID,stato,capacita);

Ora qualcuno mi puo spiegare come posso generare tutte le possibili configurazioni?

Posted by BeppeGoal on 29-01-2010 00:41:

Ragazzi, vi posto i miei dubbi notturni...
1) Comando configurazione: ho trovato un modo per trovare le 16 combinazioni possibili con 2 contenitori. L'ordine di estrazione è importante? C'è un ordine fisso in cui se li aspetta il prof?
2) nel 1' esempio a pag. 7, quando fa il comando "c 2", non mi tornano la riga 7, 9 e 10. In questo caso partendo da una situazione in cui tutti i contenitori sono pieni, come possono uscire i punti precedenti?
3) nell'istruzione "esiste" ho provato a generare tutte le possibili combinazioni partendo da 2 contenitori, ne ho trovate 16. Con n vasi quante se ne possono trovare? Pensavo, nel caso di 2 contenitori, a 2^2^2, ma mi sembra proprio un azzardo, c'è una regola per capire quante combinazioni è possibile estrarre da n contenitori?

Posted by ste182 on 29-01-2010 15:25:

Originally posted by asterix07
Torno un attimo sull argomento configurazioni.
Ho la configurazione di partenza memorizzata in una lista bidirezionale:

struct intlist {
struct contenitore c;
struct intlist *next, *prev;
};

(La struttura contenitore è formata da 3 campi int ovvero ID,stato,capacita);

Ora qualcuno mi puo spiegare come posso generare tutte le possibili configurazioni?

fai una copia della configurazione iniziale
esegui: riempi sulla copia-> se è stato riempito crei un nuovo nodo , altrimenti non fai nulla
ripristini la config iniziale e ripeti il primo passo(finchè hai provato con tutti i contenitori)
fai la stessa cosa per svuota e travasa

__________________
Live Fast, Die Fun

Posted by ste182 on 29-01-2010 15:37:

Originally posted by BeppeGoal
Ragazzi, vi posto i miei dubbi notturni...
1) Comando configurazione: ho trovato un modo per trovare le 16 combinazioni possibili con 2 contenitori. L'ordine di estrazione è importante? C'è un ordine fisso in cui se li aspetta il prof?
2) nel 1' esempio a pag. 7, quando fa il comando "c 2", non mi tornano la riga 7, 9 e 10. In questo caso partendo da una situazione in cui tutti i contenitori sono pieni, come possono uscire i punti precedenti?
3) nell'istruzione "esiste" ho provato a generare tutte le possibili combinazioni partendo da 2 contenitori, ne ho trovate 16. Con n vasi quante se ne possono trovare? Pensavo, nel caso di 2 contenitori, a 2^2^2, ma mi sembra proprio un azzardo, c'è una regola per capire quante combinazioni è possibile estrarre da n contenitori?

1) l'ordine non credo sia importante..
2) riga 7= 0[0] 2[3] 6[6]
punto di partenza= 2[2] 3[3] 6[6] voglio stampare tutte le config raggiungibili in 2 passi
passo 1 --> svuoto il bidone 2 e mi trovo in 2[2] 0[3] 6[6]
passo 2 --> travaso 1 in 2 e mi trovo con 0[0] 2[3] 6[6] ovvero la riga 7...

per trovare i precedenti, dipende come hai implementato tutto.. io ad esempio genero tutte le combinazioni e le inserisco nelle liste di adiacenza del nodo padre. così facendo mi basta eseguire visite in ampiezza e profondità oppurtunamente modificate per fare le varie funzioni.
3) a questa domanda non ti so rispondere perchè è un quesito di calcolo combinatorio(e ancora quell'esame non l'ho preparato

)
potrebbe essere come dici tu, ovvero numero_bidoni^numero operazioni ma non vorrei dire cazzate, in calcolo faccio pena

__________________
Live Fast, Die Fun

Posted by asterix07 on 29-01-2010 16:33:

@ste182

Quando nel punto 1 dici "se è stato riempito crei un nuovo nodo": il nuovo nodo lo aggiungo alla lista duplicata oppure ad una nuova lista apposita?

Posted by ste182 on 29-01-2010 19:32:

Originally posted by asterix07
@ste182

Quando nel punto 1 dici "se è stato riempito crei un nuovo nodo": il nuovo nodo lo aggiungo alla lista duplicata oppure ad una nuova lista apposita?

dipende da come implementi le cose; se fai un grafo allora i nodi generati finiranno nella lista o nella matrice di adiacenza e poi uno alla volta finiranno anche nella lista o nel vettore di vertici.
Se fai un albero allora il nodo generato sarà il figlio di quello di partenza.. ecc..

__________________
Live Fast, Die Fun

Posted by technorebel on 30-01-2010 10:57:

Ragazzi, ok il technorebel e' riuscito a farlo girare tutto e sembra funzionare senza strani segmentation fault )))), adesso mi chiedo....c'e' qualcuno che puo' dirmi come si stima in tempo di calcolo e costi da mettergli nella relazione!?!....adoro i grafi..pero'...:!!!!!

__________________
C0d3 Z3r0

Posted by loreste on 31-01-2010 06:35:

Ciao ragazzi, sto implementando il progetto, ho messo i vasi in una lista, ogni indice della lista è un record con i seguenti dati
Dimensione attuale
Dimensione massima

ora mi chiedo
1) con n vasi quante combinazioni ci sono di operazioni elementari? Come si calcola?
2) sapendo che con 2 vasi ci sono 16 combinazioni, salvo queste combinazioni in una seconda struttura, non capisco perchè voi parlate di grafi, se si implementa un grafo con le liste di adiacenza, metto nella lista le 16 combinazioni, e gli indici di queta lista a cosa puntano?

__________________
La Fede non retrocede mai!
Döma Atalanta!!!!!!!!

Posted by technorebel on 31-01-2010 11:29:

@Loreste vedo che sei di Bg pure Te! io ho realizzato un grafo, dalla matrice di tutte le combinazioni tolgo quelle che nn sono possibili, trovando i nodi del grafo, poi passi alla lista di adiacenza (vedi cormen), da li realizzi i puntatori ai nodi successivi tramite le operazioni elementari.

PS: qualcuno sulle stime di tempi di calcolo!!!??

__________________
C0d3 Z3r0

Posted by loreste on 01-02-2010 06:15:

Scusa ma non ho capito, mi spieghi come calcoli le combinazioni?
Inoltre, se ho i vasi 3 e 5, creo la seguente lista

(0[3],5[5]);
(3[3],2[5]);
(0[3],2[5]);
(2[3],0[5]);
(2[3],5[5]);
(3[3],4[5]);
....................
....................
Creata questa lista, cosa si mette nelle liste di adiacenza?

__________________
La Fede non retrocede mai!
Döma Atalanta!!!!!!!!

Posted by asterix07 on 01-02-2010 11:15:

Ragazzi io ho le seguenti strutture:

struct contnitore{
int id;
in stato;
int capacita;
}

poi ho una lista bidirezionale di contenitori che memorizza la configurazione di partenza

struct intlist {
struct contenitore c;
struct intlist *next, *prev;
};

(per intenderci intlist contiene ad es 0[3]0[5]).
Ora qualcuno è in grado di descrivermi come devo fare la struttura per memorizzare le configurazioni possibili, man mano che vengano create(grafo o lista che sia).....Grazie in anticipo

Posted by loreste on 02-02-2010 06:29:

@asterix07 tu hai la mia stessa struttura, ma guarda che intlist hai un vaso per indice, per interderci NON hai0[3]0[5] ma hai una lista fatta cosi 0[3] -> 0[5] -> nil
Detto questo hai il mio stesso problema, come si calcola le combinazioni? Si sa che con 2 vasi hai 16 combinazioni, ma con 3?
Infine io pensavo di fare una lista con le combinazioni fatta cosi
(0[3],5[5]);
(3[3],2[5]);
(0[3],2[5]);
(2[3],0[5]);
(2[3],5[5]);
(3[3],4[5]);
................

ma qui tutti parlano di grafo, e non capisco cosa mettono nelle liste di adiacenza....

__________________
La Fede non retrocede mai!
Döma Atalanta!!!!!!!!

Posted by ste182 on 02-02-2010 15:04:

nella lista di adiacenza ci vanno tutti nodi che sono raggiungibili dal nodo di partenza eseguendo tutte e 3 le operazioni elementari.
vi posto il grafo con le liste come l'ho implementato:

code:
    nodi              lista adiacenze
(0[3],0[5])      (3[3],0[5]) (0[3],5[5]) 
(3[3],0[5])      (3[3],5[5]) (0[3],0[5]) (0[3],3[5]) 
(0[3],5[5])      (3[3],5[5]) (0[3],0[5]) (3[3],2[5]) 
(3[3],5[5])      (0[3],5[5]) (3[3],0[5]) 
(0[3],3[5])      (3[3],3[5]) (0[3],5[5]) (0[3],0[5]) (3[3],0[5]) 
(3[3],2[5])      (3[3],5[5]) (0[3],2[5]) (3[3],0[5]) (0[3],5[5]) 
(3[3],3[5])      (3[3],5[5]) (0[3],3[5]) (3[3],0[5]) (1[3],5[5]) 
(0[3],2[5])      (3[3],2[5]) (0[3],5[5]) (0[3],0[5]) (2[3],0[5]) 
(1[3],5[5])      (3[3],5[5]) (0[3],5[5]) (1[3],0[5]) (3[3],3[5]) 
(2[3],0[5])      (3[3],0[5]) (2[3],5[5]) (0[3],0[5]) (0[3],2[5]) 
(1[3],0[5])      (3[3],0[5]) (1[3],5[5]) (0[3],0[5]) (0[3],1[5]) 
(2[3],5[5])      (3[3],5[5]) (0[3],5[5]) (2[3],0[5]) (3[3],4[5]) 
(0[3],1[5])      (3[3],1[5]) (0[3],5[5]) (0[3],0[5]) (1[3],0[5]) 
(3[3],4[5])      (3[3],5[5]) (0[3],4[5]) (3[3],0[5]) (2[3],5[5]) 
(3[3],1[5])      (3[3],5[5]) (0[3],1[5]) (3[3],0[5]) (0[3],4[5]) 
(0[3],4[5])      (3[3],4[5]) (0[3],5[5]) (0[3],0[5]) (3[3],1[5])

la prima colonna indica tutti i vertici del grafo, la seconda indica gli archi(le adiacenze) tra il nodo della prima colonna e i nodi della lista stessa.
ps:occhio a non generare duplicati; mettete i puntatori ai nodi nelle liste anzichè duplicare ogni nodo

__________________
Live Fast, Die Fun

Posted by -Oblivion- on 02-02-2010 15:25:

Si sa qualcosa dell'orale?

__________________
Annunci Gratis : La nuova dimensione degli annuci online - Jabbi.it

Posted by loreste on 02-02-2010 16:18:

#ste82 potresti spiegarmi come fai i seguenti passi della lista?
(0[3],0[5]) situazione inizile questo è chiaro
(3[3],0[5]) R1 prima operazione elementare
(0[3],5[5]) qua esegui S1 e R2??? sono 2 operazioni
(3[3],5[5]) qua esegui R1

non capisco se partendo da (0[3],0[5]) il successivo deve essere l'aggiunta di una sola operazione elementare, quindi non mi è chiaro come da (3[3],0[5]) arrivi a (0[3],5[5]) con una sola operazione elementare

__________________
La Fede non retrocede mai!
Döma Atalanta!!!!!!!!

Posted by ste182 on 03-02-2010 08:44:

Originally posted by loreste
#ste82 potresti spiegarmi come fai i seguenti passi della lista?
(0[3],0[5]) situazione inizile questo è chiaro
(3[3],0[5]) R1 prima operazione elementare
(0[3],5[5]) qua esegui S1 e R2??? sono 2 operazioni
(3[3],5[5]) qua esegui R1

non capisco se partendo da (0[3],0[5]) il successivo deve essere l'aggiunta di una sola operazione elementare, quindi non mi è chiaro come da (3[3],0[5]) arrivi a (0[3],5[5]) con una sola operazione elementare

la prima colonna elenca i vertici di tutto il grafo; non è posibile passare da 3[3] 0[5] a 0[3] 5[5] con una sola operazione.
le operazioni sono elencate nella seconda colonna, quindi:

da 3[3] 0[5] puoi passare a (3[3],5[5]) (0[3],0[5]) (0[3],3[5])

__________________
Live Fast, Die Fun

Posted by asterix07 on 03-02-2010 09:56:

@loreste:

Ma tu quindi continui con la stessa struttura (lista adiacenza) o la cambi con i vettori?

Posted by loreste on 03-02-2010 10:04:

ok, ho capito, cmq procedo con le liste di adiacenza. Grazie a tutti

__________________
La Fede non retrocede mai!
Döma Atalanta!!!!!!!!

Posted by BeppeGoal on 03-02-2010 11:01:

Scusate, voi come fate a leggere n valori in input nell'esecuzione di una funzione?
Ad esempio nell'esecuzione del comando "configurazione",
se devo leggere 2 valori potrei usare scanf("%d%d",&n1,n2), ma per più valori?

Posted by technorebel on 04-02-2010 19:23:

raga, ma l'orale di Aguzzoli come e'? cioe' il progetto ok, ma ti chiede la righina in particolare?!! sinceramente dopo 1047 righe ultra commentate nn vorrei che ti andasse a chiedere il pelo nell'uovo?!!!
ricordarmi cio' che ho scritto nelle vacanze di Natale....nzommmma )

...spero nn sia un'interrogazione sul C....e' uno strumento utile per risolvere un problema, pero' chi se le ricorda ora le dispense!"!!

__________________
C0d3 Z3r0

Posted by f3d386 on 06-02-2010 14:59:

ragazzi qualcuno sa spiegarmi con che idea è riuscito ad implementare la funzione configurazioni(d) ?
grazie

Posted by palaz on 06-02-2010 15:07:

ma va l'orale di aguzzoli è una vaccata.. devi spiegargli che strutture hai usato.. perche le hai usate, e se ci sono metodi per poter fare meglio...ma tutto con la teoria...la parte difficile è quella di torelli...

Posted by technorebel on 06-02-2010 17:36:

grazie Palaz!! allora sotto con la teoria!!! e speriamo di passare l'esamone!! dopo 1 mese di progetto!!

__________________
C0d3 Z3r0

Posted by f3d386 on 09-02-2010 14:55:

ragazzi una domanda...
ma se io dichiaro pericolosa una configurazione, ho capito che non deve più essere utilizzata in operazioni come contenenti o mosse...ma se dovessi raggiungerla con le operazioni elementari R S e T ?
ad esempio:
mettiamo che abbia questa situazione iniziale: 0[3] 0[5]
dichiaro pericolosa 3[3] 5[5] con:
>p 3 5
se poi faccio
>R 1
>R 2
va bene o dovrebbe stamparmi qualcosa per avvertirmi che sono in una configurazione pericolosa?

Posted by asterix07 on 09-02-2010 17:09:

DA quanto ho capito io dovrebbe dichiararla pericolosa e non farla eseguire

Posted by f3d386 on 09-02-2010 17:19:

quindi dovrebbe stamparmi "operazione pericolosa" e non eseguirla giusto?

grazie mille!

Posted by asterix07 on 09-02-2010 17:51:

Io l'ho interpretata cosi...prego

Posted by francescoo on 11-02-2010 22:33:

ciao a tutti,
finalmente ho superato algoritmi
volevo ringraziare tutti e per chi ancora lo deve sostenere vi dico che l'orale non è per niente difficile anzi..
il prof.Torelli è molto disponibile e ti fa ragionare..

in bocca al lupo..(crepi..)
ciauu

Posted by technorebel on 11-02-2010 23:50:

mi associo! un bel 24 intascato!! attenti a non sottovalutare il progetto, se lo avete fatto bene, cmq ricordatevi come funzionano precisamente tutte le strutture dati! e perche' le avete scelte, Aguzzoli s vuoli scende nei dettagli delle singole implementazioni, Torelli e' un docente magnifico! non lasciate cmq capitoli a zero, almeno una lettura fatela. Poi se nn ci arrivate, Lui e' disponibilissimo a farvi ragionare e se nn sapete a capire, e' importante e difficile questo esame.

In bocca al lupo a tutti!! adesso statistica e poi tesi!!

__________________
C0d3 Z3r0

Posted by asterix07 on 12-02-2010 15:58:

Come fareste la funzione mosse(k) avendo tutte le configurazioni salvate in un albero binario?

Posted by andrekiba on 01-03-2010 21:27:

ciao, fai una BFS (ricerca in ampiezza) a partire dalla sorgente e ogni volta che scopri un nuovo nodo salva da qualche parte il nodo che l'ha scoperto per primo...in poche parole definisci il padre. Alla fine della bfs trovi la configurazione di livello k ideale e tramite una semplice funzione ricorsiva stampi i padri...di fatto la sequenza più corta di nodi che ha portato a scoprirla.

Posted by BeppeGoal on 17-05-2010 14:46:

Scusate, qualcuno che ha passato l'esame del progetto Die Hard, potrebbe postarlo nell'area filez?
Grazie a tutti!

All times are GMT. The time now is 01:04.

Pages (2): « 1 [2]
Show all 185 posts from this thread on one page