Torre de Hanoi en C++

1. Torre de Hanoi
2. Solución del Problema de la Torre de Hanoi
3. Programa en C++ para el problema de la Torre de Hanoi

Este artículo resumirá el Problema de la Torre de Hanoi y su solución recursiva en C++.

Torre de Hanoi

Tower of Hanoi es un rompecabezas matemático que involucra tres varillas y varios discos que pueden moverse alrededor de las varillas. Los discos se colocan en orden decreciente de tamaño de arriba a abajo y forman una pila.

El objetivo es mover todos los discos en la barra de destino (última), manteniendo el mismo orden pero siguiendo algunas reglas:

1. Solo puede mover un disco a la vez.
2. No se puede colocar ningún disco en un disco que sea más pequeño que él mismo.

Siguiendo estas reglas, debe mover los discos desde la primera barra o clavija hasta la última barra. El número mínimo de movimientos necesarios para lograr esta tarea es 2^n -1, donde n es el número de discos.

Esto se ilustra en la siguiente imagen:

Ahora necesita mover estos tres discos en Peg A al destino Peg C con la ayuda de Peg B.

Solución del Problema de la Torre de Hanoi

Puede haber soluciones tanto iterativas como recursivas para este problema, pero discutiremos la recursiva aquí, ya que la iteración depende de la cantidad de discos. Para la solución recursiva, suponga que hay m discos en Peg A.

1. El mismo método básico se usa para transferir discos m-1 de la Peg A a la Peg B. Suponiendo que no rompa las reglas, el disco m es ahora el disco superior en Peg A.
2. Mover el disco m desde la Peg A hasta la clavija de destino, es decir, la Peg C, que es un procedimiento sencillo y sigue las reglas generales.
3. Usando el mismo método, mueva los discos m-1 que acabamos de poner en la Peg B desde la Peg B a la clavija de destino, es decir, la Peg C, para que puedan colocarse encima de la disco m sin romper ninguna restricción.
4. Repita estos pasos hasta llegar a la caja de salida.
5. El caso de salida es mover 0 discos, es decir, todos los discos están en la clavija de destino.

Programa en C++ para el problema de la Torre de Hanoi

El programa en C++ para resolver este problema se muestra a continuación:

void TowerOfHanoi(int m, string first, string middle, string last) {
  cout << "Current iteration " << m << endl;
  if (m == 1) {
    cout << "Moving Disc from " << first << " to " << last << endl;
  } else {
    TowerOfHanoi(m - 1, first, last, middle);
    cout << "Moving disc " << m << " from " << first << " to " << last << endl;
    TowerOfHanoi(m - 1, middle, first, last);
  }
}
int main() {
  int di = 3;
  TowerOfHanoi(di, "PegA", "PegB", "PegC");
}

Esto dará el siguiente resultado:

Tenga en cuenta que en la función TowerOfHanoi, recuperamos la función dos veces por cada iteración. Primero, nos movemos de la primera clavija al medio y luego del medio al último.

Esto hará el siguiente árbol:

main
  |--> TowerOfHanoi(3, ...)
  |      |
  |      |--> TowerOfHanoi(2, ...)
  |      |     |
  |      |     |--> TowerOfHanoi(1, ...)
  |      |     |--> TowerOfHanoi(1, ...)
  |      |<----|
  |      |--> TowerOfHanoi(2, ...)
  |      |     |
  |      |     |--> TowerOfHanoi(1, ...)
  |      |     |--> TowerOfHanoi(1, ...)
  |      |<----|
  |<-----|
  |