Upload
diana2504
View
374
Download
9
Embed Size (px)
Citation preview
Torres de Hanói
Realizado Por:Romero Diana
Republica Bolivariana de Venezuela
I.U.P. Santiago MariñoExtensión Maturín
Reseña Histórica
Por que Hanói?
Explicación
El juego consiste en pasar todos los discos del poste ocupad, es decir, la que posee la torre de discos, a una de los otros postes vacantes. Para realizar este objetivo, es necesario seguir tres simples reglas:
1) Sólo se puede mover un disco cada vez.
2) Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo.
3) Sólo puedes desplazar el disco que se encuentre arriba en cada varilla
El juego de las Torres de Hanói consiste en tres postes que serán indicados con las letras A, B y C, por lo general de izquierda a derecha, aunque el orden realmente no importa, es solo para poder referirnos a cada uno de los postes. El juego clásico contiene todos los discos en el poste A, estos son apilados en orden según su tamaño, estando el de radio mayor en la base de nuestra torre. Sabiendo que el disco 1 será el de la punta de la torre.
Explicación
Reglas del JuegoLas reglas del juego son las siguientes:
1) Sólo se puede mover un disco cada vez.2) Para cambiar los discos de lugar se pueden usar las tres columnas del juego; es decir que los distintos discos se pueden ir acomodando en las columnas según convenga.3) Nunca deberá quedar un disco grande sobre un disco chico.
Sugerencias para jugar mejor:
a) Primero inténtalo con dos discos. ¿Cuántos movimientos hiciste para terminar el juego?b) Ahora ve aumentando discos y ve jugando con 3 discos, con 4, con 5, etcétera. ¿Cuántos movimientos se necesitan para cada número de discos?
Hanói Si ya jugaste el juego, te habrás dado cuenta de
que el número de movimientos que hacen falta para terminarlo crece de manera muy rápida conforme vamos aumentando discos. De hecho, crece de manera exponencial.Así:
Solución Algorítmica
Una forma de resolver la colocación de la torre es
fundamentándose en el disco más pequeño, en este caso el de hasta arriba. El movimiento inicial de este es hacia la varilla auxiliar.
El disco número dos por regla, se debe mover a la varilla número tres. Luego; el disco uno se mueve a la varilla tres para que quede sobre el disco dos. A continuación se mueve el disco que sigue de la varilla uno, en este caso el disco número tres, y se coloca en la varilla dos. Finalmente el disco número uno regresa de la varilla tres a la uno (sin pasar por la dos) y así sucesivamente.
Es decir, el truco está en el disco más pequeño
Este problema se suele plantear a menudo en ámbitos de programación, especialmente para explicar la recursividad. Si numeramos los discos desde 1 hasta n, y llamamos X a la primera pila de discos (origen), Z a la tercera (destino) e Y a la intermedia (auxiliar) y a la función le llamaríamos Hanói (origen, auxiliar, destino), como parámetros, la función recibiría las pilas de discos. El algoritmo de la función sería el siguiente:Si origen == {0}: mover el disco 1 de pila origen a la pila destino (insertarlo arriba de la pila destino); terminar.Si no: Hanói({0...n-1},destino, auxiliar) //mover todas las fichas menos la más grande (n) a la varilla auxiliarmover disco n a destino //mover la ficha grande hasta la varilla finalHanói (auxiliar, origen, destino) //mover todas las fichas restantes, {0...n-1}, encima de la ficha grande (n)terminar
Mediante recursividad
Fin del Juego