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: 21 Gen 2007 19:37    Oggetto: Rispondi citando

Taifu ha scritto:
Essendomi stufato di aspettare, ho interrotto il programma ancora fermo ad esplorare l'albero delle 27 mosse e ho ripensato completamente l'algoritmo passando da una versione a forza "brutta" ad una realmente a forza bruta.
Adesso, con un leggerissimo fattore di miglioramento, in 87 centesimi di secondo ho trovato una soluzione in 16 mosse.
Mi sono dato per metà dell'asino per non averci pensato prima e per metà mi sono beato del programmino...

Per gli uomini di buona volontà questa è la nuova versione:

P.S. Il codice non è commentato ma sono assolutamente disponibile a spiegarlo riga per riga a chi me lo chiedesse.


Ti prendo in parola e chiedo spiegazioni.
Prima, però, sottopongo a conferma quello che penso di aver capito.

Entrambi gli algoritmi partono da un nodo (una configurazione delle taniche) e provano a fare tutti i travasi possibili tra i 12 formalmente eseguibili, verificano se il nodo al quale ognuno di essi conduce è già presente nell'albero (segno inequivocabile che l'algoritmo è già passato da quel nodo in precedenza) e, in caso non lo sia lo aggiungono all'albero.
Questo sino a che il nodo raggiunto non coincide con quello finale richiesto dal problema.

Il primo algoritmo però è ricorsivo-condizionale: la ricorsione viene eseguita solo se il nuovo nodo raggiunto non è ancora censito nell'albero; viceversa la ricorsione si chiude.

La condizione di uscita dalla ricorsione è data o dal raggiungimento della soluzione o dal raggiungimento della massima profondità dell'albero (prevista a priori fuori dal programma).

Quando l'algoritmo esce da una ricorsione, risale l'albero a ritroso (ogni uscita dalla ricorsione è un passo indietro) fino a che non ritorna ad un nodo che non ha finito di esplorare.

Ciò vuol dire, sostanzialmente, che l'algoritmo gironzola sistematicamente per tutto l'albero fino a che non trova una soluzione.

Il secondo algoritmo, invece, è composto da due parti.
La prima è iterativa (ciclo while) e scrive sistematicamente l'albero a partire dal nodo iniziale indicato dal problema.
L'uscita dal ciclo while avviene solo quando l'ultimo ciclo eseguito non è stato in grado di aggiungere nuovi nodi all'albero.
Poi l'algoritmo,o dopo aver scritto tutto l'albero, controlla se la soluzione è presente tra i nodi individuati.

In più rispetto al primo algoritmo, il secondo tiene anche traccia, per ogni nodo, del numero di passi necessari al suo raggiungimento.

Fermo restando che abbia analizzato correttamente ed esaustivamente gli algoritmi, non riesco a capire cosa determini l'efficienza del secondo.
Top
Profilo Invia messaggio privato HomePage
Taifu
Semidio
Semidio


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

MessaggioInviato: 21 Gen 2007 23:01    Oggetto: Rispondi citando

ulisse ha scritto:
Ti prendo in parola e chiedo spiegazioni.
Prima, però, sottopongo a conferma quello che penso di aver capito.
...
Fermo restando che abbia analizzato correttamente ed esaustivamente gli algoritmi, non riesco a capire cosa determini l'efficienza del secondo.


Innanzitutto hai capito e interpretato perfettamente entrambi gli algoritmi.
Ti faccio i miei più sinceri complimenti! Applause

Detto ciò, siccome io capisco di più così, provo a spiegarmi con un esempio.
Immaginiamo un grafo di possibilità siffatto:
Codice:

  B---E--F
 / \ /
A   D--G
 \ /
  C


Dove A è il punto di partenza, B, C, D ed E sono nodi intermedi, F e G sono delle possibili configurazioni finali.

Vediamo come esplorano l'albero i due algoritmi:
Codice:

Primo algoritmo:
ABEF   3
ABEDG  4
ABEDC  4
ABDEF  4
ABDG   3
ABDC   3
ACDBEF 5
ACDEF  4
ACDG   3

Secondo algoritmo:
AB    1
AC    1
 BE   2
 BD   2
  EF  3
  DG  3


Il primo percorre gli stessi segmenti più volte per il solo fatto che vi giunge attraverso cammini diversi sprecando così un sacco di tempo inutilmente. Il segmento EF varrà sempre 1 sia che arrivo da AB sia che arrivo da ACD: inutile calcolarlo due volte.

Il secondo invece si allarga a "macchia d'olio" individuando subito i cammini più rapidi verso ogni nodo. In questo modo, in maniera molto più rapida, esploro subito ogni possibile punto del grafo e posso permettermi di non dare nessuna profondità massima. Inoltre posso rispondere a domande come "quante sono le configurazioni raggiungibili?", "quanto è distante la più lontana" etc. etc.

E` chiaro che, per un grafo così poco profondo (o per un problema di tre taniche) i tempi dei due algoritmi sono comunque accettabili (pochi secondi contro pochi centesimi). Con un grafo molto più profondo (o per un problema di quattro o più taniche) allora le cose cambiano.

Visti i tempi, con la seconda versione posso permettermi di scoprire dei problemi tosti. Magari provare a individuare il problema a tre taniche minori di 10 litri con la profondità maggiore... Wink

Spero (ma non credo) di essermi spiegato meglio. Se così non fosse ti prego di dirmelo perchè ci tengo a ricambiare, almeno in parte, il tempo che hai dedicato ai due algoritmi.

Ciao.
Marco.
Top
Profilo Invia messaggio privato
Taifu
Semidio
Semidio


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

MessaggioInviato: 22 Gen 2007 01:58    Oggetto: Rispondi citando

Detto, fatto!

Questo è il più "lungo" con taniche di massimo 8 litri:
Partenza (4,4) - (5,0) - (8,4)
Arrivo (4,0) - (5,2) - (8,6)

Vi interessa sapere qual'è il più lungo in assoluto con taniche più capienti?

Ciao.
Marco.
Top
Profilo Invia messaggio privato
Taifu
Semidio
Semidio


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

MessaggioInviato: 22 Gen 2007 08:37    Oggetto: Rispondi citando

Per risolvere questo servono un bel po' di mosse:

Da (9,0) - (13,4) - (14,14)
A (9,9) - (13,2) - (14,7).

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


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

MessaggioInviato: 22 Gen 2007 10:13    Oggetto: Rispondi citando

Taifu ha scritto:
Innanzitutto hai capito e interpretato perfettamente entrambi gli algoritmi.
Ti faccio i miei più sinceri complimenti! Applause

Non era difficile: sono scritti bene!
L'unica difficoltà è nelle istruzioni specifiche di Python e nella comprensione delle variabili per le quali, deduco, Python non impone la dichiarazione.
Ma con un po' di immaginazione ci si arriva.

Ciò che non doveva sfuggirmi, invece, era l'interpretazione!

Ora è chiaro.
Pensando ai cuccioli che giorno per giorno esplorano il territorio circostante la tana.
Il primo algoritmo li farebbe partire radialmente: corro corro corro...
Il secondo, invece, li farebbe muovere a spirale con raggi sempre più grandi: giro giro giro...
Per la cronaca, i cuccioli usano il secondo algoritmo!

Ottima strategia! Ora che ho capito posso confermare che la seconda strategia è decisamente più efficiente!

Mi chiedo se sono possibili ottimizzazioni.
Ci rifletterò un pochetto. Se mi riesce provo a imbastire un programmino anch'io (lavorerò in VBA, però, che conosco già. Anche se ho visto che Python non è per nulla difficile).

Grazie per le spiegazioni chiare e illuminanti.
Hai mai pensato di darti all'insegnamento? (lo dico seriamente)

Chiudo con qualche domandina specifica di Python

Ma le variabili non si dichiarano?
A cosa serve il metodo (si chiama così, vero?) __EQ__ ?
Lo inserisci per completezza o è indispensabile dichiararlo?

Un'ultima cosa. Secondo me c'è uno sfrido nel codice: la prima istruzione del ciclo while ( aggiunto = False )
Top
Profilo Invia messaggio privato HomePage
Taifu
Semidio
Semidio


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

MessaggioInviato: 22 Gen 2007 11:33    Oggetto: Rispondi citando

ulisse ha scritto:
Grazie per le spiegazioni chiare e illuminanti.


Prego, prego. Dovere Smile

ulisse ha scritto:
Hai mai pensato di darti all'insegnamento? (lo dico seriamente)


Urka! Detto da te questo è davvero un bel complimento! Grazie!
In realtà per due settimane molti anni fa ho insegnato matematica al mio vecchio liceo e ricordo ancora lo stress dei momenti prima di entrare in classe. Ricordi a parte ho già 42 anni e oramai la mia strada lavorativa è già tracciata almeno per un po' di anni. Per ora il mio sforzo "insegnativo" è dedicato ai miei due figli. Poi si vedrà Smile

ulisse ha scritto:
Chiudo con qualche domandina specifica di Python
Ma le variabili non si dichiarano?


No. Però se usi una variabile senza averla dichiarata otterrai un'eccezione. Python è un linguaggio a forte tipizzazione dinamica. E` assolutamente eccezionale in questo.

Ti consiglio di dedicare un'oretta al tutorial di Python: io ci sono cascato così anni fa e da allora lo uso e diffondo a più non posso (il dominio www.python.it fu registrato da me tempo fa e il sito è ospitato gratuitamente nella azienda in cui lavoro). Tieni conto che ho usato nella mia vita lavorativa almeno una quindicina di linguaggi (e ne ho studiati altri quattro o cinque) per cui se ti dico che per me è di gran lunga il miglior linguaggio di programmazione esistente, lo dico a ragion veduta (ripeto: parere personale ovviamente).
Il tutoral in inglese: http://www.python.org/doc/tut/
Il tutoral in italiano: http://www.python.it/doc/Python-Docs/html/tut/tut.html

ulisse ha scritto:
A cosa serve il metodo (si chiama così, vero?) __EQ__ ?
Lo inserisci per completezza o è indispensabile dichiararlo?


Due istanze di una classe normalmente non sono confrontabili perchè vengono, giustamente, ritenute diverse dal linguaggio in quanto oggetti distinti. Definendo il metodo __eq__ posso dire a Python cosa deve fare per considerare uguali due oggetti. Per esempio con il codice seguente stabilisco che due taniche sono uguali se hanno stessa capacità e stessa quantità di acqua:
Codice:

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


Se non lo definisco nel seguente codice l'ultimo test ritornerebbe False:
Codice:

a = Tanica(5, 3)
b = Tanica(5, 3)
a == b


ulisse ha scritto:
Un'ultima cosa. Secondo me c'è uno sfrido nel codice: la prima istruzione del ciclo while ( aggiunto = False )


Bellissima la definizione di sfrido: mi piace!
Sì, è chiaramente uno sfrido. Solo in un secondo momento mi sono accorto di poter usare last e nextLast come condizione di uscita ma mi sono dimenticato di togliere l'assegnamento della variabile "aggiunto".

Hai mai pensato di dedicarti alla programmazione? Laughing Laughing Laughing

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


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

MessaggioInviato: 22 Gen 2007 12:45    Oggetto: Rispondi citando

Taifu ha scritto:
Urka! Detto da te questo è davvero un bel complimento! Grazie!

L'ho detto perché si vede che provi piacere nel "travasare" (visto che parliamo di taniche!) le tue competenze.

Taifu ha scritto:
Python è un linguaggio a forte tipizzazione dinamica.
Ohi! Mi serve una traduzione!

Taifu ha scritto:
Ti consiglio di dedicare un'oretta al tutorial di Python: io ci sono cascato così anni fa e da allora lo uso e diffondo a più non posso (il dominio www.python.it fu registrato da me tempo fa e il sito è ospitato gratuitamente nella azienda in cui lavoro).

Ma dai! Sto parlando al signor Python.it in persona! Evviva

Taifu ha scritto:
Due istanze di una classe normalmente non sono confrontabili perchè vengono, giustamente, ritenute diverse dal linguaggio in quanto oggetti distinti.

Eh, si. Quando definisci un nuovo insieme di oggetti devi definire anche le operazioni che puoi eseguire con essi altrimenti il pc che ne sa? Embarassed

La verità è che avevo cercato dove, nel codice, facessi uso dell'operatore == non trovandolo. Che idiota! Ho cercato l'operatore "uguale" ma non l'operatore "diverso" !!!

Taifu ha scritto:
Bellissima la definizione di sfrido: mi piace!

Eheh. Chi pensa che sia nato con carta e matita in mano si sbaglia!
Mio padre lavorava in fabbrica e io mi divertivo a rompere le scatole ai suoi operai con tremila domande del tipo "cos'è questo?" "cos'è quello?" "come funziona?" "a cosa serve?" e quindi prima di dire "radice quadrata" ho imparato a dire "sfrido" ! Very Happy Very Happy Very Happy
Citazione:
Hai mai pensato di dedicarti alla programmazione?

Eheheh. Che fai, ricambi le lusinghe? Wink
Dedicarmi interamente no.
Non credo potrei mai svolgere una singola attività a tempo pieno. Mi annoierei dopo un giorno.
La programmazione è uno dei miei hobbies (come hai notato se ti sei scaricato i miei programmini postati nel forum), è anche uno dei miei lavori (sviluppo software gestionale) e una delle materie di insegnamento (tengo un piccolo corso - veramente all'acqua di rose - di algoritmi di teoria dei numeri).
Top
Profilo Invia messaggio privato HomePage
Taifu
Semidio
Semidio


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

MessaggioInviato: 23 Gen 2007 01:16    Oggetto: Rispondi citando

ulisse ha scritto:
Taifu ha scritto:
Python è un linguaggio a forte tipizzazione dinamica.
Ohi! Mi serve una traduzione!


Tipizzazione statica: il programmatore deve dichiarare prima le variabili.

Tipizzazione dinamica: il programmatore non deve dichiarare prima le variabili.

Tipizzazione forte: (qui uso un esempio) il programmatore non può sommare tra di loro variabili di tipo diverso (per esempio una stringa ad un numero come si può fare in javascript) senza convertire esplicitamente una delle due variabili.

Tipizzazione debole: il contrario della precedente... Smile

Python unisce il meglio: forte tipizzazione dinamica.

Inoltre previene la stragrande maggioranza degli errori in questo campo impedendoti di usare una variabile non inizializzata.

Ciao.
Marco.
Top
Profilo Invia messaggio privato
Taifu
Semidio
Semidio


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

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

[quote="ulisse"]Eheh. Chi pensa che sia nato con carta e matita in mano si sbaglia!
Mio padre lavorava in fabbrica e io mi divertivo a rompere le scatole ai suoi operai con tremila domande del tipo "cos'è questo?" "cos'è quello?" "come funziona?" "a cosa serve?" e quindi prima di dire "radice quadrata" ho imparato a dire "sfrido" ! Very Happy Very Happy Very Happy
[quote]

Dimenticavo, anche io conosco il significato del termine sfrido per lo stesso tuo motivo: anche mio padre ha lavorato in fabbrica. Solo che io le scatole le rompevo a lui e non ai suoi operai... Smile

Ciao.
Marco.
Top
Profilo Invia messaggio privato
Taifu
Semidio
Semidio


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

MessaggioInviato: 25 Gen 2007 11:15    Oggetto: Rispondi

Taifu ha scritto:
Siccome non credo che tutti leggeranno sino in fondo, aggiungo subito alcuni nuovi sotto-indovinelli per il problema delle quattro taniche:
1) quante sono le differenti configurazioni raggiungibili dalla partenza 0/8/13/0 ?
2) quanto è distante la configurazione più lontana dal punto di partenza ?
3) e quante sono?
4) e quali sono? (ne basta una)


Ok, visto il grande interesse, vi do le risposte Laughing

Citazione:

1) 395
2) 17
3) 4
4) 5/1/1/14 , 1/6/0/14 , 1/1/0/19 , 0/1/1/19
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 Precedente  1, 2, 3, 4, 5  Successivo
Pagina 4 di 5

 
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