Newsgroup: it.hobby.enigmi
Titolo: Torre di Hanoi

Non e' un enigma, ma una richiesta.
Come tutti saprete, il rompicapo della Torre di Hanoi puo' essere
risolto facilmente dal calcolatore usando una funzione ricorsiva
(peraltro anche abbastanza semplice da definire ed implementare).
Qualcuno pero' puo' indicarmi se esiste anche una soluzione analitica
(che non fa uso della ricorsione)? E se esiste (cosa molto probabile),
come funziona?
Grazie a tutti
Bye by Massimo 8-]

 risolto facilmente dal calcolatore usando una funzione ricorsiva
Scusa, ma come funziona questo rompicapo??
Claudio
---------------------------------
http://web.tiscalinet.it/anais/anais.htm

 Qualcuno pero' puo' indicarmi se esiste anche una soluzione analitica.
Non capisco bene cosa chiedi.
La Torre di Hanoi, e' un semplice gioco meccanico inventato nel 1883 dal
matematico francese Eduard Lucas.
n dischi di diametro crescente sono impilati su uno di tre perni, il
piu' piccolo sopra. Lo scopo del gioco e' trasferire tutta la pila in un
differente piolo, spostando un disco alla volta, e' proibito coprire un
disco con uno piu' grande.
Per induzione si trova subito che le mosse necessarie sono 2^n-1. Nel
racconto originale ambientato appunto un un tempio di Hanoi, i dischi
erano ben 64, le mosse necessarie sarebbero' 18.446.744.073.709.551.615.
La strategia e' semplicissima, Chiamiamo i tre pioli a,b,c con a pieno,
allora per ogni mossa dispari muovi il disco piu' piccolo
a,b,c,a,b,c,a,b,c....  alternando le mosse pari con l'unica legalmemte
possibile.
Moltissime varianti vendute, eccone alcune presenti nella mia raccolta:
The Crippled Mutant 
I dischi possono essere mossi solo su pioli adiacenti.
The Self Solving Mutant
I dischi sono colorati alternativamente, e 2 dischi dello stesso colore
non possono venire in contatto.
The Clock
dove i pioli sono in circolo e i dischi possono essere mossi solo in
senso orario.
The Patriot
I dischi sono colorati con 3 colori.
e molte altre....
:) dario

 come funziona?
Certo che è possibile, lo fa il compilatore stesso, quando traduce il
programma in un linguaggio eseguibile dal processore che, per la sua stessa
architettura e` una macchina sequenziale. In pratica e` sempre possibile
"sciogliere" la ricorsione implementando un stack, ovvero una struttura dati
che "immagazzini" lo stato della computazione al momento della chiamata,
compreso il punto dal quale si fa la chiamata. Poi basta sostituire le
chiamate ricorsive con aggiornamenti dello stack seguiti da salti all'inizio
della routine, ed i ritorni con ripristini della stato della computazione
seguiti da salti al punto successivo all'ultima chiamata.
Nel caso della torre di hanoi, mi pare che non si abbiano vantaggi in
termini di complessita` computazionale, perche` il problema e`
intrinsecamente esponenziale, mentre altre volte rinunciare all'elegante
ricorsione fa risparmiare un fracco di risorse.
Pensa al calcolo dei numeri di Fibonacci. La definizione stessa dei numeri
"suggerisce" un approccio ricorsivo, ma questo e` altamente inefficiente,
perche` per calcolare f(n+2) chiamo due volte f(n), con inutile complessita`
esponenziale. Un semplice approccio ricorsivo, partendo dal basso invece che
dall'alto, rende la complessita` lineare.
Ciao, Silv:o)

come funziona?
E' stato dimostrato che ogni algoritmo ricorsivo può essere trasformato in
uno iterativo.


...mi interessa assai...
Puoi mandarmi altri dettagli?
Ciao, Sandro.