Torre de Hanoi usando recursión (programa C ++)

Implementación de Torre de Hanoi en el uso de programa en C ++ , Aprender: ¿Cuál es Torre de Hanoi ? Cómo implementar el uso de la recursividad en C ++?

La Torre de Hanoi es un rompecabezas matemático inventado por el matemático francés Edouard Lucas en 1883.

Hay tres clavijas, de origen (A), auxiliar (B) y destino (C). Peg A contiene un conjunto de discos apilados para parecerse a una torre, con el disco más grande en la parte inferior y el disco más pequeño en la parte superior. figura 1 Ilustrar la configuración inicial de las clavijas para 3 discos. El objetivo es transferir toda la torre de discos en PEG de A a PEG C manteniendo el mismo orden de los discos.

El obedecer las siguientes reglas:

  1. sólo un disco puede ser transferencia a la vez.
  2. Cada movimiento consiste en tomar el disco superior de uno de los PEG y de colocarla sobre la parte superior de otro, es decir un disco de PEG sólo se pueden mover if es el disco más superior de la clavija.
  3. Nunca un disco más grande se coloca en un disco más pequeño durante la transferencia.

(figura 1)

La solución a las llamadas del rompecabezas para una aplicación de funciones recursivas y relaciones de recurrencia.

un procedimiento recursivo esquelético (Esquema) para la solución del problema para un número N de discos es la siguiente:

  1. Mover los mejores N-1 discos de PEG de A a PEG B (usando C como un auxiliarypeg)
  2. mover el disco inferior de PEG de a a PEG C
  3. Move N-1 discos a partir de PEG B a Peg C (utilizando PEG a como un PEG auxiliar)

la representación pictórica del procedimiento recursivo esquelético para N = 4 discos se muestra en la Figura 2 .

(figura 2)

Algoritmo

TOH( n,  Sour, Aux , Des)
If(n=1)
Write ("Move Disk “, n ," from ", Sour ," to ",Des)
Else
TOH(n-1,Sour,Des,Aux);
Write ("Move Disk “, n ," from ", Sour ," to ",Des)
TOH(n-1,Aux,Sour,Des);
END

Tomemos un ejemplo para comprender mejor el algoritmo (Para n = 3).

(figura 3)

Aplicación de Torre de Hanoi en el uso de C ++ programa

#include<iostream>
using namespace std;
//tower of HANOI function implementation
void TOH(int n,char Sour, char Aux,char Des)
{
if(n==1)
{
cout<<"Move Disk "<<n<<" from "<<Sour<<" to "<<Des<<endl;
return;
}
TOH(n-1,Sour,Des,Aux);
cout<<"Move Disk "<<n<<" from "<<Sour<<" to "<<Des<<endl;
TOH(n-1,Aux,Sour,Des);
}
//main program
int main()
{
int n;
cout<<"Enter no. of disks:";
cin>>n;
//calling the TOH
TOH(n,'A','B','C');
return 0;
}

salida

Enter no. of disks:3
Move Disk 1 from A to C
Move Disk 2 from A to B
Move Disk 1 from C to B
Move Disk 3 from A to C
Move Disk 1 from B to A
Move Disk 2 from B to C
Move Disk 1 from A to C

Image Referencia:

  1. http://www.peterloos.de/index.php/m-wpf/m-wpf-userdefined-controls/59-a-wpf-towersofhanoi
  2. http://algorithms.tutorialhorizon.com/towers-of- Hanoi /
  3. https://www.researchgate.net/publication/278658550_An_Evolutionary_Approach_to_Tower_of_Hanoi_Problem


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *