Pídale a un maestro de programación que realmente comprenda el problema de la Torre de Hanoi que responda. Cuando n = 3, el proceso de ejecución detallado del código de llamada recursiva de la Torre de Hanoi escrito en lenguaje C.
Estaba muy confundido cuando me encontré por primera vez con la Torre de Hanoi. Con la acumulación de código, ahora es fácil de entender, por lo que el cartel original no tiene un conocimiento profundo de las funciones recursivas. Le sugiero que escriba más Algunos programas recursivos pueden ser entendidos por usted mismo una vez que domine.
Proceso de movimiento lógico del disco + análisis del proceso recursivo del programa
¿Problema de la torre de Hanoi? El análisis del algoritmo es el siguiente. Supongamos que hay n discos en A. Para facilitar la comprensión, lo haré. cambie los n discos de Numerados 1-n de arriba a abajo, etiquetados placa 1, placa 2... placa n.
Si n=1, mueva el "Disco 1" directamente de A a C.
Si n=2, entonces:
(1) Mueva n-1 (igual a 1) discos de A a B, es decir, mueva el disco 1 a B;
(2) Luego mueva el "Disco 2" de A a C;
(3) Finalmente, mueva n-1 a B (igual a 1) Se mueve un disco a C, es decir, el disco 1 colocado en B en el paso (1) se mueve a C.
Nota: Como hay más de 1 placa aquí, las placas no se pueden mover directamente de A a C. Tienes que usar B. Entonces, el significado de ?hanoi (n, uno, dos, tres) está dado por n placas, pasar de una a tres, si n>2 entonces realizar recursividad, si n=1, entonces moverse directamente.
Proceso específico:
Hanoi (2, A, B, C); porque 2>1, ingresa al enlace recursivo.
<1>Ejecutar hanoi (1, A, C, B): este es el paso (1) de ahora, lo que significa que con la ayuda del pilar C, 1 disco (disco 1) en el pilar A se está moviendo al pilar B. De hecho, dado que n = 1, el pilar C no se usa en este momento, sino que se mueve directamente.
<2>Ejecutar hanoi (1, A, B, C): Este es el paso (2), con la ayuda del pilar B, mueve un disco (disco 2) en el pilar A al C pilar. Como aquí n=1, en realidad no se mueve directamente con la ayuda del pilar B.
<3>Ejecutar hanoi(1,B,A,C): Este es el paso (3), mover una placa (disco 1) de B a C
Función Desde el El valor n de cada llamada a Hanoi es 1, no ingresará a la recursividad y la función de movimiento mov se ejecutará directamente.
Si n=3, entonces: (lo entenderás si lo piensas al revés) la penúltima parte del movimiento debe ser la siguiente situación
(1) Cambiar n`- en A Mueva 1 (igual a 2) discos a C, es decir, el disco 1 y el disco 2 están en el pilar B en este momento. Solo de esta manera se puede mover el disco inferior (disco 3). Entonces, dado que ahora estamos ignorando la placa más grande (Lámina 3), nuestro objetivo actual es mover las dos placas (Lámina 1, Placa 2) del pilar A al pilar B con la ayuda del pilar C. ¿Este proceso es el? proceso de movimiento cuando n = 2 arriba El proceso de movimiento cuando n = 2 es "2 placas, muévase del pilar A al pilar C con la ayuda del pilar B". Ahora son "2 placas, pasar del pilar A al pilar B con la ayuda del pilar C". Por lo tanto, el proceso de movimiento se puede realizar llamando directamente al proceso de movimiento de n = 2.
(2) Mueva un disco (disco 3) de A a C.
(3) En este punto, dado que la placa más grande (Placa 3) se ha movido al destino, no es necesario utilizar la placa más grande (Placa 3) sin importar cómo se mueva más adelante. Ignorémoslo por ahora. El objetivo restante es mover los n-1 discos (disco 1, disco 2) de B a C. Como no hay discos en A, para lograr el objetivo anterior en este momento, debemos usar A. lámina. El objetivo final es mover las dos placas de B a C con la ayuda de A. Este proceso es el proceso de análisis cuando n=2 es solo el pilar inicial (pilar B) y el pilar asistido (pilares A) son diferentes. . Por lo tanto, se puede lograr llamando directamente al proceso cuando n = 2.
Proceso de ejecución específico:
Hanoi (3, A, B, C); porque 3>1, ingresa al enlace recursivo.
<1>Ejecutar hanoi(2,A,C,B): Esto representa el paso (1) de ahora, moviendo dos placas (disco 1, placa 2) de A a B, con la ayuda de c. Según el proceso de análisis de n = 2, nuestro propósito debe lograrse.
<2>Ejecutar hanoi (1, A, B, C): Ahora solo hay un disco (disco 3) en A, simplemente muévalo directamente a C.
<3>Ejecutar hanoi (2, B, A, C): Esto corresponde al paso (3). El objetivo restante es mover las dos placas de B a C con la ayuda de A. Luego, basándose en el mismo proceso de movimiento de n = 2, definitivamente se logrará el objetivo.
Al final, se movieron tres placas de A a C con la ayuda de B.