Algoritmo de la Torre de Hanoi: Python, C++ Código
sarah chen
¿Qué es la Torre de Hanoi?
La Torre de Hanoi es un rompecabezas matemático formado por tres varillas y numerosos discos colocados uno encima del otro. También se la conoce como Torre de Brahma o Torre de Lucas, como la introdujo el matemático francés Edouard Lucas allá por 1883. Este rompecabezas se basa en leyendas sobre el movimiento de discos de oro entre tres varillas.
Este rompecabezas tiene tres varillas y un número variable de discos apilados. Estas barras están diseñadas como torres cíclicas. Entonces, los discos de mayor diámetro se apilan en la parte inferior y los discos más pequeños se apilan en la parte superior.
Inicialmente nos dan tres clavijas o varillas. Y uno de ellos (A, como se muestra en el ejemplo) tiene todos los discos apilados. Nuestro objetivo es mover una pila completa de discos de una varilla (A) a otra (C) obedeciendo algunas reglas específicas.
Aquí está la configuración inicial del rompecabezas.
Y este es el objetivo final.
Reglas de la Torre de Hanoi
A continuación se detallan algunas reglas esenciales para la Torre de Hanoi:
- En el estado inicial de este rompecabezas, todos los discos estarán apilados en la varilla uno.
- El estado final es que todos los discos de la varilla uno se apilarán sobre la varilla dos o la varilla tres.
- Podemos mover un disco de una varilla a otra en cualquier momento.
- Sólo podemos mover el disco superior de la varilla.
- No se puede colocar un disco encima de otro disco, que es más pequeño.
La leyenda original trataba sobre mover 64 discos. Los sacerdotes podían mover un disco a la vez según las reglas. Según la leyenda, había una profecía que decía que el mundo terminaría si lograban completar el acto. En la sección de complejidad temporal, mostraremos que una configuración de la Torre de Hanoi con n discos costaría 2^n – 1 movimiento.
Entonces, si los sacerdotes pudieran necesitar 1 segundo para mover los discos, el tiempo total que necesitarían para resolver el rompecabezas sería 2^64 – 1 segundo o 584,942,417,356 años, 26 días, 7 horas y 15 segundos.
Algoritmo para la Torre de Hanoi
Una forma general de resolver la Torre de Hanoi es un algoritmo recursivo. Primero, debemos decidir sobre dos varillas o clavijas como origen y destino, y la clavija de repuesto sería un auxiliar o ayuda.
Estos son los pasos para resolver el rompecabezas de la Torre de Hanoi:
- Mueva los n-1 discos superiores desde la clavija de origen a la clavija auxiliar.
- Luego, mueva el enésimo disco desde la clavija de origen a la clavija de destino.
- Finalmente, mueva los n-1 discos restantes desde la clavija auxiliar a la clavija de destino.
Nota: : Si tenemos un solo disco, podemos moverlo directamente del origen al destino.
Cómo resolver el rompecabezas de la Torre de Hanoi
Ilustremos el algoritmo para tres discos y consideremos la clavija A como fuente, la clavija B como auxiliar y la clavija C como destino.
Paso 1) Inicialmente, todos los discos se apilarán en la clavija A.
En este punto:
Fuente = clavija A
Destino = clavija C
Ayudante = clavija B
Ahora, necesitamos mover los n-1 discos superiores desde la fuente al asistente.
Nota: Aunque sólo podemos mover un disco a la vez, nuestro problema pasa de ser un problema de 3 discos a uno de 2 discos, que es una llamada recursiva.
Paso 2) Como realizamos una llamada recursiva desde la clavija A y el destino es la clavija B, usaremos la clavija C como ayuda.
Observe que estamos nuevamente en la etapa uno para el mismo problema de la torre de Hanoi para dos discos.
Ahora necesitamos mover n-1 o un disco desde el origen al auxiliar, moviendo el disco más pequeño de la clavija A a la clavija C.
En este punto:
Fuente = clavija A
Destino = clavija B
Ayudante = clavija C
Paso 3) Luego, de acuerdo con nuestro algoritmo, el enésimo o segundo disco necesario debe transferirse al destino o clavija B.
En este punto:
Fuente = clavija A
Destino = clavija B
Ayudante = clavija C
Paso 4) Ahora, moveremos los n-1 discos o el disco uno desde el asistente o clavija C al destino o clavija B de acuerdo con la tercera etapa de nuestro algoritmo.
En este punto:
Fuente = clavija A
Destino = clavija B
Ayudante = clavija C
Paso 5) Después de completar la llamada recursiva, volveremos a nuestra configuración anterior en la primera etapa del algoritmo.
Paso 6) Ahora, en la segunda etapa, moveremos nuestra fuente a nuestro destino, que es mover el disco 3 a la clavija C desde la clavija A.
En este punto:
Fuente = clavija A
Destino = clavija C
Ayudante = clavija B
Paso 7) Ahora podemos ver eso
d es mover los discos restantes desde el asistente (clavija B) al destino (clavija C). Usaremos la fuente inicial o clavija A como ayuda en este caso.
Paso 8) Como no podemos mover dos discos simultáneamente, realizaremos una llamada recursiva para el disco 1. De acuerdo con el último paso y nuestro algoritmo, un destino en este paso es la clavija A.
En este punto:
Fuente = clavija B
Destino = clavija A
Ayudante = clavija C
Paso 9) Nuestra llamada recursiva está completa ahora. Luego movemos el disco 2 desde su origen a su destino.
En este punto:
Fuente = clavija B
Destino = clavija C
Ayudante = clavija A
Paso 10) Luego movemos nuestro n-1 restante o disco 1 del asistente al destino.
En este punto:
Fuente = clavija A
Destino = clavija C
Ayudante = clavija B
Pseudocódigo para la Torre de Hanoi
START
Procedure Tower_Of_Hanoi(disk, source, dest, helper)
IF disk == 1, THEN
move disk from source to dest
ELSE
Tower_Of_Hanoi (disk - 1, source, helper, dest)
move disk from source to dest
Tower_Of_Hanoi (disk - 1, helper, dest, source)
END IF
END Procedure
código de programa en C++
#include <bits/stdc++.h>
using namespace std;
void tower_of_hanoi(int num, string source, string dest, string helper) {
if (num == 1) {
cout << " Move disk 1 from tower " << source << " to tower " << dest << endl;
return;
}
tower_of_hanoi(num - 1, source, helper, dest);
cout << " Move disk " << num << " from tower " << source << " to tower " << dest << endl;
tower_of_hanoi(num - 1, helper, dest, source);
}
int main() {
int num;
cin >> num;
printf("The sequence of moves :\n");
tower_of_hanoi(num, "I", "III", "II");
return 0;
}
Salida
3 The sequence of moves : Move disk 1 from tower I to tower III Move disk 2 from tower I to tower II Move disk 1 from tower III to tower II Move disk 3 from tower I to tower III Move disk 1 from tower II to tower I Move disk 2 from tower II to tower III Move disk 1 from tower I to tower III
código de programa en Python
def tower_of_hanoi(n, source, destination, helper):
if n==1:
print ("Move disk 1 from peg", source," to peg", destination)
return
tower_of_hanoi(n-1, source, helper, destination)
print ("Move disk",n," from peg", source," to peg", destination)
tower_of_hanoi(n-1, helper, destination, source)
# n = number of disks
n = 3
tower_of_hanoi(n,' A','B','C')
Salida:
Move disk 1 from peg A to peg B Move disk 2 from peg A to peg C Move disk 1 from peg B to peg C Move disk 3 from peg A to peg B Move disk 1 from peg C to peg A Move disk 2 from peg C to peg B Move disk 1 from peg A to peg B
Complejidad de la Torre de Hanoi
Aquí está la complejidad temporal y espacial de la Torre de Hanoi:
1) Complejidad temporal:
Si volvemos a mirar nuestro algoritmo, podemos ver que estamos introduciendo una llamada recursiva para (n-1) discos dos veces. Esas llamadas recursivas para (n-1) discos se pueden dividir en otros ((n-1)-1) y así sucesivamente hasta que solo tengamos un disco para mover.
Para tres discos-
- El disco 3 llama dos veces a una función recursiva para el disco dos.
- El disco 2 llama dos veces a una función recursiva para el disco uno.
- El disco 1 puede moverse en un tiempo constante y el tiempo para resolver tres discos.
= 2*(Tiempo para resolver dos discos) + constante Tiempo para mover el disco 3
= 2*(2*tiempo para resolver un disco + tiempo constante para mover el disco 2) + tiempo constante para mover el disco 3
= (2*2) (tiempo constante para mover el disco 1) + 2*tiempo constante para mover el disco 2 + tiempo constante para mover el disco 3
Para n discos, se puede escribir como:
(2n-1 * tiempo constante para mover el disco 1 + 2n-2 * tiempo constante para mover el disco 2 +….
Esta progresión geométrica dará como resultado O(2n-1) o O (2n), que es exponencial.
2) Complejidad espacial
La complejidad espacial de la Torre de Hanoi es 0(n). Esto se debe a que necesitamos almacenar la secuencia de las placas. Cuando utilizamos la recursión, utilizamos la pila. Y el tamaño máximo de la pila puede ser “n”. Por eso la complejidad espacial se convierte en O(n).