¿Cómo jugar a la Torre de Hanoi?
Un erudito estadounidense descubrió un método particularmente simple: simplemente use el siguiente método dos veces por turno.
Organiza las tres columnas en forma de "aguja", coloca todos los discos en la columna A en orden descendente y determina el orden de las columnas según el número de discos:
Si n es un número par, entonces se colocará en el sentido de las agujas del reloj de la siguiente manera: ABC si n es un número impar, se colocará en el sentido de las agujas del reloj como: ACB; Después de repetidas pruebas de esta manera, el movimiento de la Torre de Hanoi se puede completar de acuerdo con las regulaciones.
Así que es muy sencillo. El resultado es mover la pepita de oro en una dirección según las reglas de movimiento:
Por ejemplo, el movimiento de la torre de tres pisos en Hanoi. : A → C, A → B, C → B , A → C, B → A, B → A, B → C, A → C.
Datos ampliados:
Tema clásico de la Torre de Hanoi:
Tres columnas adyacentes, numeradas A, B, C, A, de abajo hacia arriba Usa N discos de diferentes tamaños para formar una forma de pirámide. Todos los discos deben moverse a la columna B uno por uno, y no se permite que el disco grande esté encima del disco pequeño cada vez que se mueve la misma columna.
Necesitamos movernos al menos unas cuantas veces, sea H(n) el número de movimientos.
Mueve los n-1 tableros de arriba a la columna C, coloca el más grande en B, y mueve todos los tableros de C a B, obteniendo así la expresión:
H⑴ = 1
H(n)= 2 * H(n-1)+1(n & gt; 1)
Pronto podremos obtener H( La fórmula general de n):
2^n-1(n>0)
Y este método es de hecho el menos frecuente. La prueba es muy simple. Puedes intentar comenzar desde dos El movimiento del bloque. El tablero ha comenzado, puedes intentarlo.
Desarrollo adicional del problema:
Si hay dos placas de cada tamaño y son adyacentes, entonces el número de placas es 2n. Pregunta: (1) Si no considera cuántas veces es necesario mover placas del mismo tamaño hacia arriba y hacia abajo, sea j(n) el número de movimientos (2) Siempre que el orden del mismo tamaño; Las placas en la última B son las mismas que el orden en la última A, es necesario cuántas veces moverse, el número de movimientos es K (n).
(1) El movimiento equivale a mover cada placa nuevamente en la pregunta anterior, es decir:
j(n)= 2 * h(n)= 2*( 2^ n-1)= 2^(n+1)-2
Antes de analizar [2], primero expliquemos un fenómeno. Si hay dos placas del mismo tamaño en la columna A, la superior es negra y la inferior es blanca, debemos mover las dos placas a la columna B dos veces.
El orden de las placas se volverá negro en la parte inferior y blanco en la parte superior. Luego, la placa de B se moverá dos veces a C. El orden de las placas será el mismo que en A. De esto, podemos concluir que incluso si dos placas adyacentes se mueven varias veces, el orden de las placas no cambiará, de lo contrario se invertirá.
Volviendo a la pregunta original, cuando se mueven n discos, el número total de movimientos del n-1 disco anterior es 2*H(n-1), por lo que el número de movimientos del n- 1 disco de arriba debe ser un número par. La última placa debe ser 1.
Pregunta de discusión (2):
En resumen, se puede concluir que las 2n placas de A deben moverse a B. Se puede concluir que las 2n-2 anteriores las placas deben moverse un número par de veces, por lo que el orden permanece sin cambios. El número de movimientos es:
J(n-1) = 2^n-2
Entonces el. penúltimo El tablero se mueve 2 * j(n-1)+1 = 2(n+1)-3.
La placa base se mueve en último lugar, por lo que el número total de movimientos es:
k(n)= 2 *(2 * j(n-1)+1)+1 = 2*(2^ (n+1)-3)+1 = 2^(n+2)-5
Referencia:
Torre de Hanoi (juguete educativo)- Enciclopedia Baidu
p>