Cómo derivar la fórmula de la Torre de Hanoi
a[1]=1;
a[n]= a[n-1] *2+1;
¿Puedo pedir la fórmula general?
a[1]=1;
a[n]=a[n-1]*2+1;
A[i] puede ser obtenido =2^i-1;
Prueba, usa inducción matemática:
1 Conjetura a[i] = 2^i-1
2. Obviamente esto es cierto cuando i=1.
3. Supongamos que es cierto cuando i=k, es decir, a[k] = 2^k - 1, entonces:
Por a[n] = a[; n-1] * 2 - 1 obtiene
a[k+1] = a[k] * 2 - 1
= 2^k * 2 - 1
= 2^(k-1) - 1
Así está demostrado.
Además:
El problema de la Torre de Hanoi (también conocido como problema de la Torre de Hanoi) es un problema basado en una leyenda:
Hay tres polos A, B y C, hay N (N>1) discos con agujeros en el polo A, y el tamaño de los discos disminuye de abajo hacia arriba. Es necesario mover todos los discos al polo C de acuerdo con las siguientes reglas:
1. Sólo se puede mover un disco a la vez
2. No se pueden apilar discos más grandes; discos más pequeños superiores.
Consejo: Puedes colocar temporalmente el disco en el polo B, o puedes mover el disco del polo A nuevamente al polo A, pero debes cumplir con estas dos reglas.
P: ¿Cómo moverse? ¿Cuál es el número mínimo de movimientos?
La regla general es N=64, por lo que el número mínimo de movimientos es 264-1. Es decir, si el disco pudiera moverse en un segundo, todavía tardaría 584.554.000.000 de años. Actualmente, según la teoría del Big Bang, la edad del universo es de sólo 13,7 mil millones de años.
En un juguete real, normalmente N=8, esto requeriría 255 movimientos. Si N=10, se requieren 1023 movimientos. Si N=15, se necesitan 32767 movimientos; esto significa que si una persona mueve un disco todos los días desde los 3 hasta los 99 años, solo podrá moverlo 15 veces. Si N=20, esto requeriría 10.485.575 movimientos, o más de un millón de veces.
Veamos la situación de Hani (1, uno, dos, tres). Esto es para mover los mosaicos de una columna directamente a tres columnas. Tenga en cuenta que no importa si la primera o tercera columna es A, B o C. Lo que es importante recordar es 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. . superior. Por conveniencia, escriba este movimiento como:
uno = "tres
Veamos el caso de hanoi(2, uno, dos, tres) nuevamente. Considerando que ya hemos analizado En el caso de hanoi (1), se puede ver que en este momento ocurrirán tres operaciones:
uno = "dos
uno = "tres
dos = "tres
Obviamente, esto en realidad equivale a mover dos discos directamente de una columna a tres columnas.
Miremos de nuevo al caso de hanoi(3, uno, dos, tres). Análisis
hanoi(2, uno, tres, dos)
uno = "tres
hanoi(2, dos, uno, tres)
En otras palabras, primero mueva los dos discos de la primera columna a la segunda columna, luego mueva el disco de la primera columna a la tercera columna y finalmente mueva los dos discos de la segunda columna a la tercera columna.
¿No es esto equivalente a mover tres discos de una columna directamente a tres columnas?
Usando inducción, podemos ver que para cualquier n,
hanoi(n-1, uno, tres, dos)
uno = "tres "
hanoi(n-1, dos, uno, tres)
En otras palabras, movemos n-1 discos de la columna uno a la columna dos y luego movemos los discos de la columna uno. Un disco se mueve a la tercera columna y, finalmente, n-1 discos de la segunda columna se mueven a la tercera columna. ¡Este es el resultado que necesitamos!
Respuesta: wuchenghua121 - Gerente de nivel 4 12-5 11:51
Torre de Hanoi
El problema con la Torre de Hanoi (también conocida como Torre de Hanoi) es un antigua leyenda india. Brahma, el creador del mundo, dejó tres barras de diamantes en un templo. Hay 64 piezas redondas de oro en la primera barra, la pieza más grande está en la parte inferior y el resto son más pequeñas entre sí. Orden Los monjes trabajaron incansablemente para moverlos uno por uno de un poste a otro. Se estipuló que podían usar el poste del medio como ayuda, pero solo podían mover uno a la vez y los más grandes no se podían colocar. encima de los más pequeños. Con respecto al método de resolución del problema, calcule usted mismo; consulte el procedimiento al final. Frente al enorme número 18446744073709551615 (el número de veces que se movió el disco de oro), los monjes parecían incapaces de completar el movimiento del disco de oro incluso después de pasar toda su vida.
Más tarde, esta leyenda evolucionó hasta convertirse en el juego Hannuka Tower:
1 Hay tres polos A, B y C. Hay varios discos en el pilar A
2 Mueva un disco a la vez, y el más pequeño solo se puede apilar encima del más grande
3. los discos del pilar A al pilar C
Después de la investigación, se descubrió que el método para romper la Torre Hannuka es muy simple. Mueve el oro en una dirección según las reglas de movimiento:
Por ejemplo, la Torre de Hanoi de tres niveles: A→C,A→B,C→B,A→C,B→A, B→C,A→ C
Además, el problema de la Torre de Hannover también es un problema de recursividad clásico en programación.
Suplemento: Implementación del algoritmo de la Torre de Hanoi (c++)
#include
#include
usando espacio de nombres std;
ofstream fout(" out.txt");
void Move(int n,char x,char y)
{
fout<< "Mover el número "< } void Hannoi(int n,char a,char b,char c) { if(n==1) Mover( 1,a,c); else { Hannói(n-1,a,c,b); Mover(n,a,c); Hannói(n-1,b,a,c); } } int main() { fout<< "Aquí hay una solución de la Torre Hannoi de 7 pisos:"< Hannoi( 7 ,'a','b','c'); fout.close(); cout<< "¡Salida completa!" return 0; } Algoritmo C Lite /* Copyrighter by SS7E */ #include void hanoi(int n,char A,char B,char C) /* Copyright de SS7E */ { if(n==1) { printf("Mover el disco %d de %c a %c\n", n,A , C); } else { hanoi(n-1,A,C,B); por SS7E */ printf("Mover el disco %d de %c a %c\n", n,A,C); printf("Mover el disco %d de %c a %c\n",n,A,C); hanoi(n-1,B,A,C); /* Copyrighter by SS7E */ } }} main() /* Copyrighter by SS7E */ { int n; printf ( "Ingrese el número n para resolver el problema de Hanoi de enésimo orden:\n"); scanf("%d",&n); hanoi(n,' A ','B','C'); }/* Copyrighter by SS7E */ Respondida por Vanquisher_ - Lifter Level 5 12- 5 13:57 parcel:::::::::::: programa hanoi; funciónhanoi(x:integer)：longint comenzar si x=1 entonces hanoi:=1 si x=2 entonces hanoi:=3; else comenzar hanoi：=2*hanoi(x-1)+1; finalizar; finalizar; comenzar leer(x){primer número} escribir(hanoi(x)); finalizar. Nuestra idea es que el enésimo número es igual al n-1º número multiplicado por 2+1 veces