Programma in c
ciao non riesco a trovare l'algoritmo da implementare in C
purtroppo sono alle prime armi e non ho tanta esperienza
qualcuno di voi può ad aiutarmi?
grazie di cuore
è il classico prblema di logica
Si hanno due recipienti uno da 3 litri e l'altro da 5; l'obbiettivo è di ottenere 4 litri d'acqua: quale è il procedimento?
Attenzione: i recipenti si possono riempire SOLO fino al bordo e NON sono tarati; potete travasare, riempire e svuotare i recipienti tutte le volte che volete.
riempire il secchio da 3, versare in quello da 5, riempire di nuovo il secchio da 3, versare in quello da 5, ma ci entrano solo 2 litri indi in quello da 3 rimane 1 litro. Vuotare il secchio da 5 versare prima il litro e poi di nuovo con quello da tre. così ci saranno 4 litri
devo trovare l'algoritmo per rispondere alla segente domanda:
dati n recipienti di capacità diverse è possibile avere nel primo recipiente n0 capacita nel secondo c1 nel 3 c3 e così via per tutti i recipienti con le operazioni svuota riempi e travasa che funzionano come descritto nel problemino di logica sopra riportato
purtroppo sono alle prime armi e non ho tanta esperienza
qualcuno di voi può ad aiutarmi?
grazie di cuore
è il classico prblema di logica
Si hanno due recipienti uno da 3 litri e l'altro da 5; l'obbiettivo è di ottenere 4 litri d'acqua: quale è il procedimento?
Attenzione: i recipenti si possono riempire SOLO fino al bordo e NON sono tarati; potete travasare, riempire e svuotare i recipienti tutte le volte che volete.
riempire il secchio da 3, versare in quello da 5, riempire di nuovo il secchio da 3, versare in quello da 5, ma ci entrano solo 2 litri indi in quello da 3 rimane 1 litro. Vuotare il secchio da 5 versare prima il litro e poi di nuovo con quello da tre. così ci saranno 4 litri
devo trovare l'algoritmo per rispondere alla segente domanda:
dati n recipienti di capacità diverse è possibile avere nel primo recipiente n0 capacita nel secondo c1 nel 3 c3 e così via per tutti i recipienti con le operazioni svuota riempi e travasa che funzionano come descritto nel problemino di logica sopra riportato
Risposte
Prova a dare un'occhiata agli algoritmi di path-finding per la ricerca di percorsi minimi all'interno di un grafo. Come inizio potresti per esempio dare un occhiata all'algoritmo "Breadth-first search". Il problema per due recipienti con volumi primi tra di loro è ben conosciuto (dai un occhiata qui), non si può dire la stessa cosa con un numero maggiore di recipienti. Immagino che l'analisi si possa però effettuare a partire dal problema con due recipienti.
grazie provo a dare un occhiata
ok ho capito grazie al vostro aiuto l'attinenza tra i 2 recipienti e le equazioni diofantee ax+by=c
tuttavia devo trovare una soluzione per n recipienti
Quancuno può aiutarmi?
Grazie
tuttavia devo trovare una soluzione per n recipienti
Quancuno può aiutarmi?
Grazie
Qual'è la condizione dei recipienti? Che cosa ti chiede esattamente l'esercizio?
riporto un estratto del progetto questo è il link al progetto http://homes.dsi.unimi.it/~aguzzoli/did ... iehard.pdf
(il progetto lo devo fare per l'appello dell'11 febbraio
vibi@inwind.it
grazie
- 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µa
la con¯gurazione (0[2],0[3],0[6]). Se esiste giµa una sequenza di contenitori, la cancella e ne crea
una nuova.
- riempi(i)
Il contenitore i viene riempito fino all'orlo: il suo livello diventa ci. Ad esempio, riempi(2) sulla
con¯gurazione (0[2],2[3],0[6]) porta alla configurazione (0[2],3[3],0[6]). L'operazione non
µe valida se il contenitore i µe giµa pieno. In tal caso stampa OPERAZIONE NON VALIDA.
- svuota(i)
Il contenitore i viene svuotato completamente: il suo livello diventa 0. Ad esempio, svuota(2) sulla
con¯gurazione (0[2],2[3],0[6]) porta alla configurazione (0[2],0[3],0[6]). L'operazione non
µe valida se il contenitore i µe giµa vuoto. In tal caso stampa OPERAZIONE NON VALIDA.
- travasa(i; j)
'acqua del contenitore i viene versata nel contenitore j fino al completo riempimento di j o al
completo svuotamento di i.
Ad esempio, data la configurazione (0[2],3[3],2[6]), travasa(2; 1) porta alla cofigurazione
(2[2],1[3],2[6]) mentre travasa(2; 3) porta alla con¯gurazione (0[2],0[3],5[6]) L'operazione
non µe valida se i µe giµa vuoto o se j µe giµa pieno. In tal caso stampa OPERAZIONE NON VALIDA.
- visualizza()
Visualizza la configurazione attuale.
- esiste(k)
Stampa SI' oppure NO a seconda che dalla configurazione attuale sia possibile o meno raggiungere
una configurazione in cui almeno un contenitore ha livello k.
- raggiungibile(a)
Dato un vettore a = (a1; a2; : : : ; an) di interi positivi, stampa SI' oppure NO a seconda che dalla
configurazione attuale sia possibile raggiungere una configurazione in cui, per ogni i 2 f1; 2; : : : ; ng,
il contenitore i ha livello ai.
- configurazioni(d)
Stampa tutte le configurazioni raggiungibili dalla configurazione attuale eseguendo esattamente d
operazioni elementari. Ad esempio, dalla configurazione (2[3],0[5]) con una mossa si possono rag-
giungere le configurazioni (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).
3.2 Per l'appello del 28 gennaio (consegna entro l'1 febbraio)
- contenenti(k)
Stampa tutte le configurazioni raggiungibili dalla configurazione attuale e contenenti il valore k
come livello di almeno un contenitore. Se non esistono con¯gurazioni soddisfacenti la condizione,
stampa NON PRESENTI!.
- mosse(k)
Stampa una sequenza ammissibile di lunghezza minima tra quelle che portano dalla configurazione
attuale ad una configurazione contenente il valore k come livello di almeno un contenitore. Se non es-
iste nessuna configurazione raggiungibile che contiene il valore k, allora stampa IRRAGGIUNGIBILE!.
Ad esempio, John e Zeus hanno seguito la piµu corta sequenza di operazioni che porta ad una config-
urazione contenente 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]).
- 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µa piµu 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 con¯gurazione attuale in una configurazione pericolosa,
l'operazione non deve essere eseguita, e deve essere stampato il messaggio OPERAZIONE PERICOLOSA.
- innocua(a)
Dato un vettore a = (a1; a2; : : : ; an) di interi positivi, dichiara \innocua" la configurazione in cui
il contenitore i ha livello ai. Questo implica che questa con¯gurazione potrµa essere nuovamente
utilizzata nel calcolo di altre operazioni (quali ad esempio contenenti(k) o mosse(k)).
- critica(a)
Stampa, se esiste, una configurazione a0 (distinta da a e dalla configurazione attuale) tale che ogni
sequenza di operazioni elementari dalla con¯gurazione attuale alla con¯gurazione a contiene a0. Se
tale con¯gurazione non esiste, allora stampa NON ESISTE CONFIGURAZIONE CRITICA. (Si osservi che
per una data configurazione c possono esistere piµu con¯gurazioni critiche distinte. Basta stamparne
una di queste.)
- mosse(k; h)
Stampa una sequenza ammissibile di lunghezza minima tra quelle che portano da una configurazione
avente un contenitore riempito a livello k a una avente un contenitore riempito a livello h. Se non
esiste nessuna di tali configurazioni, allora stampa NON E' POSSIBILE!.
- disattiva()
Disattiva la possibilitµa di svuotare i contenitori, fino a quando tale possibilitµa non viene riattivata
tramite l'operazione attiva(). Questo implica che ogni operazione elementare svuota(i) dovrµa
essere ignorata, e che nel calcolo di altre operazioni (quali ad esempio mosse(k) o mosse(k; h))
l'operazione svuota(i) non potrµa essere utilizzata.
- attiva()
Riattiva la possibilitµa di svuotare i contenitori.
(il progetto lo devo fare per l'appello dell'11 febbraio
vibi@inwind.it
grazie
- 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µa
la con¯gurazione (0[2],0[3],0[6]). Se esiste giµa una sequenza di contenitori, la cancella e ne crea
una nuova.
- riempi(i)
Il contenitore i viene riempito fino all'orlo: il suo livello diventa ci. Ad esempio, riempi(2) sulla
con¯gurazione (0[2],2[3],0[6]) porta alla configurazione (0[2],3[3],0[6]). L'operazione non
µe valida se il contenitore i µe giµa pieno. In tal caso stampa OPERAZIONE NON VALIDA.
- svuota(i)
Il contenitore i viene svuotato completamente: il suo livello diventa 0. Ad esempio, svuota(2) sulla
con¯gurazione (0[2],2[3],0[6]) porta alla configurazione (0[2],0[3],0[6]). L'operazione non
µe valida se il contenitore i µe giµa vuoto. In tal caso stampa OPERAZIONE NON VALIDA.
- travasa(i; j)
'acqua del contenitore i viene versata nel contenitore j fino al completo riempimento di j o al
completo svuotamento di i.
Ad esempio, data la configurazione (0[2],3[3],2[6]), travasa(2; 1) porta alla cofigurazione
(2[2],1[3],2[6]) mentre travasa(2; 3) porta alla con¯gurazione (0[2],0[3],5[6]) L'operazione
non µe valida se i µe giµa vuoto o se j µe giµa pieno. In tal caso stampa OPERAZIONE NON VALIDA.
- visualizza()
Visualizza la configurazione attuale.
- esiste(k)
Stampa SI' oppure NO a seconda che dalla configurazione attuale sia possibile o meno raggiungere
una configurazione in cui almeno un contenitore ha livello k.
- raggiungibile(a)
Dato un vettore a = (a1; a2; : : : ; an) di interi positivi, stampa SI' oppure NO a seconda che dalla
configurazione attuale sia possibile raggiungere una configurazione in cui, per ogni i 2 f1; 2; : : : ; ng,
il contenitore i ha livello ai.
- configurazioni(d)
Stampa tutte le configurazioni raggiungibili dalla configurazione attuale eseguendo esattamente d
operazioni elementari. Ad esempio, dalla configurazione (2[3],0[5]) con una mossa si possono rag-
giungere le configurazioni (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).
3.2 Per l'appello del 28 gennaio (consegna entro l'1 febbraio)
- contenenti(k)
Stampa tutte le configurazioni raggiungibili dalla configurazione attuale e contenenti il valore k
come livello di almeno un contenitore. Se non esistono con¯gurazioni soddisfacenti la condizione,
stampa NON PRESENTI!.
- mosse(k)
Stampa una sequenza ammissibile di lunghezza minima tra quelle che portano dalla configurazione
attuale ad una configurazione contenente il valore k come livello di almeno un contenitore. Se non es-
iste nessuna configurazione raggiungibile che contiene il valore k, allora stampa IRRAGGIUNGIBILE!.
Ad esempio, John e Zeus hanno seguito la piµu corta sequenza di operazioni che porta ad una config-
urazione contenente 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]).
- 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µa piµu 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 con¯gurazione attuale in una configurazione pericolosa,
l'operazione non deve essere eseguita, e deve essere stampato il messaggio OPERAZIONE PERICOLOSA.
- innocua(a)
Dato un vettore a = (a1; a2; : : : ; an) di interi positivi, dichiara \innocua" la configurazione in cui
il contenitore i ha livello ai. Questo implica che questa con¯gurazione potrµa essere nuovamente
utilizzata nel calcolo di altre operazioni (quali ad esempio contenenti(k) o mosse(k)).
- critica(a)
Stampa, se esiste, una configurazione a0 (distinta da a e dalla configurazione attuale) tale che ogni
sequenza di operazioni elementari dalla con¯gurazione attuale alla con¯gurazione a contiene a0. Se
tale con¯gurazione non esiste, allora stampa NON ESISTE CONFIGURAZIONE CRITICA. (Si osservi che
per una data configurazione c possono esistere piµu con¯gurazioni critiche distinte. Basta stamparne
una di queste.)
- mosse(k; h)
Stampa una sequenza ammissibile di lunghezza minima tra quelle che portano da una configurazione
avente un contenitore riempito a livello k a una avente un contenitore riempito a livello h. Se non
esiste nessuna di tali configurazioni, allora stampa NON E' POSSIBILE!.
- disattiva()
Disattiva la possibilitµa di svuotare i contenitori, fino a quando tale possibilitµa non viene riattivata
tramite l'operazione attiva(). Questo implica che ogni operazione elementare svuota(i) dovrµa
essere ignorata, e che nel calcolo di altre operazioni (quali ad esempio mosse(k) o mosse(k; h))
l'operazione svuota(i) non potrµa essere utilizzata.
- attiva()
Riattiva la possibilitµa di svuotare i contenitori.
Se non hai altro da fare da qui al 11 febbraio forse ce la puoi anche fare
Che cosa sei riuscito a fare finora? Dal testo del problema presumo che voglia una soluzione che sfrutti i normali algoritmi su grafi. La dimensione del grafo può ovviamente diventare grande molto in fretta ma credo che non verrà testato con un numero di contenitori particolarmente grande o con contenitori particolarmente capienti.
- crea contenitori(c)
- riempi(i)
- svuota(i)
- travasa(i; j)
- visualizza()
sto implementando Esiste : sfruttando la propretà delle equazioni
per il resto non sono riuscita a trovare una soluzione valida al momento
grazie
- riempi(i)
- svuota(i)
- travasa(i; j)
- visualizza()
sto implementando Esiste : sfruttando la propretà delle equazioni
per il resto non sono riuscita a trovare una soluzione valida al momento
grazie
GRAZIE APATRIARCA
sono riuscita con la funzione esiste
per raggiungibile richiamo l'algorimo di esiste
e fin qui ok se i test vanno bene
configurazioni(d)
per ogni elemento provo tutte le possibili d combinazioni di operazioni ma viene qualcosa di enorme
e per contenenti(k)
pensavo di valutare tutte le possibili combinazioni
a1 a2 a3 a4 ...
B1 B2 B3 B4 ...
dove B1 è l'insime di tutti gli interi positivi <=a1
e con raggiungibile verificarle
ma mi sembra qualcosa di enorme
possibile che non cia altro modo?
grazie ciao
sono riuscita con la funzione esiste
per raggiungibile richiamo l'algorimo di esiste
e fin qui ok se i test vanno bene
configurazioni(d)
per ogni elemento provo tutte le possibili d combinazioni di operazioni ma viene qualcosa di enorme
e per contenenti(k)
pensavo di valutare tutte le possibili combinazioni
a1 a2 a3 a4 ...
B1 B2 B3 B4 ...
dove B1 è l'insime di tutti gli interi positivi <=a1
e con raggiungibile verificarle
ma mi sembra qualcosa di enorme
possibile che non cia altro modo?
grazie ciao
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo