city_andre
02-11-2009, 11:41
Buongiorno a tutti .........
Dovrei fare il seguente progetto, ma avrei bisogno di aiuto x capire che struttura dati potrei utilizzare ........
con gurazione inizialmente vuota (0[3],0[5])
In questo progetto si chiede di risolvere il problema dei contenitori nel caso generale. Si deve gestire una
sequenza di n contenitori in ordine non decrescente di capacita c1 <c2 < cn inizialmente vuoti.
Denotiamo con (k1; k2; : : : ; kn) la con gurazione dei livelli d'acqua nei contenitori, dove 0 < ki < ci per
ogni i = 1; : : : ; n.
Sulla struttura dati che memorizza la sequenza devono essere de nite le seguenti operazioni:
- crea contenitori(n; c)
Dato un intero n ed un vettore c = (c1; c2; : : : ; cn) di interi positivi, inizializza una sequenza di n
contenitori inizialmente vuoti aventi capacita c1; c2; : : : ; cn. Ad esempio, crea sequenza(3; [2; 3; 6])
inizializzera la con gurazione (0[2],0[3],0[6]). Se esiste gia una sequenza di contenitori, la
cancella e ne crea una nuova.
- riempi(i)
Il contenitore i viene riempito no all'orlo: il suo livello passa da ki a ci. Ad esempio, riempi(2)
sulla con gurazione (0[2],2[3],0[6]) porta alla con gurazione (0[2],3[3],0[6]). L'operazione
non e valida se il contenitore i è gia pieno.
1
- svuota(i)
Il contenitore i viene svuotato completamente: il suo livello passa da ki a 0. Ad esempio, svuota(2)
sulla con gurazione (0[2],2[3],0[6]) porta alla con gurazione (0[2],0[3],0[6]). L'operazione
non e valida se il contenitore i e gia vuoto.
- travasa(i; j)
L'acqua del contenitore i viene versata nel contenitore j no al completo riempimento di j o al
completo svuotamento di i: se ki + kj < cj allora ki diventa 0 e kj diventa kj + ki, altrimenti
ki diventa ki - (cj - kj) e kj diventa cj . Ad esempio, data la con gurazione (0[2],3[3],2[6]),
travasa(2; 1) porta alla con gurazione (2[2],1[3],2[6]) mentre travasa(2; 3) porta alla con gu-
razione (0[2],0[3],5[6]) L'operazione non e valida se i è gia vuoto o se j e gia pieno.
- visualizza()
Visualizza la con gurazione attuale.
- livelli(k)
restituisce tutti i contenitori che nella con gurazione attuale hanno livello uguale a k. Se nessun
contenitore ha livello k, non stampa nulla. Ad esempio, livelli(2) chiamato sulla con gurazione
(2[2],2[3],0[6]) restituisce 1, 2.
- mosse(d)
Stampa tutte le con gurazioni direttamente raggiungibili eseguendo d operazioni dalla con gu-
razione attuale. Ad esempio, dalla con gurazione (2[3],0[5]) con una mossa si possono raggiun-
gere le con gurazioni (3[3],0[5]) con riempi(1), (2[3],5[5]) con riempi(2), (0[3],0[5]) con
svuota(1) e (0[3],2[5]) con travasa(1; 2).
- cammino minimo(k)
Stampa la piu corta sequenza di operazioni che porta dalla con gurazione iniziale ad una con-
gurazione contenente il valore k come livello di almeno un contenitore. Se non esiste nessuna
con gurazione raggiungibile che contiene il valore k, allora stampa ERRORE!. Ad esempio, John
e Zeus hanno seguito la piu corta sequenza di operazioni che porta ad una con gurazione conte-
nente un 4: (0[3],0[5]), (0[3],5[5]), (3[3],2[5]), (0[3],2[5]), (2[3],0[5]), (2[3],5[5]),
(3[3],4[5]).
- contenenti(k; h)
Stampa le con gurazioni raggiungibili che contengono contemporaneamente i livelli k e h, pre-
senti in un ordine qualunque. Se non esistono con gurazioni soddisfacenti la condizione, stampa
NON PRESENTI!.
Si noti che le operazioni richieste sono liberamente implementabili; in particolare, non vanno necessaria-
mente intese come prototipi di funzioni.
Dovrei fare il seguente progetto, ma avrei bisogno di aiuto x capire che struttura dati potrei utilizzare ........
con gurazione inizialmente vuota (0[3],0[5])
In questo progetto si chiede di risolvere il problema dei contenitori nel caso generale. Si deve gestire una
sequenza di n contenitori in ordine non decrescente di capacita c1 <c2 < cn inizialmente vuoti.
Denotiamo con (k1; k2; : : : ; kn) la con gurazione dei livelli d'acqua nei contenitori, dove 0 < ki < ci per
ogni i = 1; : : : ; n.
Sulla struttura dati che memorizza la sequenza devono essere de nite le seguenti operazioni:
- crea contenitori(n; c)
Dato un intero n ed un vettore c = (c1; c2; : : : ; cn) di interi positivi, inizializza una sequenza di n
contenitori inizialmente vuoti aventi capacita c1; c2; : : : ; cn. Ad esempio, crea sequenza(3; [2; 3; 6])
inizializzera la con gurazione (0[2],0[3],0[6]). Se esiste gia una sequenza di contenitori, la
cancella e ne crea una nuova.
- riempi(i)
Il contenitore i viene riempito no all'orlo: il suo livello passa da ki a ci. Ad esempio, riempi(2)
sulla con gurazione (0[2],2[3],0[6]) porta alla con gurazione (0[2],3[3],0[6]). L'operazione
non e valida se il contenitore i è gia pieno.
1
- svuota(i)
Il contenitore i viene svuotato completamente: il suo livello passa da ki a 0. Ad esempio, svuota(2)
sulla con gurazione (0[2],2[3],0[6]) porta alla con gurazione (0[2],0[3],0[6]). L'operazione
non e valida se il contenitore i e gia vuoto.
- travasa(i; j)
L'acqua del contenitore i viene versata nel contenitore j no al completo riempimento di j o al
completo svuotamento di i: se ki + kj < cj allora ki diventa 0 e kj diventa kj + ki, altrimenti
ki diventa ki - (cj - kj) e kj diventa cj . Ad esempio, data la con gurazione (0[2],3[3],2[6]),
travasa(2; 1) porta alla con gurazione (2[2],1[3],2[6]) mentre travasa(2; 3) porta alla con gu-
razione (0[2],0[3],5[6]) L'operazione non e valida se i è gia vuoto o se j e gia pieno.
- visualizza()
Visualizza la con gurazione attuale.
- livelli(k)
restituisce tutti i contenitori che nella con gurazione attuale hanno livello uguale a k. Se nessun
contenitore ha livello k, non stampa nulla. Ad esempio, livelli(2) chiamato sulla con gurazione
(2[2],2[3],0[6]) restituisce 1, 2.
- mosse(d)
Stampa tutte le con gurazioni direttamente raggiungibili eseguendo d operazioni dalla con gu-
razione attuale. Ad esempio, dalla con gurazione (2[3],0[5]) con una mossa si possono raggiun-
gere le con gurazioni (3[3],0[5]) con riempi(1), (2[3],5[5]) con riempi(2), (0[3],0[5]) con
svuota(1) e (0[3],2[5]) con travasa(1; 2).
- cammino minimo(k)
Stampa la piu corta sequenza di operazioni che porta dalla con gurazione iniziale ad una con-
gurazione contenente il valore k come livello di almeno un contenitore. Se non esiste nessuna
con gurazione raggiungibile che contiene il valore k, allora stampa ERRORE!. Ad esempio, John
e Zeus hanno seguito la piu corta sequenza di operazioni che porta ad una con gurazione conte-
nente un 4: (0[3],0[5]), (0[3],5[5]), (3[3],2[5]), (0[3],2[5]), (2[3],0[5]), (2[3],5[5]),
(3[3],4[5]).
- contenenti(k; h)
Stampa le con gurazioni raggiungibili che contengono contemporaneamente i livelli k e h, pre-
senti in un ordine qualunque. Se non esistono con gurazioni soddisfacenti la condizione, stampa
NON PRESENTI!.
Si noti che le operazioni richieste sono liberamente implementabili; in particolare, non vanno necessaria-
mente intese come prototipi di funzioni.