Indice del forum Olimpo Informatico
I Forum di Zeus News
Leggi la newsletter gratuita - Attiva il Menu compatto
 
 FAQFAQ   CercaCerca   Lista utentiLista utenti   GruppiGruppi   RegistratiRegistrati 
 ProfiloProfilo   Messaggi privatiMessaggi privati   Log inLog in 

    Newsletter RSS Facebook Twitter Contatti Ricerca
* QUIZ: Le TRE taniche (forse anche di più)
Nuovo argomento   Rispondi    Indice del forum -> Enigmi e giochi matematici
Precedente :: Successivo  
Autore Messaggio
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 06 Gen 2007 21:09    Oggetto: * QUIZ: Le TRE taniche (forse anche di più) Rispondi citando

Il problema delle due taniche era stato proposto qui.

Ora passiamo a qualcosa di più complicato.

Ho trovato su Puzzles and paradoxes di T. H. O'Beirne (Oxford University Press - 1965) un intero capitolo dedicato a taniche, bottiglie e bidoni.

Ecco il primo quesito che ho scelto:

Usando tre taniche da 3, 5 e 8 galloni suddividere 8 galloni in due parti uguali.


L'ultima modifica di ulisse il 23 Feb 2007 16:15, modificato 1 volta
Top
Profilo Invia messaggio privato HomePage
MK66
Moderatore Sistemi Operativi
Moderatore Sistemi Operativi


Registrato: 17/10/06 22:24
Messaggi: 8448
Residenza: dentro una cassa sotto 3 metri di terra...

MessaggioInviato: 07 Gen 2007 12:13    Oggetto: Rispondi citando

Premetto che potranno esserci metodi migliori, ma questo è il primo che mi è venuto in mente, immedesimandomi mentalmente in una situazione del genere...Shocked Confuso
Citazione:

Indicando le 3 taniche come A (3 galloni), B (5 galloni) e C (8 galloni), un procedimento potrebbe essere questo:
- la situazione iniziale è: A=0 B=0 C=8
- si travasano 3 galloni da C in A (la situazione diventa A=3 B=0 C=5)
- si travasano i 3 galloni da A a B (A=0 B=3 C=5)
- si travasano altri 3 galloni da C in A (A=3 B=3 C=2)
- si riempie B con parte del contenuto di A (A=1 B=5 C=2)
- si svuota il contenuto di B in C (A=1 B=0 C=7)
- si travasa il contenuto da A in B (A=0 B=1 C=7)
- si riempie A con parte del contenuto di C (A=3 B=1 C=4)
- si travasa il contenuto di A in B (A=0 B=4 C=4) ed il gioco è fatto.

Top
Profilo Invia messaggio privato HomePage
Benny
Moderatore Hardware e Networking
Moderatore Hardware e Networking


Registrato: 28/01/06 14:35
Messaggi: 6382
Residenza: Non troppo vicino, mai troppo lontano

MessaggioInviato: 07 Gen 2007 13:44    Oggetto: Rispondi citando

Un casino... meglio segnare passaggio per passaggio:
Citazione:
Situazione iniziale:
Tanica da 8: 8 galloni
Tanica da 5: vuota
Tanica da 3: vuota

riempio la tanica da 3 galloni versando acqua da quella da 8 galloni
T8: 5 gall
T5: vuota
T3: 3 gall

verso il contenuto di T3 in T5
T8: 5 gall
T5: 3 gall
T3: vuota

verso altri 3 galloni da T8 in T3
T8: 2 gall
T5: 3 gall
T3: 3 gall

riempio T5 versando da T3
T8: 2 gall
T5: 5 gall
T3: 1 gall

vuoto T5 in T8
T8: 7 gall
T5: vuota
T3: 1 gall

vuoto T3 in T5
T8: 7 gall
T5: 1 gall
T3: vuota

riempio T3 attingendo da T8
T8: 4 gall
T5: 1 gall
T3: 3 gall

infine vuoto T3 in T5
T8: 4 gall
T5: 4 gall
T3: vuota

in tutto 2^3=8 passaggi
(che l'esponente sia casuale?)


Come dice MK66, magari c'è una soluzione più semplice, ma con meno passaggi non mi viene...
Top
Profilo Invia messaggio privato
_L_
Semidio
Semidio


Registrato: 27/12/06 23:47
Messaggi: 215
Residenza: Brugherio (MI)

MessaggioInviato: 07 Gen 2007 13:50    Oggetto: Rispondi citando

Citazione:
a=tanica da 3, b=tanica da 5, c=tanica da 8
a b c
0 0 8 stato iniziale
0 5 3 (c --> b)
3 2 3 (b --> a)
0 2 6 (a --> c)
2 0 6 (b --> a)
2 5 1 (c --> b)
3 4 1 (b --> a)
0 4 4 (a --> c)
in 7 passaggi
Top
Profilo Invia messaggio privato HomePage MSN
Salmastro
Dio minore
Dio minore


Registrato: 13/12/06 19:36
Messaggi: 883
Residenza: Casalmico

MessaggioInviato: 07 Gen 2007 17:45    Oggetto: W _L_! Rispondi citando

...pensavo anch'io che 8 fosse il minimo, ora credo che non si possa fare meglio di quanto ci ha "nascosto" _L_!

Ma, ora, nasce spontanea una domanda: posto che le configurazioni possibili sono

Citazione:
24 (credo e spero) e cioè, nell'ordine tanica da 3, tanica da 5, tanica da 8,

008 017 026 035 044 053
107 116 125 134 143 152
206 215 224 233 242 251
305 314 323 332 341 350


è possibile partendo da quella neutra (008) raggiungere una qualsiasi delle altre? E se non è possibile, perche?

Salmastro
Top
Profilo Invia messaggio privato AIM Yahoo MSN
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 09 Gen 2007 14:45    Oggetto: Rispondi citando

Bravo MK66 che ha trovato una soluzione in 8 mosse e bravo _L_ che ne ha trovata una in 7 !

Resta da capire se è l'unica soluzione in 7 mosse e se, soprattutto, è la migliore.

Mi piace la domanda di Salmastro che muove così il primo passo verso la modellizzazione del problema!
Avendo il libro sotto al naso non posso intervenire quindi resto in attesa di risposte e considerazioni.

Permettetemi un piccolo aiuto (la strada verso il modello è lunga, seppur non complicata).

A meno di non travasare a casaccio del liquido da una tanica all'altra (cosa totalmente inutile ai nostri scopi) avremo sempre a che fare con quantità intere di liquido.

Secondo questa premessa che per rigore esplicito, avete già scelto di rappresentare lo stato del sistema facendo uso di una terna di numeri interi.

Proviamo ad usare un po' di geometria analitica. Poiché abbiamo 3 taniche dovremo introdurre una terna XYZ di assi cartesiani ortogonali.
I possibili stati del nostro sistema saranno rappresentati da punti (a coordinate intere) nello spazio cartesiano.

Dove se ne sta questo insieme di punti? sono sparsi a casaccio o se ne stanno in un luogo geometrico ben preciso?
Per rispondere a questa domanda ricordate che la quantità di liquido presente complessivamente nelle tre taniche è costante...
Top
Profilo Invia messaggio privato HomePage
Taifu
Semidio
Semidio


Registrato: 24/10/06 10:13
Messaggi: 203

MessaggioInviato: 09 Gen 2007 16:25    Oggetto: Rispondi citando

Vi confermo che la soluzione in sette mosse e` unica ed e` anche la migliore.
Ciao.
Marco.
P.S. Ho usato la forza bruta e un programmino Python di una trentina di righe... Smile
Top
Profilo Invia messaggio privato
Taifu
Semidio
Semidio


Registrato: 24/10/06 10:13
Messaggi: 203

MessaggioInviato: 09 Gen 2007 16:56    Oggetto: Re: W _L_! Rispondi citando

Ecco la risposta per salmastro.
Anche se non so il perche`...
Di fianco a ogni posizione il numero minimo di mosse.

Citazione:
Posizione: 008 = 0
Posizione: 017 = 6
Posizione: 026 = 3
Posizione: 035 = 2
Posizione: 044 = 7
Posizione: 053 = 1
Posizione: 107 = 5
Posizione: 116 = irraggiungibile
Posizione: 125 = irraggiungibile
Posizione: 134 = irraggiungibile
Posizione: 143 = irraggiungibile
Posizione: 152 = 4
Posizione: 206 = 4
Posizione: 215 = irraggiungibile
Posizione: 224 = irraggiungibile
Posizione: 233 = irraggiungibile
Posizione: 242 = irraggiungibile
Posizione: 251 = 5
Posizione: 305 = 1
Posizione: 314 = 7
Posizione: 323 = 2
Posizione: 332 = 3
Posizione: 341 = 6
Posizione: 350 = 2


Ciao.
Marco.
Top
Profilo Invia messaggio privato
Salmastro
Dio minore
Dio minore


Registrato: 13/12/06 19:36
Messaggi: 883
Residenza: Casalmico

MessaggioInviato: 09 Gen 2007 17:15    Oggetto: il luogo dei punti Rispondi citando

dalle dritte di Ulisse e dal quel che mi ricordo di geometria analitica nello spazio (che odiavo: non riesco a pensare in tre dimensioni!), mi pare che
Citazione:
i punti appartengano al piano x+y+z=8, cioè quello perpendicolare al versore(?) (1; 1; 1)
poi posso fare un passetto avanti e cioè
Citazione:
per x fissato (per noi: 0,1,2 e 3) le possibili coppie (y;z), in numero di 6 per ogni x, appartengono ad una retta e, per essere più precisi ad un segmento
concludendo tutti i punti (ma sono veramente 24?) appartengono ad un
Citazione:
parallelogramma nello spazio con vertici in: (0;0;8 ), (0;5;3), (3;0;5) e (3;5;0), con gli altri simmetricamenti disposti, lungo il perimetro ed all'interno

se li collego, ho una specie di rete, ma allo stato attuale non so trovare una legge che mi possa far saltellare su TUTTI questi punti...

Salmastro

P.S.: leggendo Taifu mi accorgo che del "mio" parallelogramma possono essere raggiunti tutti e solo i 16 punti lungo il perimetro. Quelli all'interno NO! Quale oscura ragione spiega tutto ciò??
Top
Profilo Invia messaggio privato AIM Yahoo MSN
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 09 Gen 2007 23:32    Oggetto: Rispondi citando

Perfetto!
(solo una pignoleria che mi vergogno di puntualizzare: i versori sono i vettori di lunghezza unitaria uscenti dall'origine e diretti come gli assi coordinati; quindi (1;1;1) è giusto chiamarlo vettore)

Ecco i grafici di quanto hai scritto con qualche osservazione.

Innanzi tutto il piano passante per (8,0,0), per (0,8,0) e per (0,0,8 ).
Poiché le misure delle taniche sono positive ho limitato la figura al "quadrante" a coordinate positive. Il piano si riduce, dunque a un triangolo.



Al variare del liquido complessivamente contenuto nelle taniche, l'unica cosa che cambia è la distanza del piano dall'origine e, conseguentemente, la dimensione del triangolo.

Osservando il triangolo da un'altra angolazione ovvero da un punto sul prolungamento del vettore (1;1;1) possiamo notare che il triangolo è equilatero, che la trama del reticolo è costituita da tre fasci di rette ognuno parallelo a un lato del triangolo e che, assecondando l'orientamento degli assi, ogni tanica si riempie andando verso il corrispondente vertice del triangolo e si svuota andando verso il lato opposto.
I punti su una parallela corrispondono a tutte le configurazioni che possiamo ottenere mantenendo costante il contenuto di una tanica e distribuendo il liquido residuo in tutti i modi possibili tra le altre due taniche.



Poiché tutti i punti che rappresentano potenziali stati del sistema giacciono sul triangolo, possiamo dimenticarci dello spazio tridimensionale e considerare soltanto il triangolo equilatero col relativo reticolo ottenuto unendo tutti i punti prima trovati.

Ovviamente una tanica da 3 galloni non potrà contenerne 4 quindi dovremo escludere dal reticolo tutti i punti corrispondenti a configurazioni impossibili.
Il reticolo delle configurazioni possibili sarà costituito da un poligono incluso nel triangolo la cui forma dipenderà dalle condizioni iniziali (volume di ognuna delle tre taniche e liquido complessivamente disponibile).

Nel nostro caso il reticolo è esattamente quello descritto da Salmastro:


Ho evidenziato con un quadratino rosso la configurazione di partenza, con un quadratino blu quella di arrivo e con i pallini rossi le altre configurazioni possibili.

Un cambio di stato (una "mossa") può essere rappresentato con una freccia che unisce i due stati iniziale e finale.
Poiché l'unica cosa che possiamo fare è travasare liquido da una tanica ad un'altra, due punti potranno essere collegati da una freccia solo se essi coincidono per una coordinata ovvero se giacciono sulla medesima parallela.

Evidentemente tutti gli stati possono essere stati iniziali ma non tutti gli stati possono essere stati finali.

Ora dovrebbe essere facile rispondere alla domanda di Salmastro: "quali sono i punti che non possono mai essere raggiunti da una freccia e perché?"
Come ha notato Salmastro i punti raggiungibili sono solo quelli perimetrali.
Questo perché i punti perimetrali sono tutti quelli corrispondenti a taniche piene o taniche vuote (infatti quando iniziamo a travasare del liquido da una tanica ad un'altra siamo costretti a proseguire sino a che o la prima tanica si svuota o la seconda si riempie).

Quindi le uniche frecce che potremo disegnare sul reticolo saranno quelle che terminano sul perimetro.
Anzi, poiché dopo la prima mossa piombiamo inesorabilmente sul perimetro, possiamo tranquillamente affermare che le uniche frecce che è lecito disegnare sono quelle che collegano due punti perimetrali sulla stessa parallela.

Ecco un'esempio di mosse che soddisfano tale condizione.



E' tutto qui e le sequenze di mosse vanno costruite per tentativi o ci sono ulteriori regole che ci garantiscono di determinare con certezza se il problema ammette o no soluzione e, nel caso esista, di costruirla?
Top
Profilo Invia messaggio privato HomePage
Taifu
Semidio
Semidio


Registrato: 24/10/06 10:13
Messaggi: 203

MessaggioInviato: 09 Gen 2007 23:52    Oggetto: Rispondi citando

Se vi puo` essere di aiuto questi sono i numeri minimi di mosse con cui si possono raggiungere le configurazioni possibili:
Codice:

          0
        5   6
      4   .   3
    1   .   .   2
      7   .   .   7
        2   .   .   1
          3   .   4
            6   5
              2
               
Top
Profilo Invia messaggio privato
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 17 Gen 2007 17:03    Oggetto: Rispondi citando

Avevo lasciato una domanda in sospeso:
Ulisse ha scritto:
E' tutto qui e le sequenze di mosse vanno costruite per tentativi o ci sono ulteriori regole che ci garantiscono di determinare con certezza se il problema ammette o no soluzione e, nel caso esista, di costruirla?


Quindi rispondo prima di passare alla fase successiva.
Non pensavate mica di cavarvela col semplice problema delle 3 taniche, vero? In fondo al post trovate il nuovo problema!

Ci sono ulteriori regole che garantiscono di determinare se il problema ammetta o meno soluzione.
Il metodo è costruttivo quindi, oltre a garantire l'esistenza, consente anche di individuare la soluzione.

Innanzi tutto avevo trascurato di specificare che i possibili cammini devono essere reversibili.
I vincoli dichiarati nel problema si traducono pari pari nella richiesta di reversibilità delle mosse.
Si parte da una configurazione "terminale" ovvero in cui ogni tanica è o completamente piena o completamente vuota e si arriva ad un'altra configurazione terminale.
Ciò definisce completamente una mossa reversibile.

A che serve specificare la reversibilità delle mosse?
Serve perché uno dei metodi per individuare le soluzioni richiede di procedere a ritroso dalla configurazione finale, fino a raggiungere quella iniziale.
Ciò è possibile solo in presenza di mosse reversibili.

Come si sceglie la nuova mossa dopo averne effettuata una?
Basta osservare che nel movimento sul reticolo vale la "regola del rimbalzo" nota ai giocatori di biliardo: quando arriviamo ad un punto sul perimetro, la nuova mossa è quella che fa procedere in direzione simmetrica rispetto all'asse della "sponda".
Muoversi in direzioni diverse è vietato dalla regola di reversibilità.
Se anche tale regola non sussistesse (formalmente nessuno vieta di spostarsi da un punto interno ad un lato ad un suo vertice) otterremmo solo una inutile perdita di mosse.
Fanno eccezione i vertici dai quali si può uscire seguendo la regola del rimbalzo oppure costeggiando il perimetro.
Nel problema in esame (3 taniche da 3, 5 e 8 galloni) l'unica ragione per non seguire la regola del rimbalzo è per raggiungere in due sole mosse il vertice 350.

Detto questo, rimangono solo due possibili cammini risolutivi:



Quello in blu rappresenta la soluzione in 8 mosse fornita da MK66.
Quella in giallo rappresenta la soluzione in 7 mosse fornita da _L_

Un altro modo di procedere consiste nel partire dalla configurazione iniziale ed etichettare con un 1 tutti i punti raggiungibili da 008 in una sola mossa e poi procedere etichettando con 2 tutti i punti raggiungibili con una sola mossa a partire da tutti i punti etichettati 1 e così via sino a esaurimento delle mosse possibili. Se con una mossa raggiungiamo un punto già etichettato con un numero più basso, abbandoniamo il cammino e ci concentriamo sui rimanenti.

Con questo metodo otteniamo, nel nostro problema, il seguente grafico che è pari pari il grafico formato testo postato da Taifu:



Oltre ad individuare tutti i punti raggiungibili a partire dalla configurazione iniziale (e quindi a determinare l'esistenza o meno di una soluzione) possiamo in questo modo individuare il percorso più breve (se esistente) che conduce alla soluzione e quantificare il numero di mosse necessarie.

Per concludere c'è ancora una cosa da dire: il problema delle tre taniche è stato proposto per la prima volta da Tartaglia nel XVI secolo.
Ricordo che quanto ho scritto è tratto (traducendolo con un bagno di sudore da un inglese probabilmente ineccepibile ma decisamente contorto e arzigogolato) dal testo citato nel post di apertura.
Unico contributo personale è la parte iniziale per spiegare da dove piova il triangolo che nel testo, come al solito, viene presentato direttamente senza spiegare se l'idea sia grazia dello spirito santo o chissà che.

Chi volesse divertirsi può cimentarsi ancora con tre taniche, questa volta da 5, 7 e 9 galloni tentando di suddividere 9 galloni in due parti da 3 e 6 galloni ognuna.

Ora che la trattazione del problema delle tre taniche è completata, passiamo a qualcosa di più impegnativo cioè al problema delle quattro taniche ecco il problema che l'autore immerge in un contesto di spionaggio:

In un centro militare di ricerche hanno sviluppato la formula per un nuovo propellente. Ne hanno anche prodotto una piccola quantità (26 galloni) che custodiscono in tre taniche da 5, 8 e 13 galloni.

Tre agenti segreti di una potenza nemica rubano le taniche prendendone ognuno una.
Quando, ancora in territorio nemico, si radunano si accorgono che la tanica più piccola ha perso il tappo e, durante il trasporto, si è svuotata.
Essi hanno a disposizione una quarta tanica da 26 galloni in grado, quindi, di contenere tutto il propellente residuo.
Per non rischiare il danno totale durante il rientro in patria (ovvero di perdere in un botto tutto il propellente rimasto) decidono, però, di dividere i 21 galloni residui in tre parti uguali.

Siete in grado di individuare una soluzione ottimale?

Uscendo dalla metafora il problema è: date quattro taniche da 5, 8, 13 e 26 galloni, vuote quelle da 5 e da 26 galloni e piene le altre due, suddividere 21 galloni in tre parti uguali.

Chi arrivasse ad una soluzione tramite forza bruta (uno a caso) può farlo ma dovrà fornirmi una copia del codice (in Pythoon per caso?) che sono curioso di vedere come avete impostato la risoluzione.
Top
Profilo Invia messaggio privato HomePage
Taifu
Semidio
Semidio


Registrato: 24/10/06 10:13
Messaggi: 203

MessaggioInviato: 17 Gen 2007 21:48    Oggetto: Rispondi citando

ulisse ha scritto:
Uscendo dalla metafora il problema è: date quattro taniche da 5, 8, 13 e 26 galloni, vuote quelle da 5 e da 26 galloni e piene le altre due, suddividere 21 galloni in tre parti uguali.

Chi arrivasse ad una soluzione tramite forza bruta (uno a caso) può farlo ma dovrà fornirmi una copia del codice (in Pythoon per caso?) che sono curioso di vedere come avete impostato la risoluzione.


Ulisse,
una domanda: va bene solo la configurazione 0/7/7/7 oppure basta anche una in cui uno dei 7 e` diviso in due taniche? Per esempio 1/7/7/6 ?

Te lo chiedo perche` posso gia` affermare che non esistono soluzioni con 7 o meno mosse anche nell'ipotesi in cui un 7 e` diviso tra due taniche. Aumentare a 8 o piu` mosse vuol dire allungare di parecchio i tempi di esecuzione per cui vorrei capire se posso tagliare qualche ramo.

Con 5 mosse siamo a 15 secondi di esecuzione.
Con 6 mosse siamo a 1 minuto e 8 secondi di esecuzione.
Con 7 mosse siamo a 5 minuti e 8 secondi di esecuzione.
E cosi` via...

Ah, dimenticavo: si chiama Python. Ancora non lo sapete, ma in futuro chiamarlo Pythoon sara` come aver accennato al teorema di Piiitagora... Smile

Ciao.
Marco.
Top
Profilo Invia messaggio privato
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 18 Gen 2007 09:13    Oggetto: Rispondi citando

Taifu ha scritto:
Ah, dimenticavo: si chiama Python. Ancora non lo sapete, ma in futuro chiamarlo Pythoon sara` come aver accennato al teorema di Piiitagora... Smile


Ehm, ehm... Embarassed Embarassed Embarassed Embarassed Embarassed

E' che io conosco a malapena il Baasic... Toilet


La configurazione 1/7/7/6 non può essere considerata finale (ad esempio perché le tre spie, per potersene andare ognuno con una tanica, devono fare ancora una mossa e concludere con 0/7/7/7).

Tempi macchina che si allungano? Jump
Prova a sottoporre al tuo programma il secondo problema con tre taniche e dimmi che succede...
Top
Profilo Invia messaggio privato HomePage
Taifu
Semidio
Semidio


Registrato: 24/10/06 10:13
Messaggi: 203

MessaggioInviato: 18 Gen 2007 10:34    Oggetto: Rispondi citando

ulisse ha scritto:

Tempi macchina che si allungano? Jump
Prova a sottoporre al tuo programma il secondo problema con tre taniche e dimmi che succede...


Il secondo problema con tre taniche non ha soluzione (do per scontato che una soluzione abbia meno di 99 mosse).

E il tuo sorrisino beffardo riguardo ai tempi macchina mi pensare che anche la versione a quattro taniche non ce l'abbia.

Mi toccherà leggere a fondo la tua spiegazione per dimostrare che non c'è soluzione...

Ma il tempo latita! Smile

Ciao.
Marco.
Top
Profilo Invia messaggio privato
Salmastro
Dio minore
Dio minore


Registrato: 13/12/06 19:36
Messaggi: 883
Residenza: Casalmico

MessaggioInviato: 18 Gen 2007 10:54    Oggetto: mi fido di taifu Rispondi citando

...per cui abbandono i rimbalzi nel "trapezio" (?) legato alle configurazioni delle tre taniche, anche se a prima vista il fatto che i punti di arrivo siano ben 4 (036, 063, 306, 360) e siano tutti sul perimetro dovrebbe invitarmi a perseverare.

Per le 4 taniche sono curioso di vedere come si gioca a biliardo all'interno di una piramide tronca.

Salmastro
Top
Profilo Invia messaggio privato AIM Yahoo MSN
Taifu
Semidio
Semidio


Registrato: 24/10/06 10:13
Messaggi: 203

MessaggioInviato: 18 Gen 2007 15:52    Oggetto: Rispondi citando

Dunque, dunque, limitandoci alla soluzione con 7/7/7 il programmino è molto più spedito.
La soluzione più breve trovata sinora è in 45 mosse (in circa 5 secondi di tempo macchina).
Sta ancora girando, vediamo.
Ciao.
Marco.
P.S. Il tempo di scrivere questo messaggio e ne ha trovata una da 44 mosse.

Citazione:

In 44 mosse
['<Tanica da 5 con 5>', '<Tanica da 8 con 3>', '<Tanica da 13 con 13>', '<Tanica da 26 con 0>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 8>', '<Tanica da 13 con 13>', '<Tanica da 26 con 0>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 0>', '<Tanica da 13 con 13>', '<Tanica da 26 con 8>']
['<Tanica da 5 con 5>', '<Tanica da 8 con 0>', '<Tanica da 13 con 8>', '<Tanica da 26 con 8>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 5>', '<Tanica da 13 con 8>', '<Tanica da 26 con 8>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 0>', '<Tanica da 13 con 8>', '<Tanica da 26 con 13>']
['<Tanica da 5 con 5>', '<Tanica da 8 con 0>', '<Tanica da 13 con 3>', '<Tanica da 26 con 13>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 5>', '<Tanica da 13 con 3>', '<Tanica da 26 con 13>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 0>', '<Tanica da 13 con 3>', '<Tanica da 26 con 18>']
['<Tanica da 5 con 3>', '<Tanica da 8 con 0>', '<Tanica da 13 con 0>', '<Tanica da 26 con 18>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 3>', '<Tanica da 13 con 0>', '<Tanica da 26 con 18>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 0>', '<Tanica da 13 con 0>', '<Tanica da 26 con 21>']
['<Tanica da 5 con 5>', '<Tanica da 8 con 0>', '<Tanica da 13 con 0>', '<Tanica da 26 con 16>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 5>', '<Tanica da 13 con 0>', '<Tanica da 26 con 16>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 0>', '<Tanica da 13 con 5>', '<Tanica da 26 con 16>']
['<Tanica da 5 con 5>', '<Tanica da 8 con 0>', '<Tanica da 13 con 5>', '<Tanica da 26 con 11>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 5>', '<Tanica da 13 con 5>', '<Tanica da 26 con 11>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 0>', '<Tanica da 13 con 10>', '<Tanica da 26 con 11>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 8>', '<Tanica da 13 con 2>', '<Tanica da 26 con 11>']
['<Tanica da 5 con 5>', '<Tanica da 8 con 3>', '<Tanica da 13 con 2>', '<Tanica da 26 con 11>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 3>', '<Tanica da 13 con 7>', '<Tanica da 26 con 11>']
['<Tanica da 5 con 3>', '<Tanica da 8 con 0>', '<Tanica da 13 con 7>', '<Tanica da 26 con 11>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 0>', '<Tanica da 13 con 7>', '<Tanica da 26 con 14>']
['<Tanica da 5 con 5>', '<Tanica da 8 con 0>', '<Tanica da 13 con 2>', '<Tanica da 26 con 14>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 5>', '<Tanica da 13 con 2>', '<Tanica da 26 con 14>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 0>', '<Tanica da 13 con 2>', '<Tanica da 26 con 19>']
['<Tanica da 5 con 2>', '<Tanica da 8 con 0>', '<Tanica da 13 con 0>', '<Tanica da 26 con 19>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 2>', '<Tanica da 13 con 0>', '<Tanica da 26 con 19>']
['<Tanica da 5 con 5>', '<Tanica da 8 con 2>', '<Tanica da 13 con 0>', '<Tanica da 26 con 14>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 7>', '<Tanica da 13 con 0>', '<Tanica da 26 con 14>']
['<Tanica da 5 con 5>', '<Tanica da 8 con 7>', '<Tanica da 13 con 0>', '<Tanica da 26 con 9>']
['<Tanica da 5 con 4>', '<Tanica da 8 con 8>', '<Tanica da 13 con 0>', '<Tanica da 26 con 9>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 8>', '<Tanica da 13 con 4>', '<Tanica da 26 con 9>']
['<Tanica da 5 con 5>', '<Tanica da 8 con 3>', '<Tanica da 13 con 4>', '<Tanica da 26 con 9>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 3>', '<Tanica da 13 con 9>', '<Tanica da 26 con 9>']
['<Tanica da 5 con 3>', '<Tanica da 8 con 0>', '<Tanica da 13 con 9>', '<Tanica da 26 con 9>']
['<Tanica da 5 con 5>', '<Tanica da 8 con 0>', '<Tanica da 13 con 9>', '<Tanica da 26 con 7>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 5>', '<Tanica da 13 con 9>', '<Tanica da 26 con 7>']
['<Tanica da 5 con 5>', '<Tanica da 8 con 5>', '<Tanica da 13 con 4>', '<Tanica da 26 con 7>']
['<Tanica da 5 con 2>', '<Tanica da 8 con 8>', '<Tanica da 13 con 4>', '<Tanica da 26 con 7>']
['<Tanica da 5 con 2>', '<Tanica da 8 con 0>', '<Tanica da 13 con 12>', '<Tanica da 26 con 7>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 2>', '<Tanica da 13 con 12>', '<Tanica da 26 con 7>']
['<Tanica da 5 con 5>', '<Tanica da 8 con 2>', '<Tanica da 13 con 7>', '<Tanica da 26 con 7>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 7>', '<Tanica da 13 con 7>', '<Tanica da 26 con 7>']

Il codice del programma Python è questo:
Codice:

class Tanica(object):
    def __init__(self, capacita, litri=0):
        self.capacita = capacita
        self.litri = litri

    def capacita_residua(self):
        return self.capacita - self.litri

    def __eq__(self, tanica):
        return self.capacita == tanica.capacita and self.litri == tanica.litri

    def versa_in(self, tanica, litri=None):
        if litri == None:
            litri = min(tanica.capacita_residua(), self.litri)
        self.litri -= litri
        tanica.litri += litri
        return litri

    def __repr__(self):
        return "<Tanica da %d con %d>" % (self.capacita, self.litri)

def esplora(situazione, risultato, massimo, mosse = []):
    if len(mosse) > massimo:
        return massimo
    if situazione == risultato:
        print "*" * 40
        print "In %d mosse" % len(mosse)
        for mossa in mosse:
            print mossa
        return len(mosse)
    else:
        for prima in range(len(situazione)):
            for seconda in range(len(situazione)):
                if prima != seconda and situazione[prima].litri > 0 and situazione[seconda].capacita_residua > 0:
                    litri = situazione[prima].versa_in(situazione[seconda])
                    mossa = str([str(tanica) for tanica in situazione])
                    if not mossa in mosse:
                        mosse.append(str([str(tanica) for tanica in situazione]))
                        massimo = esplora(situazione, risultato, massimo, mosse)
                        mosse.pop()
                    litri = situazione[seconda].versa_in(situazione[prima], litri)
        return massimo

max_mosse = 50
taniche = [Tanica(5), Tanica(8, 8), Tanica(13, 13), Tanica(26)]
risultato = [Tanica(5, 0), Tanica(8, 7), Tanica(13, 7), Tanica(26, 7)]
print "=" * 20
print "Da\t%s\nA\t%s" % (taniche, risultato)
print "In massimo %d mosse" % max_mosse
esplora (taniche, risultato, max_mosse)
Top
Profilo Invia messaggio privato
Taifu
Semidio
Semidio


Registrato: 24/10/06 10:13
Messaggi: 203

MessaggioInviato: 18 Gen 2007 15:58    Oggetto: Rispondi citando

Siamo a 42 mosse.

Sono curioso di vedere fino a dove scende...
Top
Profilo Invia messaggio privato
Taifu
Semidio
Semidio


Registrato: 24/10/06 10:13
Messaggi: 203

MessaggioInviato: 18 Gen 2007 16:20    Oggetto: Rispondi citando

41...

E mi sa che oltre non scende.
Top
Profilo Invia messaggio privato
Taifu
Semidio
Semidio


Registrato: 24/10/06 10:13
Messaggi: 203

MessaggioInviato: 18 Gen 2007 16:34    Oggetto: Rispondi

E mi "sapeva" male.

39
Top
Profilo Invia messaggio privato
Mostra prima i messaggi di:   
Nuovo argomento   Rispondi    Indice del forum -> Enigmi e giochi matematici Tutti i fusi orari sono GMT + 1 ora
Vai a 1, 2, 3  Successivo
Pagina 1 di 3

 
Vai a:  
Non puoi inserire nuovi argomenti
Non puoi rispondere a nessun argomento
Non puoi modificare i tuoi messaggi
Non puoi cancellare i tuoi messaggi
Non puoi votare nei sondaggi