Creato da tanksgodisfriday il 26/03/2006
Cose varie al PC, sul Web e nella mente. Puoi scrivermi a: tanksgodisfriday@libero.it
|
« Archive.org: un sito per... | Borseggiatori a rovescio » |
Ponti e attraversamenti offrono spunti per molti problemi di logica.Il più famoso è sicuramente quello dei ponti di Königsberg, proposto e studiato intorno nel 1736 dal matematico svizzero Leonhard Eulero, inaugurando la teoria dei grafi: una citta tedesca, Königsberg (stra-famosa, anche perché vi nacque il filosofo Immanuel Kant), sette ponti che collegano le sponde delle varie diramazioni del fiume che l'attraversa; domanda: esiste un percorso ininterrotto, passando per tutti ponti, ma una volta sola per ognuno? Eulero dimostrò che non era possibile. Il problema è parente stretto del giochino che avremo fatto tutti alle elementari: percorrere il disegno in basso nella figura, senza sollevare la penna dal foglio. Un percorso, a differenza del caso precedente, esiste. Altri percorsi simili si trovano in un mio vecchio post. Altro problema arcinoto è quello del contadino che deve traghettare da una sponda all'altra di un fiume, uno alla volta, un lupo, un agnello e un cavolfiore. Se lasciato solo con l'agnello, il lupo se lo pappa, e lo stesso fa l'agnello con il cavolfiore. In quale ordine vanno portati i tre da una parte all'altra? Terzo problema, che trovo molto bello. Meno noto, se ne trova una versione in inglese sul sito della università americana dello Utah. Quattro persone devono attraversare un ponte. È buio pesto, e i quattro hanno a disposizione una sola pila per illuminare il tragitto. In più, il ponte non è dei più solidi, e possono attraversarlo al massimo due persone per volta. I quattro camminano a velocità diverse: A. da solo impiegherebbe 1 minuto, per B. ce ne vogliono 2, a C. 5, infine a D. addirittura 10. Occorre trovare una sequenza fatta di: due persone che attraversano il ponte, una torna indietro con la pila, e così via. È possibile farcela in 17 minuti totali, ma non è semplicissimo. Buon fine settimana. |
La URL per il Trackback di questo messaggio è:
https://gold.libero.it/elaborando/trackback.php?msg=7580375
I blog che hanno inviato un Trackback a questo messaggio:
https://gold.libero.it/elaborando/trackback.php?msg=7580375
I blog che hanno inviato un Trackback a questo messaggio:
Nessun trackback
Gli Ospiti sono gli utenti non iscritti alla Community di Libero.
Area personale
- Login
Ultimi commenti
Grazie, Maria!
Un abbraccio.
Inviato da: tanksgodisfriday
il 17/01/2023 alle 18:30
Visitato il nuovo sito. Come sempre interessante e...
Inviato da: Fajr
il 17/01/2023 alle 17:14
Ho visitato il sito, è carino....peccato che non si può...
Inviato da: Mr.Loto
il 07/01/2023 alle 18:09
In realtà, "mi tawa" significa "io mi...
Inviato da: Marco Rossi
il 18/08/2019 alle 21:27
Tanti auguri di buone feste da kepago
Inviato da: amandaclark82
il 30/12/2016 alle 15:48
Inviato da: tanksgodisfriday
il 17/01/2023 alle 18:30
Inviato da: Fajr
il 17/01/2023 alle 17:14
Inviato da: Mr.Loto
il 07/01/2023 alle 18:09
Inviato da: Marco Rossi
il 18/08/2019 alle 21:27
Inviato da: amandaclark82
il 30/12/2016 alle 15:48
- trovare la soluzione e' difficile perche' viene naturale assumere come mossa elementare una sequenza del tipo X e Y attraversano, poi X o Y torna indietro, senza considerare lo stato (che permette ad esempio a T di tornare indietro)
- il problema e' simmetrico: se una sequenza di passi fa attraversare il ponte in un certo tempo da sinistra a destra, la sequenza rovesciata lo attraversa nello stesso tempo da destra a sinistra. quindi se si trova una soluzione "minima", anche la sua inversa e' ancora una soluzione minima
- [tecnica] se uno volesse risolvere il problema usando la forza bruta di un programma per calcolatore (magari aumentando il numero di persone), basterebbe tenere presente che quando nessuno sta attraversando lo stato e' definito dal sottoinsieme delle persone che sono a sinistra del ponte (con n persone ci sono 2^n stati possibili, ad esempio con 4 sono 16) e il problema si riduce a trovare i percorsi di costo minimo tra i nodi 0000 e 1111 in un grafo in cui nodi sono i vari stati possibili e gli archi tra i nodi sono etichettati con un costo pari al tempo di attraversamento per passare da uno stato all'altro (infinito se non e' possibile passare dall'uno all'altro)
ciao -- peppe
Non avevo fatto caso alla simmetria del problema; molto interessante. Chissà se consente di semplificare il programma.
Ciao!