Torre De Hanoi
Páginas: 4 (781 palabras)
Publicado: 23 de mayo de 2012
TORRE DE HANÓI
Las Torres de Hanói es un juego matemático inventado en 1883 por el matemático francés Éduard Lucas.1 Este solitario se trata de un juego de ocho discos de radiocreciente que se apilan insertándose en una de las tres estacas de un tablero. El objetivo del juego es crear la pila en otra de las estacas siguiendo unas ciertas reglas. El problema es muy conocido enla ciencia de la computación y aparece en muchos libros de texto como introducción a la teoría de algoritmos.
Análisis del juego
Llamaremos THn a un juego de la Torre de Hanoi de n discos.Llamaremos postes a las agujas de diamante o a los clavos en los que se insertan los discos. En el poste A, el de la izquierda, están insertados todos los discos al principio del juego y queremos mover latorre al poste C, el de la derecha. El poste B, el central, nos servirá de ayuda para depositar temporalmente algunos discos a lo largo del procedimiento. Llamaremos Mn al mínimo número de movimientosnecesarios para solucionar THn. Consideraremos ordenados los discos de menor a mayor radio, de forma que el disco 1 es el más pequeño, el disco 2 el siguiente y, así, el disco n será el más grande y, portanto, el que reposa en la base del juego.
Es claro que si n=1 entonces M(1)=1, pues basta desplazar el único disco del juego desde el poste A hasta el poste C. Si n=2, entonces hay que trasladarel primer disco hasta B, el segundo hasta C y, finalmente, el tercero hasta C. Por tanto, M(2)=3. Si n=3, entonces hay que trasladar los dos primeros discos hasta B, lo que requerirá M(2)=3movimientos; luego el tercer disco hasta C y, finalmente, los dos discos pequeños desde B hasta C, lo que aporta otros M(2)=3 movimientos. Por tanto, M(3)=2M(2)+1=7. Como también M(2)=2M(1)+1, postulamos que,en general, se cumple que M(n)=2M(n-1)+1
La expresión anterior es una recurrencia. Busquemos ahora una fórmula explícita. Dado que M(1)=1=2^1-1, M(2)=3=2^2-1, M(3)=7=2^3-1, podemos postular...
Las Torres de Hanói es un juego matemático inventado en 1883 por el matemático francés Éduard Lucas.1 Este solitario se trata de un juego de ocho discos de radiocreciente que se apilan insertándose en una de las tres estacas de un tablero. El objetivo del juego es crear la pila en otra de las estacas siguiendo unas ciertas reglas. El problema es muy conocido enla ciencia de la computación y aparece en muchos libros de texto como introducción a la teoría de algoritmos.
Análisis del juego
Llamaremos THn a un juego de la Torre de Hanoi de n discos.Llamaremos postes a las agujas de diamante o a los clavos en los que se insertan los discos. En el poste A, el de la izquierda, están insertados todos los discos al principio del juego y queremos mover latorre al poste C, el de la derecha. El poste B, el central, nos servirá de ayuda para depositar temporalmente algunos discos a lo largo del procedimiento. Llamaremos Mn al mínimo número de movimientosnecesarios para solucionar THn. Consideraremos ordenados los discos de menor a mayor radio, de forma que el disco 1 es el más pequeño, el disco 2 el siguiente y, así, el disco n será el más grande y, portanto, el que reposa en la base del juego.
Es claro que si n=1 entonces M(1)=1, pues basta desplazar el único disco del juego desde el poste A hasta el poste C. Si n=2, entonces hay que trasladarel primer disco hasta B, el segundo hasta C y, finalmente, el tercero hasta C. Por tanto, M(2)=3. Si n=3, entonces hay que trasladar los dos primeros discos hasta B, lo que requerirá M(2)=3movimientos; luego el tercer disco hasta C y, finalmente, los dos discos pequeños desde B hasta C, lo que aporta otros M(2)=3 movimientos. Por tanto, M(3)=2M(2)+1=7. Como también M(2)=2M(1)+1, postulamos que,en general, se cumple que M(n)=2M(n-1)+1
La expresión anterior es una recurrencia. Busquemos ahora una fórmula explícita. Dado que M(1)=1=2^1-1, M(2)=3=2^2-1, M(3)=7=2^3-1, podemos postular...
Leer documento completo
Regístrate para leer el documento completo.