.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 ste182 on 22-12-2009 15:17:

Progetto "DIE HARD"

Ciao ragazzi!
è uscito, come avrete notato, il testo del progetto "DIE HARD".
Sto iniziando a ragionarci sopra e sembra abbastanza fattibile, no?
Il mio dubbio è sul tipo di struttura adeguata da utilizzare; sicuramente l'operazione più frequente sarà la ricerca(quindi ho escluso le liste).
Sono indeciso se utilizzare hash table o alberi rb. Le prime hanno complessità costante nel caso migliore ma dipendono da molti fattori nel caso medio/peggiore(fattore di carico, numero degli elementi, grandeza tabella..).
Gli alberi rb invece hanno tempo di ricerca pari a O(log(n)).
voi che ne dite? che strutture pensate di utilizzare?

ps: è fattibile secondo voi una cosa del tipo: utilizzare hash con alberi rb per risolvere le collisioni?

__________________
Live Fast, Die Fun

Posted by f3d386 on 22-12-2009 16:43:

guarda io sto pensando di utilizzare gli alberi rb come struttura principale...
non sono però riuscito ancora a individuare la struttura adatta per quanto riguarda le combinazioni, cioè tutti i passaggi per passare da una configurazione a ad una configurazione b.
Voi che pensate di fare?

Posted by ste182 on 22-12-2009 16:49:

eh, bella domanda...

__________________
Live Fast, Die Fun

Posted by arfish on 23-12-2009 14:41:

Ragazzi ma come funziona l'operazione raggiungibile??

Posted by f3d386 on 23-12-2009 21:45:

eh...proprio lì sta il casino.
In teoria ti dice se è possibile passare da una configurazione A ad una B attraverso una serie di operazioni elementari (riempi, svuota, travasa).
Ad esempio se la mia configurazione A è 0[3] 0[5] chiedo al programma se è raggiungibile una configurazione B ad esempio 0[3] 4[5]...
in questo modo in teoria:

r 0 4

e il programma dovrebbe restituirmi SI in quanto facendo questi passaggi:

1. riempire il contenitore da 5 galloni: (0[3],5[5]);
2. travasare il contenitore da 5 in quello da 3: (3[3],2[5]);
3. svuotare il contenitore da 3: (0[3],2[5]);
4. travasare il contenitore da 5 in quello da 3: (2[3],0[5]);
5. riempire il contenitore da 5: (2[3],5[5]);
6. travasare il contenitore da 5 in quello da 3: (3[3],4[5]);
7. svuotare il contenitore da 3: (0[3] 4[5])

ottengo proprio la configurazione dei livelli richiesta in input...

il problema è: che struttura usare? io sto pensando a un grafo ma ho qualche problema a far tornare il tutto...

idee???

Posted by technorebel on 23-12-2009 22:26:

io voterei per un albero di ricerca rb...come prima idea...ma ben vengano altre...

__________________
C0d3 Z3r0

Posted by f3d386 on 23-12-2009 22:37:

si credo che per gestire l'input vada bene...ma il raggiungibile non credo sia implementabile con un albero rosso nero...o almeno non ne sono tanto sicuro...

Posted by arfish on 24-12-2009 09:42:

f3d386 dopo aver letto il tuo post stavo pensando anch'io a un grafo.
Magri popolarlo con i risultati di tutte le combinazioni fino a raggiungere la soluzione... non credo sia una soluzione decente...

Posted by f3d386 on 24-12-2009 11:17:

oltre a non essere decente presenta pure un problema...le operazioni riempi e svuota hanno condizioni ke evitano il loop, ossia quando un contenitore è pieno l'operazione riempi si blocca e idem per l'operazione svuota se un contenitore è vuoto. L'operazione travasa invece è previsto si blocchi se il contenitore sorgente è vuoto o se il contenitore destinazione è pieno, ma cosa sucede se ad esempio ho una tanica da 3 e una da 5 riempio quella da 3 e poi continuo a travasare quella quantità d'acqua tra i due vasi???si crea un loop e l'operazione travasa continuerà a generare operazioni possibili...è un casino!volevo scrivere al prof di questo problema ma credo che non mi risponderebbe comunque fino al 7 di gennaio...

Posted by arfish on 24-12-2009 11:42:

pensavo di risolvere il problema del calcolo dei "percorsi" già effettuati inserendo i risultati in un albero, e cercare se sono stati già calcolati o meno, ma il tutto mi sembra di un macchinoso...

Posted by f3d386 on 25-12-2009 23:02:

ragazzi scusate...prima ancora di arrivare al punto cruciale mi sono fermato sul problema dell'input, nel caso dell'inserimento (es. N 3 4 5)
cioè lui dice cito testualmente:
"
- crea contenitori(c)
Dato un vettore c = (c1 , c2 , . . . , cn ) di interi positivi, inizializza una sequenza di n contenitori
inizialmente vuoti aventi capacit`a c1 , c2 , . . . , cn . Ad esempio, crea contenitori(2, 3, 6) inizializzerà la conﬁgurazione (0[2],0[3],0[6]). Se esiste già una sequenza di contenitori, la cancella e ne crea una nuova. "
ma questo significa che obbligatoriamente l'input dovrà essere inserito in un vettore?
e poi io per il momento non sto usando un vettore ma per far capire al compilatore che la seuquenza di interi di input è finita, come faccio? avevo pensato che l'utente possa far terminare la sequenza inserendo il valore 0 (dato ke non è concepibile un contenitore di capacità 0)...ma il prof non dice nulla in merito nella scheda del progetto...dite che posso fare così o sono completamente fuori strada?

Posted by f3d386 on 25-12-2009 23:29:

ho risolto!!!
la soluzione ce l'avevo sotto gli occhi ma data l'ora non me ne rendevo conto XD XD XD

Posted by f3d386 on 26-12-2009 10:34:

ragazzi ma nessuno ha idea della struttura da usare per implementare le funzioni esiste raggiungibile e configurazioni ???
io mi sto dannando cercando di capire quale può essere!!! :evil:
help meeeeeeeeee!!!!!!!!!!!

Posted by Deckard on 26-12-2009 11:08:

Originally posted by f3d386
ragazzi ma nessuno ha idea della struttura da usare per implementare le funzioni esiste raggiungibile e configurazioni ???
io mi sto dannando cercando di capire quale può essere!!!
help meeeeeeeeee!!!!!!!!!!!

Ma è sicuramente un grafo. Le varie operazioni come "raggiungibili" e "configurazioni" sono delle semplici visite per ampiezza e/o profondità opportunamente modificate.
Il problema è capire come rappresentarlo questo grafo: tramite vettore di liste di adiacenza calcolando all'inizio tutti i possibili lati? È la soluzione più semplice ma molto inefficiente poiché lo spazio occupato aumenta in maniera esponenziale rispetto al numero dei contenitori.
Le altre possibilità che mi sono venute in mente ho paura siano invece un po' troppo complesse da implementare.

__________________
And all those moments will be lost in time, like tears in rain...

Posted by pirlo21 on 26-12-2009 12:58:

secondo me bisogna decifrare bene questo....
- raggiungibile(a)
Dato un vettore a = (a1; a2; : : : ; an) di interi positivi, stampa SI' oppure NO a seconda che dalla
con¯gurazione attuale sia possibile raggiungere una con¯gurazione in cui, per ogni i 2 f1; 2; : : : ; ng,
il contenitore i ha livello ai.

Perchè non mi sembra che sia lo stesso significato spiegato all'inizio del testo, così come la storia delle bombe assume significato solo nelle versioni successive del programma, potrebbe essere così anche per raggiungibile

Posted by palaz on 26-12-2009 15:43:

qualcuno è gia riuscito a implementare esiste??
è un vero macello!!!!

Posted by massimo1984 on 26-12-2009 16:13:

sei in linea?

Posted by f3d386 on 26-12-2009 16:13:

io x il momento mi sono fermato alle funzioni crea,riempi, vuota travasa ed esci...anch'io sono convintissimo che sia un grafo e anche a me non piace la soluzione basata sulle liste di adiacenza...possibile che non esista un modo più efficiente di implementare la struttura?
Inoltre, chiedo, il problema che avevo scritto qualche post fa sul fatto che se continuo a travasare la stessa quantità tra 2 contenitori la struttura cresce all'infinito come lo si risolve?

Posted by f3d386 on 26-12-2009 16:16:

@Deckard :

Come fai a calcolare all'inizio tutti i possibili lati del grafo?

Posted by massimo1984 on 26-12-2009 16:16:

palaz ci sei ?? (mandami una mail: massimo84@fastwebnet.it) Credo che possiamo darci una mano.

Posted by massimo1984 on 26-12-2009 16:18:

raga qua io credo di avere trovato qualkosa ma ho bisogno di aiuto..

Posted by massimo1984 on 26-12-2009 16:19:

suggerimento: www.inzonatre.altervista.org (incontriamoci nella sezione chat di questo sito cazzutissimo che avevo creato io tempo fa per discutere in tempi brevi.. Grazie)

Posted by palaz on 26-12-2009 16:25:

eccomi...

Posted by palaz on 26-12-2009 16:26:

io per ora ho usato un albero rb.. tanto la visita in ampiezza si può fare lo stesso

Posted by palaz on 26-12-2009 16:31:

a prima vista un grafo mi sembra un po dispersivo.. nel senso che lo fermi solo se trovi altrimenti vai avanti continuamente....

Posted by f3d386 on 27-12-2009 10:13:

io più che altro vorrei intanto capire come generare tutte le possibili configurazioni usando le tre operazioni elementari....per sapere su un input di n elementi quante ne genera x avere un'idea...

Posted by palaz on 27-12-2009 15:37:

prova a guardare questo schema.. a me mi ha aiutato a capire come si possono trovare le soluzioni..me lo ha passato massimo....
e in effetti è un grafo...

Posted by f3d386 on 27-12-2009 16:03:

si vedo...le configurazioni nei vertici devono essere tutte quelle possibili e gli archi le operazioni elementari....ma come fai a calcolare tt le combinazioni possibili?è lì ke m'impianto...ancora prima dell'implementazione vorrei capire la logica che ci sta dietro...

Posted by palaz on 27-12-2009 16:05:

eh tipo io sto provando a fare una funzione che calcoli per ogni bidone lo svuotamento... se fattibile crea la nuova configurazione e la attacca al nodo precedente....se ne trova una seconda la attacca come secondo next...e cosi via per tutte e tre le operazioni.. ma anche io sto solo provando a mettere giu qualcosa...

Posted by pirlo21 on 28-12-2009 09:00:

diciamo che trovare tutte le combinazioni è un problema ma è un problema fattibile... il vero problema è la funzione ESISTE perchè ha bisogno di calcolare infinite combinazioni in quanto non esiste un numero n fissato di operazioni elementari dopo il quale fermarsi...

Posted by middu on 28-12-2009 13:55:

chi vuole scambiare idee segretariousi@live.it sono presente su msn

Posted by middu on 28-12-2009 14:20:

a me viene in mente una struttura di grafo, dati i concetti di ragggiungibilità

Posted by arfish on 28-12-2009 16:02:

Credo che utilizzare un grafo sia necessario, il discorso è come lo riempio ci metto tutte le possibili e immaginabili combinazioni? Oppure esiste un'altra maniera?

Posted by middu on 28-12-2009 18:15:

ma penso che per iniziare dobbiamo creare una struct per rappresentare un contenitori

Posted by middu on 28-12-2009 18:19:

penso di si! in quanto ad esempio se devi creare n contenitori iniziali bisogna memorizzarli tutti nella struttura di grafo. Io avrei pensato di rappresentare il grafo mediante liste di adiacenza, ma ripeto bisogna realizzare il contenitore come un nodo di tale grafo. Questo lo si fa tramite una struct.

Posted by -Oblivion- on 31-12-2009 11:48:

Scusatemi la domanda forse banale, ma cosa significa questo nelle specifiche:

Il programma deve leggere dallo standard input (stdin) una sequenza di righe (separate da \n), ciascuna
delle quali etc.. etc..

I vari elementi sulla riga sono separati da uno o piµu spazi. Quando una riga µe letta, viene eseguital'operazione associata; le operazioni di stampa sono effettuate sullo standard output (stdout), e ognioperazione deve iniziare su una nuova riga.

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

Posted by -Oblivion- on 31-12-2009 12:47:

PS. per la ricerca delle varie combinazioni in n passi e la ricerca di una determinata combinazione, io stavo pensando di applicare Dijkstra su liste di adiacenza.
Il loop si evita appunto con dijkstra.

Questa è la mia primissima idea ponderata in 5 minuti dopo aver letto il progetto, quindi con buona probabilità è una minchiata, in questo caso sarei immensamente felice se me lo diceste XD

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

Posted by delleroby on 02-01-2010 21:14:

Ciao a tutti,
ma secondo voi l'input deve avvenire da prompt dei comandi o da file di testo?

Grazie mille per la risposta!

Posted by darkshadow on 02-01-2010 23:53:

è indifferente perchè basta fare il redirect dello stdin su file o lasciarlo di default alla tastiera

__________________
by Ð@rk§h@ÐØw

Posted by delleroby on 03-01-2010 02:34:

Si sò che non dovrebbe essere difficile.
Ma il prof come lo vuole? Lettura da file o inserimento da tastiera?

Scusate se ripresento il dubbio.

E grazie ancora.

Posted by darkshadow on 03-01-2010 12:26:

forse non hai capito, il fatto che gli passi l'input da file o da tastiera è indifferente xte. le funzioni di I/O (es. scanf, getchar, ecc) sono sempre le stesse indipendentemente da dove prendi l'input.

spero di essere stato + chiaro questa volta.

__________________
by Ð@rk§h@ÐØw

Posted by iDarbert on 04-01-2010 11:38:

Originally posted by delleroby
Si sò che non dovrebbe essere difficile.
Ma il prof come lo vuole? Lettura da file o inserimento da tastiera?

Scusate se ripresento il dubbio.

E grazie ancora.

Da tastiera

Posted by f3d386 on 04-01-2010 11:39:

qualcuno è riuscito ad implementare almeno uan delle funzioni esiste raggiungibile configurazioni?

Posted by iDarbert on 04-01-2010 12:08:

Io sono ancora bloccato all'implementazione dei grafi, non è che qualcuno ha ancora gli esercizi del laboratorio?

Posted by palaz on 04-01-2010 13:13:

anche io sono bloccato.. penso di aver trovato l'algoritmo adatto ma non riesco a metterlo giu funzionante e mi va in loop!!!

Posted by pirlo21 on 04-01-2010 18:19:

scusate una domanda molto stupida, ma a me sembra che di stupidate in questi progettini ci sia ben poco...
sono giorni che sto impazzendo sull'inserimento...il professore vuole che si usi scanf o getchar, ma com'è possibile acquisire un numero non noto di parametri con queste funzioni????? Ho provato con scanf ad acquisire una stringa (per poi spezzarla con strtok) ma mi da enormi problemi, cosa che non fa se uso la gets()...

Posted by palaz on 04-01-2010 18:37:

tu leggi il comando con getchar e i numeri li leggi successivamente con scanf assicurandoti di non trovare uno spazio allora salti la lettura...

Posted by palaz on 04-01-2010 18:39:

tipo questo puo essere l'while di lettura che devi usare per leggere tutta la riga di comando dell'inserimento dei bidoni
while((c=getchar())!='\n')
{
effettuare inserimento valore nell'apposito campo del bidone
}

Posted by francescoo on 05-01-2010 00:12:

ciao a tutti,
io ho fatto inserire una sequenza di caratteri, a seconda del primo carattere immesso,salvo ,ad esempio per inserimento, le capienze nel vettore e poi con queste capienze dovrei creare l'albero dove per ogni nodo definirei i seguenti dati:
num.di cont (kiave)
capienza
qnt litri ha all'interno
ke ne dite?
ke alberi usereste?rb?
aspetto grazie mille

Posted by palaz on 05-01-2010 11:14:

io non ho usato gli alberi per contenere le informazioni iniziali perche gli alberi sono molto utili nel caso d continue ricerce... in questo problema si devono generare delle soluzioni.. anzi tutte le possibili soluzioni.... e le operazioni di svuota riempi e travasa funzionano tramite indice...

Posted by francescoo on 05-01-2010 11:25:

e quindi palaz tu per questo progetto non usi alberi?e cosa usi le liste?

Posted by palaz on 05-01-2010 11:57:

no beh.. uso i grafi... o cmq una implementazione simile ai grafi..
alla fin fine ho notato che è meglio per generare le combinazioni possibili

Posted by f3d386 on 05-01-2010 14:25:

@palaz

scusami ma tu ke ci metti nel nodo di un grafo? cioè costruisci un nodo x ogni configurazione possibile o ad esempio crei un nodo per tt le combinazioni possibili da un nodo precedente usando la funzione "riempi", uno x quelle trovate usando "svuota" ecc ecc ?
xchè io al momento sono molto in crisi su questo...cioè penso di aver trovato un metodo per generare tutte le possibili combinazioni (ho ancora qualche prob coi loop) ma dopo non so come utilizzare i risultati in un grafo...non so se mi spiego...

Posted by technorebel on 05-01-2010 19:14:

io sto piacevolmente notando quanto sia utile il sito algoteam. Proprio utile.

__________________
C0d3 Z3r0

Posted by palaz on 05-01-2010 19:49:

io in u nodo ci metto una configurazione.. se no sinceramente non saprei come fare...

Posted by francescoo on 05-01-2010 22:24:

anche io pensavo una configurazione per ogni nodo...
e technorebel tu da algoteam quale implementazione di grafo stai utilizzando?

Posted by francescoo on 05-01-2010 23:09:

ragazzi sto andando in una confusione pazzesca e manca pochissimo tempo...
allora inzialmente pensavo di usare alberi rb e in ogni nodo
rappresentavo un contenitore con relativa capacità e litri contenuti..ma come mi avete fatto notare per questo problema gli alberi non sono cosi indicati..
quindi userei grafi..ma quindi per salvare in ogni nodo la configurazione attuale come faccio?
in ogni nodo salvo un vettore contenente i litri che ha ogni contenitore?
vi prego di spiegarmi come usare i grafi per questo probelma xke sono davvero in crisi..
grazie

Posted by f3d386 on 06-01-2010 00:52:

io sono nella tua stessa situazione francescoo...sono partito con una struttura ad albero rb x i contenitori ma adesso devo riscrivere tt daccapo per implementare una struttura basata sui grafi...il problema poi è cosa metterci nel nodo e soprattutto come implementare la funzione che calcoli tt le combinazioni possibili...sono abbastanza in crisi anche xchè sono 3 anni ke tento di dare sto esame...è uno degli ultimi ma anche uno dei peggiori...

Posted by ste182 on 06-01-2010 10:50:

ciao ragazzi..
io per crea_contenitori, riempi, svuota e travasa ho usato un semplice array dinamico.
ora per le altre funzioni pensavo di usare un grafo con liste di adiacenza; ma non ne sono molto convinto perchè ,per trovare una determinata configurazione, dobbiamo scorrere tutta la lista.. voi che ne dite?

__________________
Live Fast, Die Fun

Posted by francescoo on 06-01-2010 12:34:

e quindi ste182 tu ogni volta che ti rikiama la funzione esiste,raggiungibile,configurazioni allochi un grafo e lo deallochi alla fine della funzione??

Posted by technorebel on 06-01-2010 17:24:

@ francescoo
Sto scartabellando tra i vari grafi, studiare le parti di codice per adattare il progetto.

__________________
C0d3 Z3r0

Posted by francescoo on 06-01-2010 19:02:

ok..ma per ogni nodo del grafo tu cosa memorizzi?e come?è quello che non riesco a capire..
come fai a salvare tutte le capacità in un nodo?in ogni nodo salvi un vettore?

Posted by ste182 on 06-01-2010 20:02:

Originally posted by francescoo
e quindi ste182 tu ogni volta che ti rikiama la funzione esiste,raggiungibile,configurazioni allochi un grafo e lo deallochi alla fine della funzione??

l'idea è quella.. ora mi tocca metterla in pratica

__________________
Live Fast, Die Fun

Posted by f3d386 on 06-01-2010 21:34:

@francescoo

stesso problema...come fai a salvare in un nodo tt le configurazioni?
ankio all'inizio ero partito con l'idea degli alberi rb ma poi sono ricorso agli array dinamici...ho ancora qualche problema a volte di overflow ma almeno quella parte è quasi completa...ma il grafo è veramente un casino!!!

Posted by f3d386 on 07-01-2010 11:55:

ragazzi io da adesso fino alle 1730 circa sono qui in comelico...c'è qlkun'altro da queste parti ?
così magari si discute insieme del progetto...

Posted by technorebel on 07-01-2010 12:44:

ogni nodo misura il vettore dei contenitori. Derivanti da matrici di adiacenza.
poi ti calcoli per ogni operazione quanti nodi vengono generati.
Prova!!

__________________
C0d3 Z3r0

Posted by ste182 on 07-01-2010 14:05:

ragazzi ma voi che struttura usate per la funzione esiste?? grafi o alberi??

__________________
Live Fast, Die Fun

Posted by asterix07 on 07-01-2010 17:59:

!-Chiarimento:
Nel progetto è scritto:"Denotiamo con un vettore (a1,a2...an) di interi la configurazione dei livelli d'acqua nei contenitori..."

Ma se si crea una struttura del tipo

struct contenitore{
int capacità;
int stato;
}

non dovrebbe servire un array perche tengo traccia della configurazione mediante la variabile stato di ogni contenitore.
Inoltre anche le funzioni del tipo riempi travasa ecc... andrebbero ad agire su questa variabile.
Ora siccome mi sembra una soluzione scontata, quali sono le controindicazioni?

Posted by iDarbert on 07-01-2010 18:05:

Originally posted by asterix07
!-Chiarimento:
Nel progetto è scritto:"Denotiamo con un vettore (a1,a2...an) di interi la configurazione dei livelli d'acqua nei contenitori..."

Ma se si crea una struttura del tipo

struct contenitore{
int capacità;
int stato;
}

non dovrebbe servire un array perche tengo traccia della configurazione mediante la variabile stato di ogni contenitore.
Inoltre anche le funzioni del tipo riempi travasa ecc... andrebbero ad agire su questa variabile.
Ora siccome mi sembra una soluzione scontata, quali sono le controindicazioni?

Sì, ma ogni configurazione dovrà immagazzinare lo stato di ogni singolo contenitore. È lì che serve l'array.

Certo c'è da chiedersi se è il caso di creare una struct contenitore quando basterebbero magari due array, uno che indica le capacità in ordine e un altro che indica i volumi effettivamente contenuti.
Anche se questo complicherebbe un po' le operazioni penso, obbligando a ripescare l'array delle capacità anziché leggendo semplici proprietà della struct.

Posted by ste182 on 09-01-2010 08:55:

sono riuscito a generare tutte le possibili combinazioni e inserirle nel grafo(implementato tramite liste di adiacenza). ora mi chiedo: per la funzione "esiste" uso una visita in ampiezza o profondità??

inserendo N 3 5 ottengo:

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

come vedete, i nodi sono 16(tutte le possibili combinazioni usando riempi, svuota e travasa).
ora per la esiste mi conviene visitare in ampiezza o profondità?? che casino

__________________
Live Fast, Die Fun

Posted by f3d386 on 09-01-2010 10:24:

@ste182

cavolo ma come hai fatto????
io sto impazzendo sulla funzione che genera tt le possibili combinazioni...
al di là dell'inserimento nel grafo ke poi è il passo successivo, come fai a calcolare tt le combinazioni possibili???

Posted by ste182 on 09-01-2010 10:39:

Originally posted by f3d386
@ste182

cavolo ma come hai fatto????
io sto impazzendo sulla funzione che genera tt le possibili combinazioni...
al di là dell'inserimento nel grafo ke poi è il passo successivo, come fai a calcolare tt le combinazioni possibili???

1 parti dalla configurazione attuale, ne fai una copia
2 usi la copia per eseguire riempi svuota e travasa per ogni bidone, salvando i nuovi nodi generati e mettendoli in una coda(devi controllare che non ci sia già in coda)
3 estrai un elemento dalla coda e lo fai diventare la configurazione attuale
4 ripeti il punto 2 finchè ci sono elementi in coda

ps: al punto 3 estrai un nodo dalla coda, quindi questo non esisterà più. può però succedere che si rigeneri nelle prossime operazioni, quindi prima di rimetterlo in coda(creando così un loop) devi controllare anche che non esista tra i nodi già generati

__________________
Live Fast, Die Fun

Posted by f3d386 on 09-01-2010 11:08:

grazie mille!
solo una cosa non ho capito...qui dici:
"ps: al punto 3 estrai un nodo dalla coda, quindi questo non esisterà più. può però succedere che si rigeneri nelle prossime operazioni, quindi prima di rimetterlo in coda(creando così un loop) devi controllare anche che non esista tra i nodi già generati"

cioè?
devo controllare che non sia nella coda ma nemmeno nei nodi generati?e l'elenco dei nodi già generati dove lo salvi?in una lista?

Posted by ste182 on 09-01-2010 12:49:

esatto.. una lista o una coda vanno bene

__________________
Live Fast, Die Fun

Posted by francescoo on 09-01-2010 15:40:

ciao ste 182..
io ho avuto la tua stessa idea solo che ho un blocco e non riesco a implementarlo..e una volta fatto saprei come finire il tutt..ti vorrei kiederti una cosa..hai msn?mi daresti il tuo contatto?

Posted by francescoo on 09-01-2010 16:50:

c'è qlcn???
io l'ho pensato nelllo stesso modo di ste82..pero ho un problema:
faccio come ha detto lui al primo punto e cioè mi copio la lista che contiene configurazione attuale,dopo di che con questa copia dovrei cominciare a fare le varie operazioni di riempi,svuota e travasa per trovare le possibili configurazioni;
ora il mio problema quindi è:
prendo la lista(che è una copia di quella di partenza)
eseguo riempi, se riempi si puo fare io modifico la lista su cui stavo lavorando..
capite?cosi facendo io perdo la configurazione che avevo prima..

Posted by palaz on 09-01-2010 16:54:

beh crea un nuovo nodo che coniene la configurazione allora..

Posted by francescoo on 09-01-2010 17:06:

quindi ogni volta creo una copia della configurazione(chiamiamo la lista della conf l_conf),
faccio puntare la copia dalla lista configurazione(l_conf) e quindi sulla copia eseguo l'operazione?

Posted by ste182 on 10-01-2010 00:11:

la configurazione iniziale è una array o un nodo contenente l'array, giusto?
quindi mettiamo che ho una funzione copia(sorgente, destinazione)
...facciamo

code:
copia(attuale,copia);  //faccio una copia
for(i=0;i<dim;i++){
  if(riempi(copia,i){
    //inserisci nella coda 
    //inserisci nel grafo
  }
copia(attuale,copia);  //ripristina la config. iniziale
}

poi devi rifare per svuota e travasa(usa un doppio for)

__________________
Live Fast, Die Fun

Posted by francescoo on 10-01-2010 14:01:

ok grazie mille per il chiarimento pero questo lo avevo capito,il mio problema è nel'esempio che mi hai fatto tu dove hai scritto inserisci nella coda,inserisci nel grafo.
qui dovrei creare ogni volta un nuovo vettore?non so come costruire la coda e il grafo..come impostare la struttura..

Posted by palaz on 10-01-2010 15:50:

beh per la coda ti basta creare una struttura con due puntatori uno al primo elemento e uno all'ultimo, e ti devi ricordare che se inserisci sposti il puntatore all'ultimo, mentre se estrai devi spostare il puntatore al primo... e legare tra di loro tutti gli elementi interni alla coda ad es con un puntatore next...

Posted by palaz on 10-01-2010 15:52:

il grafo è un po piu incasinato ma ad esempio nel mio creo il primo nodo di partenza e in base a quanti nodi genero nella funzione genera, alloco un grafo **next in modo da legare tutti i figli al padre reallocando ogni volta che ne trovo uno nuovo...

Posted by francescoo on 10-01-2010 16:09:

ok palaz ma non riesco a implementarlo..
la mia coda deve avere un puntatore a interi per gli array che hanno la conf giusto?

cioè io dalla conf attuale faccio riempi 1 , se possibile ottengo una nuova conf che salvo in un nuovo vettore che quindi alloco dinamicamente?giusto?
poi la mia coda sarà composta da un puntatore a interi e quindi gli faccio puntare il vet appena creato,giusto?
e poi dopo come faccio a collegare tutti questi vettori?

Posted by palaz on 10-01-2010 16:12:

anche io ho usato delle code.. ma primo e ultimo li ho fatti puntare direttamente al nodo che contiene la configurazione

Posted by palaz on 10-01-2010 16:13:

pero creare solo dei vettori è scomodo io ho messo tutto in un nodo
in modo da poter puntare i suoi figli con un puntatore next creato apposta nel nodo..

Posted by francescoo on 10-01-2010 18:12:

domani qlcn di voi e' in comelico?io sono li..nel caso io sono li..

Posted by f3d386 on 11-01-2010 11:10:

ragazzi ho un grosso problema in fase di compilazione che vi posto di seguito:

gcc -c main.c
In file included from intqueue.h:5,
from main.c:5:
intdummylist.h:8: error: redefinition of ‘struct configurazione’
intdummylist.h:12: error: conflicting types for ‘configurazione’
intdummylist.h:12: note: previous declaration of ‘configurazione’ was here
intdummylist.h:14: error: redefinition of ‘struct intlist’
intdummylist.h:19: error: conflicting types for ‘intlist’
intdummylist.h:19: note: previous declaration of ‘intlist’ was here
intdummylist.h:22: error: conflicting types for ‘createlist’
intdummylist.h:22: note: previous declaration of ‘createlist’ was here
intdummylist.h:25: error: conflicting types for ‘traverse’
intdummylist.h:25: note: previous declaration of ‘traverse’ was here
intdummylist.h:28: error: conflicting types for ‘countlist’
intdummylist.h:28: note: previous declaration of ‘countlist’ was here
intdummylist.h:31: error: conflicting types for ‘insert’
intdummylist.h:31: note: previous declaration of ‘insert’ was here
intdummylist.h:34: error: conflicting types for ‘insertatend’
intdummylist.h:34: note: previous declaration of ‘insertatend’ was here
intdummylist.h:37: error: conflicting types for ‘delete’
intdummylist.h:37: note: previous declaration of ‘delete’ was here
intdummylist.h:40: error: conflicting types for ‘destroylist’
intdummylist.h:40: note: previous declaration of ‘destroylist’ was here
make: *** [main.o] Errore 1

la cosa buffa è che tolta la struttura configurazione che è una mia creazione le altre sono quelle che si possono trovare nel file omonimo su algoteam...

potete aiutarmi????

vi posto anche il makefile nel caso l'errore fosse lì...

exe: main.o intdummylist.o intqueue.o
gcc -o exe main.o intdummylist.o intqueue.o

main.o: main.c intdummylist.h intqueue.h
gcc -c main.c

intdummylist.o: intdummylist.c intdummylist.h
gcc -c intdummylist.c

intqueue.o: intqueue.c intqueue.h intdummylist.h
gcc -c intqueue.c

grazie...

Posted by f3d386 on 11-01-2010 11:58:

ok risolto XD

Posted by nevRotico on 11-01-2010 14:43:

Ragazzi che casino =)

Io sono riuscito a fare acquisizione, creazione contenitori, riempimento, svuotamento e visualizzazione per il momento. Tutto questo però utilizzando una matrice bidimensionale in cui ogni riga corrisponde ad un contenitore e le due colonne equivalgono la prima al quantitativo di litri contenuto e la seconda alla capacità massima del contenitore.

Dite che va bene oppure sto sbagliando in partenza?

Posted by nevRotico on 12-01-2010 11:26:

allora raga? si può procedere così o bisogna cambiare impostazione? che dite?

Posted by middu on 12-01-2010 19:46:

allora sto cominciando a vedere quello che posso fare; io avrei fatto
struct contenitore{
int capacità;
int stato;
} e mettendo una lista che contiene le configurazioni di ogni contenitore . é giusto questo???

Posted by middu on 12-01-2010 21:06:

altro dubbio : comando N 3 5 mi crea un contenitore da 3 galloni e da 5 galloni ??? Nel senso che crea due nodi separati ??? Poi si parla di contenitori da 5 e 3 galloni . A questo punto mi chiedo. Se nel nodo da memorizzare devo tenere in mente anche questa variabile . Non so se mi sono spiegato :

struct contenitore{
int capacità;
int stato;
} ed è il nodo che rappresenta il contenitore. Adesso eseguo il comando N 3 2 i nodi vengono così creati :

nodo 1 : capacità = 3 e stato = 0;
nodo 2 : capacità = 2 e stato = 0;

se invece riempi (2) viene riempito il nodo 2 e lo stato del nodo 2 diventa 2 ?? Come sto procedendo???

Posted by iDarbert on 12-01-2010 21:09:

Originally posted by middu
altro dubbio : comando N 3 5 mi crea un contenitore da 3 galloni e da 5 galloni ??? Nel senso che crea due nodi separati ??? Poi si parla di contenitori da 5 e 3 galloni . A questo punto mi chiedo. Se nel nodo da memorizzare devo tenere in mente anche questa variabile . Non so se mi sono spiegato :

struct contenitore{
int capacità;
int stato;
} ed è il nodo che rappresenta il contenitore. Adesso eseguo il comando N 3 2 i nodi vengono così creati :

nodo 1 : capacità = 3 e stato = 0;
nodo 2 : capacità = 2 e stato = 0;

se invece riempi (2) viene riempito il nodo 2 e lo stato del nodo 2 diventa 2 ?? Come sto procedendo???

Esatto, giusto così

Posted by middu on 12-01-2010 21:16:

ma dai ho ragionato giusto??? strano

Posted by middu on 12-01-2010 21:16:

oltre a quei due parametri va messo qualche informazione in più???

Posted by middu on 12-01-2010 21:23:

// operazione di creazione dei nodi : si tratta di inserire nella
// struttua da implementare n nodi, tante sono le capacità passate dal
// comando. Ad esempio N 1 2 4 crea tre nodi nella struttura dati di
// capacità 1 2 e 4 galloni rispettivamente

Posted by f3d386 on 14-01-2010 17:48:

@ste182

ormai dovrò fare l'appello del 1 febbraio, ma ho comunque problemi in quella parte di cui avevamo discusso...
riesci a contattarmi a qst indirizzo mail così puoi chiarirmi una parte del mio codice che non funziona?
grazie

f3d3ux@gmail.com

Posted by francescoo on 14-01-2010 21:10:

ciao a tutti,
un mio amico lo ha consegnato con goldwurm e l'assistente di laboratorio(so che è una donna ma non ricordo il nome), gli ha detto che l'uso di liste per riempi,svuota e travasa non va bene perchè richiede troppo tempo per input grandi..
qualcuno lo ha consegnato con il prof del serale e mi sa dire se a lui va bene con le liste??

Posted by f3d386 on 15-01-2010 11:16:

domandina stupida...ma quando esco dal programma è necessario fare il free() di tutto ma proprio tutto quello che ho allocato in memoria???

@francescooo

Guarda io faccio il serale e Aguzzoli mi è sembrato molto disponibile ad accettare varie implementazioni.
Personalmente io le operazioni fondamentali di riempi,svuota e travasa le faccio su array, ma uso comunque le liste in varie parti del programma e non mi ha mai detto che sia sbagliato o inaccettabile...

Posted by palaz on 15-01-2010 12:45:

beh io l'ho consegnato con aguzzoli ma prima del 22 non vi so dire nulla....cmq organizzate la struttura base con gli array cosi risolvete il problema dello scorrere la lista.. io il free() della struttura base non l'ho fatto perche tanto all'uscita del programma la memoria viene cancellata.. va fatto per quelle di supporto

Posted by nevRotico on 15-01-2010 12:56:

Le operazioni base infatti anche io le ho implementate con un semplice array bidimensionale

Posted by f3d386 on 15-01-2010 13:03:

@palaz

tu il controllo per vedere se una configurazione è già stata creata o meno come l'hai fatto?
xchè io alla fine non sono riuscito a far niente di più che far scorrere la lista coi nodi già generati e per ogni elemento della lista scorrere l'array dei livelli...
solo che così non è molto efficiente

Posted by palaz on 15-01-2010 13:09:

beh innanzi tutto non so se quello che ho fatto va bene.. lo scopriro solo il 22.. ma in pratica ogni volta che creo un nodo lo lego al padre... prima di legarlo io chiamo una funzione di ricerca in ampiezza che scorre tutta la mia struttura.... mentre l'ultima funzione l'ho implementata su una coda perché era un po piu incasinata con la ricorsione e andavo a sovrascrivere dei valori...
diciamo che con questo metodo per le prime due funzioni sono sicuro di non creare doppioni di configurazioni e anche di mandare mail il programma in loop perché mi tengo sempre da parte in una coda i nodi che sono ancora da analizzare(cioè di cui devono ancora essere create le configurazioni)..

Posted by francescoo on 15-01-2010 16:12:

ok..io avevo usato le liste anche per le operazioni elementari..
quindi voi consigliate di usare un array bidimensionale di n colonne(n è il numero di contenitori) e 2 righe(una per la cap e una per i litri contenuti)?

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

array bidimensionale = matrice (giusto ?)
io ho semplicemente usato un array di strutture.
la struttura rappresenta un contenitore e ha 2 campi: stato e livello.
ogni elemento dell'array è dunque un elemento struct e accedo ai campi semplicemente facendo vettore[i].livello oppure vettore[i].stato.

ps: ragazzi non mandatemi messaggi privati o richieste di msn, non sono mica un call center
se postate qui i vostri problemi, cercherò di aiutarvi e così magari aiutiamo anche altri che hanno il vostro stesso problema.
Comunque io non sono riuscito a consegnare per il primo appello, adesso sto cercando di implementare le funzioni per l'appello successivo.

__________________
Live Fast, Die Fun

Posted by nevRotico on 15-01-2010 23:11:

Esatto e quindi ho:
contenitori[cont][0] che contiene lo stato del contenitore e contenitori[cont][1] che contiene il livello massimo del contenitore

Ovviamente non potendo sapere a priori quanti contenitori verranno creati con il comando N contenitori viene allocato dinamicamente.

Posted by francescoo on 17-01-2010 01:18:

ciao a tutti,
vorrei chiedervi delle delucidazioni in merito alla funzione configurazioni (d):

mettiamo che io sono in 0[3] 5[5]
e d è 3

io devo stampare tutte le pox combinazioni che si possono trovare in 3 passi:
quindi come questo: svuota[2]-riempi[1]-travasa[1][2]
oppure stesse operazioni per d volte(ovviamente se possibile)e quindi non come l'esempio fatto sopra:
quindi riempi riempi riempi
svuota svuota scuota
travasa travasa travasa
??
spero di essermi spiegato..

Posted by palaz on 17-01-2010 12:34:

io ho fatto cosi:
se mi chiede con zero passi restituisco la configurazione base
con un passo faccio tutti i possibili casi quindi con i ltuo imput sarebbe 00 . 35 . 32
con due passi rifaro tutti i pasaggi un'altra volta ottenendo :
da 00: 30 . 05
da 35: nulla perche se no ripeterei configurazioni appena trovate dal passo 00
da 32: 02 . 35
e cosi via per ogni passo
con questo metodo l'imput del prof corrisponde....
spero di averti chiarito i dubbi

Posted by sko02 on 18-01-2010 08:40:

Raga vi spiego perché un array bidimensionale non è la struttura dati migliori (secondo la prof. Lonati):

code:
Per un numero abbastanza grande di contenitori non è detto che nella memoria ci sia abbastanza spazio (consecutivo)
 per l'allocazione della memoria necessaria per contenere l'intero array...

Io stò cercando di mettere a punto quello che secondo me è il miglior compromesso
e cioé un albero 2- e 3-nodi o il red-black ....
certo così i tempi di per la ricerca della posizione si allunga non è più immediato
come per un array ma almeno nel caso peggiore è log N per qualsiasi posizione

__________________
http://utenti.lycos.it/awo23/sko02.jpg

Posted by asterix07 on 18-01-2010 18:25:

ma il prototipo della funzione deve seguire quello del progetto o è a nostra discrezione? Mi spiego meglio:
Nel testo del progetto la funzione visualizza viene definita come
visualizza();
io ad esempio poso crearla come
visualizza( struct...);
(cioè passandogli un parmetro)

Posted by ste182 on 18-01-2010 19:27:

è a nostra discrezione..

__________________
Live Fast, Die Fun

Posted by ste182 on 18-01-2010 20:40:

ok ho risolto

__________________
Live Fast, Die Fun

Posted by arfish on 21-01-2010 11:43:

Ragazzi ma se i risultati del sono identici a quelli del prof. ma non nello stesso ordine??? Va bene lo stesso???

Posted by ste182 on 21-01-2010 15:27:

Originally posted by arfish
Ragazzi ma se i risultati del sono identici a quelli del prof. ma non nello stesso ordine??? Va bene lo stesso???

basta che siano giusti... l'ordine credo dipenda da come hai implementato le funzioni(ad esempio inserisci un nodo in testa anzichè in coda, quindi stampi in ordine inverso a quello del prof..)

__________________
Live Fast, Die Fun

Posted by francescoo on 21-01-2010 16:03:

ciao,
dpo tutto mi sono accorto ora di avere un problema all'inizio..
nell'inserimento delle capacità io ho utilizzato un
while(getchar()!='\n')
{
se diverso da ' ' inserisco il valore nel vett
}

il problema è che usando il getchar il valore è un carattere che vado a inserire in un vett di caratteri che poi trasformo in intero..
il problema è che cosi facendo prende numero <10
perche se inserisco 10 il getchar me li prende come 2 numeri diversi..
quindi mi fa un cont da 1 e un cont da 0..
ho provato a fare sempre il while con il getchar e poi all'interno lo scanf ma si blocca..
help me..

Posted by ste182 on 21-01-2010 19:07:

Originally posted by francescoo
ciao,
dpo tutto mi sono accorto ora di avere un problema all'inizio..
nell'inserimento delle capacità io ho utilizzato un
while(getchar()!='\n')
{
se diverso da ' ' inserisco il valore nel vett
}

il problema è che usando il getchar il valore è un carattere che vado a inserire in un vett di caratteri che poi trasformo in intero..
il problema è che cosi facendo prende numero <10
perche se inserisco 10 il getchar me li prende come 2 numeri diversi..
quindi mi fa un cont da 1 e un cont da 0..
ho provato a fare sempre il while con il getchar e poi all'interno lo scanf ma si blocca..
help me..

io ho costruito una funzione così:

code:
leggi_input(vett *v){
	int n,c;
	v->i=(int *)malloc(sizeof(int));
	v->dim=0;

	while((c=getchar()) != '\n')
	{
	 	scanf ("%d", &n);
		v->i=(int *)realloc(v->i,(v->dim+1)*sizeof(int));
		v->i[v->dim]=n;
		v->dim++;
	}
}

struct vett{
 int dim;
 int i*;
}

__________________
Live Fast, Die Fun

Posted by francescoo on 21-01-2010 19:45:

praticamente è quello che ho fatto anche io..
pero alcune volte va altre si blocca del tutto..viene fuori il messaggio di windows che si è bloccato..
dici che puo essere xke sbaglio nel deallocare?
qlcn sa il motivo di questo errore?

Posted by francescoo on 21-01-2010 21:31:

forse ho risolto..quando eseguivo la malloc non mettevo sizeof(int) e quindi probabilmente andava fuori..
puo essere questo il motivo per cui il programma si bloccava?

Posted by ste182 on 21-01-2010 23:55:

e cosa mettevi?? comunque nella malloc devi specificare la grandezza dell'area da allocare, quindi direi che sizeof è necessario

__________________
Live Fast, Die Fun

Posted by BeppeGoal on 22-01-2010 10:55:

Scusate, ho qualche dubbio...
- L'operazione "e", esiste, stampa sì o no a seconda che dalla configurazione attuale sia possibile o meno raggiungere una configurazione in cui almeno un contenitore ha livello k.

Almeno intende che sia minino k o "esattamente" k?

Per l'operazione "raggiungibile", invece, voi come l'avete interpretata? Sono fermo perché ho diverse ipotesi, ma non riesco a implementare in modo efficiente.

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

Posted by ste182 on 24-01-2010 21:35:

cmq generare tutte le possibili combinazioni e salvarle in una struttura è l'unico modo(o almeno credo).. al massimo si può ottimizzare la parte in cui fai i calcoli per generare tutte le combinazioni

__________________
Live Fast, Die Fun

Posted by Utopia on 24-01-2010 21:39:

Ragazzi come avete risolto il problema della ricerca di un configurazione nel grafo?

esempio: come faccio a sapere che strada prendere per raggiunge la configurazione 3[3],4[5] dalla radice ? cosi a caso, esploro tutte le possibili... o avete messo delle chiavi ?

Posted by francescoo on 25-01-2010 07:25:

ciao,
ho un paio di domandine:
1)per deallocare un matrice ad esempio la matrice **mat,basta fare free(mat)?o la devo mettere dentro un for?

2)io ho la mia lista v,per scorrerla e pero tenere cmq un riferimento alla testa della lista uso un altro puntatore di tipo lista che chiamo l1, e quindi pongo l1=v, ora questo l1 all'inizio devo fare l1=malloc....?penso di no..perchè va a puntare la lista gia creata e quindi non gli devo allocare spazio giusto?

3) per chi ha gia fatto l'orale con torelli..cosa chiede all'orale?

grazie mille

Posted by palaz on 25-01-2010 08:19:

allora per la domanda 2 non devi allocare l1 perche punta a una porzione di memoria gia esistente... quindi hai ragione
per la prima domanda... se è un doppio puntatore prima devi deallocare tutti i nodi puntati poi puoi deallocare mat;
infine.. all'orale torellli fa tre domande.. una sulla prima parte, cioè algoritmi di ordinamento, una sulla seconda ad es tabelle hash e una sulla parte finale, a me è capitata la domanda sulla differenza tra algoritmi greedy e programmazione dinamica.... detto cosi sembra una cazzata ma vuole sapere le cose molto nel particolare, anche se ti da una mano e ti fa ragionare

Posted by francescoo on 25-01-2010 13:33:

@palaz:
ma quindi te la teoria dove l'hai studiata?sulla dispensa di algoritmi o su altre fonti?
e lui vuole sapere anche i tempi di calcolo p cmq le cose nel specifico?
perchè io per ora sto guardando quello che lui ha scritto sul suo sito e studiando dalla dispensa..
pero non sapevo(anche perchè è molto difficile) se imparare proprio a memoria tutti i logaritmi,tempi di calcolo ecc..

Posted by palaz on 25-01-2010 13:37:

beh studi dal libro anche...
tipo: la mia prima domanda è stata: parlami del merge sort... sono partito con lo spiegare come è l'algoritmo...e lui appena ha visto che lo sapevo mi ha fermato e ha iniziato a chiedermi tempi... se ci sono problemi con la memoria.. di quanto cresce.. se è asintotico e perche..
insomma cose di questo tipo...

Posted by plafo on 25-01-2010 15:48:

Originally posted by palaz
beh studi dal libro anche...
tipo: la mia prima domanda è stata: parlami del merge sort... sono partito con lo spiegare come è l'algoritmo...e lui appena ha visto che lo sapevo mi ha fermato e ha iniziato a chiedermi tempi... se ci sono problemi con la memoria.. di quanto cresce.. se è asintotico e perche..
insomma cose di questo tipo...

quanto tempo ci vuole, secondo te, per studiare in modo decente la teoria?

Posted by palaz on 25-01-2010 20:35:

eh tanto.. io me la sono vista prima e dopo il progetto e in ogni caso ho fatto un orale di merda!

Posted by francescoo on 26-01-2010 07:22:

@palaz:
quindi se ho capito bene per deallocare la matrice:
ad esempio ho una matrice di 2 righe e n colonne io l'ho allocata cosi:
matr = malloc ( 2 * sizeof ( int * ) );
for ( r = 0; r < 2; r++ )
{
*(m+r) = malloc ( n * sizeof ( int ) );
}

quindi per deallocarla:

if(mat!=NULL)
{
for ( r = 0; r < 2; r++ )
{
free(mat+r);
}
free(mat);
}

giusto?e un modo per verificare se l'ho deallocata?

Posted by palaz on 26-01-2010 08:25:

penso sia giusto... per verificare .. no so.. prova a stampare dopo che l'hai allocata i valori che conteneva prima della deallocazione...

Posted by ste182 on 26-01-2010 23:55:

Originally posted by francescoo
@palaz:
quindi se ho capito bene per deallocare la matrice:
ad esempio ho una matrice di 2 righe e n colonne io l'ho allocata cosi:
matr = malloc ( 2 * sizeof ( int * ) );
for ( r = 0; r < 2; r++ )
{
*(m+r) = malloc ( n * sizeof ( int ) );
}

quindi per deallocarla:

if(mat!=NULL)
{
for ( r = 0; r < 2; r++ )
{
free(mat+r);
}
free(mat);
}

giusto?e un modo per verificare se l'ho deallocata?

si è giusto; prima allochi un vettore per le righe, poi per ogni riga allochi un vettore per la colonna.
la deallocazione è giusta.. solo una cosa: perchè usi la notazione con i cast? non che sia errato ma trattandosi di una matrice, quindi accessibile tramite indici, non ti viene più comodo usare una cosa del tipo:
//allocazione
matrice=(int**)malloc(2*sizeof(int*));
for(i=0;i<2;i++)
matrice[i] = (int*)malloc(n*sizeof(int));

//deallocazione
for(i=0;i<2:i++)
free(matrice[i]);
free(matrice)

ovviamente per accedere agli elementi userai matrice[i][j].
ps: se vuoi ottimizzare un minimo il codice evita il for se hai solo 2 righe.. puoi fare direttamente:
matrice[0]= malloc....
matrice[1]= malloc..
in questo modo eviti l'inizializzazione del contatore, il test su di esso e il suo incremento
:cool:

__________________
Live Fast, Die Fun

Posted by willyrs on 27-01-2010 14:09:

Ragazzi, ma come l'avete fatto mosse(k)? Io ho fatto un grafo orientato e non pesato, e sia Prim che Dijkstra richiedono il peso...

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

Posted by francescoo on 27-01-2010 17:33:

@ste182:
mi sta venendo un dubbio:

io ho fatto piu o meno come avevi detti tu alla pagina 6..intendo per trovare tutte le possibili configurazioni..
il mio grafo pero alla fine è una lista contenente tutte le configurazioni, ed è come se avessi fatto una visita per ampiezza.
pero non sono liste di adiacenza è un unica lista che ha tutte le configurazioni quindi ad es se io parto da 0[3]0[5] la mia lista sarà composta cosi:
0[3]0[5] ->3[3]0[5]->0[3]5[5]->3[3]5[5]->0[3]3[5]->...
in ogni campo della lista oltre alla matrice con la configurazione relative ci sono due campi int num e int padre quindi poi cosi riesco a trovare secondo le varie richieste anche di stampare il cammino ecc..
funziona tutto perfettamente..
pero secondo te è accettabile?questo puo definirsi come grafo?

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

Originally posted by francescoo
@ste182:
mi sta venendo un dubbio:

io ho fatto piu o meno come avevi detti tu alla pagina 6..intendo per trovare tutte le possibili configurazioni..
il mio grafo pero alla fine è una lista contenente tutte le configurazioni, ed è come se avessi fatto una visita per ampiezza.
pero non sono liste di adiacenza è un unica lista che ha tutte le configurazioni quindi ad es se io parto da 0[3]0[5] la mia lista sarà composta cosi:
0[3]0[5] ->3[3]0[5]->0[3]5[5]->3[3]5[5]->0[3]3[5]->...
in ogni campo della lista oltre alla matrice con la configurazione relative ci sono due campi int num e int padre quindi poi cosi riesco a trovare secondo le varie richieste anche di stampare il cammino ecc..
funziona tutto perfettamente..
pero secondo te è accettabile?questo puo definirsi come grafo?

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

__________________
Live Fast, Die Fun

Posted by ste182 on 27-01-2010 21:19:

Originally posted by willyrs
Ragazzi, ma come l'avete fatto mosse(k)? Io ho fatto un grafo orientato e non pesato, e sia Prim che Dijkstra richiedono il peso...

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

__________________
Live Fast, Die Fun

All times are GMT. The time now is 00:49.

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