¿Cuál es la fórmula del problema de la Torre de Hanoi?
Existen tres polos a, b y c. 1) Disco perforado, el tamaño del disco disminuye de abajo hacia arriba. Todos los discos deben moverse a la barra C de acuerdo con las siguientes reglas:
1. Solo se puede mover un disco a la vez;
2. platos pequeños.
Consejo: El disco se puede colocar temporalmente en el poste B, o el disco retirado del poste A se puede mover nuevamente al poste A, pero se deben seguir las dos reglas anteriores.
P: ¿Cómo moverse? ¿Cuántas veces tendré que mudarme?
Generalmente N=64. Esto requiere al menos 264-1 movimientos. En otras palabras, si un disco pudiera moverse en un segundo, aún tardaría 584.554 millones de años. Según la teoría del Big Bang, la edad del universo es de sólo 65.438+03.7 mil millones de años.
En juguetes reales, normalmente n = 8, esto requeriría 255 pasos. Si N=10, se requieren 1023 movimientos. Si N=15, se necesitan 32767 movimientos; es decir, si una persona mueve un disco todos los días desde los 3 hasta los 99 años, solo podrá mover 15 bloques. Si N = 20, es necesario moverlo 1048575 veces, que es más de un millón de veces.
Veamos primero la situación en Hanoi (1, 1, 2, 3). En este momento, mueva directamente una placa de una columna a tres columnas. Tenga en cuenta que no importa si una o tres columnas son A, B o C. Recuerde que el disco de la columna representada por el segundo parámetro de la función se mueve a la columna representada por el cuarto parámetro. Por conveniencia, esta operación se registra como:
Uno=》Tres
Veamos la situación en Hanoi (dos, uno, dos, tres). Teniendo en cuenta que se ha analizado la situación en Hanoi (1), se sabe que en realidad habrá tres acciones en este momento, a saber:
Uno=》Dos
Uno=》 Tres
Dos=》Tres
Obviamente, esto en realidad equivale a mover dos discos de una columna directamente a tres columnas.
Mira la situación en Hanoi (tres, uno, dos, tres). Análisis
Hanoi (dos, uno, tres, dos)
Uno=》tres
Hanoi (dos, dos, uno, tres)
Es decir, primero mueva dos discos de una columna a dos columnas, luego mueva un disco de una columna a tres columnas y, finalmente, mueva dos discos de dos columnas a tres columnas. ¿No es esto equivalente a mover tres discos de una columna directamente a tres columnas?
Por inducción sabemos que para cualquier n,
Hanoi (n-1, uno, tres, dos)
Uno=》tres
Hanoi (n-1, dos, uno, tres)
Es decir, primero mueva n-1 discos de una columna a dos columnas y luego mueva un disco de una columna a tres columnas. y finalmente mueva n-1 discos de dos columnas a tres columnas. ¡Este es el resultado que necesitamos!
Encuestado: Wu Chenghua 121-Gerente Nivel 4 12-5 11:51.
Hanoi
El problema de la Torre de Hanoi es una antigua leyenda en la India. Brahma, el dios de la creación, dejó tres barras de diamantes en un templo. El primero estaba cubierto con 64 piezas redondas de oro, la pieza más grande en la parte inferior y una más pequeña que la otra. Los monjes del templo se tomaron la molestia de moverlos de un palo a otro, estipulando que el palo del medio podía usarse como ayuda, pero sólo se podía mover uno a la vez, y el más grande no se podía colocar encima. encima del más pequeño. Calcule la solución usted mismo. Ver el final del espectáculo. Ante un número enorme (el número de veces que se mueve el disco) 1844674073709551615, parece imposible que los monjes pasen toda su vida completando el movimiento del disco de oro.
Más tarde, esta leyenda evolucionó hasta convertirse en el juego de la Torre de Hanoi:
1 Hay tres polos A, B, C, B, C. Hay algunas verduras en el polo A.
2. Mueve un plato a la vez, el más pequeño sólo se puede apilar encima del más grande.
3. Mueva todas las placas del polo A al polo c.
A través de investigaciones, se descubre que el agrietamiento de la Torre de Hanoi es muy simple, que consiste en mover la pepita de oro en una dirección según las reglas de movimiento:
Por ejemplo , el movimiento de la Torre de tres niveles en Hanoi: A → C , A → B, C → B, A → C, B → A, B → A, B → C, A → C.
Además, el problema de la Torre de Hanoi también es un problema de recursividad clásico en programación.
Suplemento: Implementación del algoritmo de la Torre de Hanoi (c++)
# include & ltfstream & gt
# include & ltiostream & gt
Usar el espacio de nombres estándar
de la secuencia fout(" out . txt ");
void Move(int n, char x, char y)
{
fout & lt& lt"bar"< & ltn & lt& lt"número de" < & ltx & lt& lt"movido a"
}
void Hannoi (int n, char a, char b, char c)
{
Si (n==1)
Mover(1, a, c ) ;
Otros
{
Hannoy(n-1, a, c, b
Mover(n , a,); c);
Hannoy (n-1, b, a, c);
}
}
int principal();
{
fout & lt& lt"La siguiente es la solución a la pagoda de siete pisos en Hanoi:"
Hannoi(7,' a ', ' b ', ' c ');
fout .
cout & lt& lt"¡Salida completada!" ;
}
Algoritmo simplificado en lenguaje C
/* Titular de los derechos de autor SS7E*/
# include & ltstdio.h & gt / * Propietario de los derechos de autor de SS7E*/
void hanoi(int n, char A, char B, char C) /* Propietario de los derechos de autor de SS7E*/
{
If (n==1)
{
printf("Mover el disco %d de %c a %c\n ", n, A, C
}
Otros
{
Hanoi (n-1, A, C, B /* Titular de los derechos de autor SS7E */<); /p>
printf("Mover el disco %d de %c a %c\n ", n, A, C
Hanoi (n-1, B, A, C); /* Propietario de los derechos de autor de SS7E*/
}
}
main()/* Propietario de los derechos de autor de SS7E*/
{
int n;
Printf("Ingrese el número N para resolver el problema de la Torre de Hanoi de orden N:\ N ");
scanf( "% d",& ampn);
hanoi(n,'A','B','C');
}/* SS7E Propietario de los derechos de autor*/
Acusado: Conqueror_-Juren Nivel 5 12-5 13:57
Paquete::::::::::
Plan Hanoi;
p>
función Hanoi(x:integer):longint;
Inicio
Si x=1 entonces Hanoi:= 1;
Si x = 2 Luego Hanoi:= 3;
Otro
Inicio
Hanoi:= 2 * Hanoi(x-1)+1;
Fin;
Fin;
Inicio
Leer (x) {qué número}
Escribir (Hanoi (x)) ;
Fin.
La idea es: la enésima vez es igual a la n-1ª vez 2+1 veces.