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

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

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?

eh, bella domanda...

__________________
Live Fast, Die Fun

Ragazzi ma come funziona l'operazione raggiungibile??

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

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

__________________
C0d3 Z3r0

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

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

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

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

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

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

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

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

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

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