Estructura de datos y algoritmos - Torre de Hanoi

Tower of Hanoi, es un rompecabezas matemático que consta de tres torres (clavijas) y más de un anillo es como se muestra:

Estos anillos son de diferentes tamaños y se apilan en orden ascendente, es decir, el más pequeño se coloca sobre el más grande. Hay otras variaciones del rompecabezas en las que aumenta el número de discos, pero el número de torres sigue siendo el mismo.

Reglas

La misión es mover todos los discos a alguna otra torre sin violar la secuencia de disposición. Algunas reglas a seguir para la Torre de Hanoi son:

• Solo se puede mover un disco entre las torres en un momento dado.
• Solo se puede quitar el disco "superior".
• Ningún disco grande puede colocarse sobre un disco pequeño.

A continuación se muestra una representación animada de la resolución de un rompecabezas de la Torre de Hanoi con tres discos.

El rompecabezas de la torre de Hanoi con n discos se puede resolver en un mínimo 2ⁿ−1pasos. Esta presentación muestra que un rompecabezas con 3 discos ha tomado2³ - 1 = 7 pasos.

Algoritmo

Para escribir un algoritmo para la Torre de Hanoi, primero debemos aprender cómo resolver este problema con una menor cantidad de discos, digamos → 1 o 2. Marcamos tres torres con nombre, source, destination y aux(solo para ayudar a mover los discos). Si solo tenemos un disco, entonces se puede mover fácilmente de la clavija de origen a la de destino.

Si tenemos 2 discos -

• Primero, movemos el disco más pequeño (superior) a la clavija auxiliar.
• Luego, movemos el disco más grande (inferior) a la clavija de destino.
• Y finalmente, movemos el disco más pequeño de aux a la clavija de destino.

Entonces, ahora estamos en condiciones de diseñar un algoritmo para Tower of Hanoi con más de dos discos. Dividimos la pila de discos en dos partes. El disco más grande (n- ^ésimo disco) está en una parte y todos los demás (n-1) discos están en la segunda parte.

Nuestro objetivo final es mover el disco ndesde el origen al destino y luego coloque todos los demás (n1) discos en él. Podemos imaginar aplicar lo mismo de forma recursiva para todo el conjunto de discos dado.

Los pasos a seguir son:

Step 1 − Move n-1 disks from source to aux
Step 2 − Move nth disk from source to dest
Step 3 − Move n-1 disks from aux to dest

Un algoritmo recursivo para Tower of Hanoi se puede manejar de la siguiente manera:

START
Procedure Hanoi(disk, source, dest, aux)

   IF disk == 1, THEN
      move disk from source to dest             
   ELSE
      Hanoi(disk - 1, source, aux, dest)     // Step 1
      move disk from source to dest          // Step 2
      Hanoi(disk - 1, aux, dest, source)     // Step 3
   END IF
   
END Procedure
STOP

Para verificar la implementación en programación C, haga clic aquí .