Esta vez comparto con ustedes el pseudocodigo para resolver el problema de las torres de hanoi utilizando recursividad, este dilema es tipico de la programacion que suelen dejar en las escuelas como tarea.
Para ver la solucion sin recursividad clic aqui
Descripcion del problema:
Se tienen tres torres y un conjunto N de discos dediferentes tamaños. Cada uno tiene una perforacion en el centro que le permite desplazarse por las torres. Inicialmente, los N discos estan ordenados de mayor a menor en una de las torres. Se debe de pasar los discos a otra torre utilizando la tercera como auxiliar. Este movimiento debe hacerse respetando las siguientes reglas:
1.- En cada movimiento solo puede intervenir un disco, por lo tanto siempre sera el disco superior el que puede moverse.
2.-No puede quedar un disco sobre otro de menor tamaño.
Explicacion grafica:
Pseudocodigo:
hanoi(n, origen, destino, auxiliar)
si n=1
entonces
mover un disco de la torre origen a la torre destino //{solucion del metodo recursivo}
si no
//{mover n-1 discos de la torre origen a la torre auxiliar}
llamar hanoi(n-1, origen, auxiliar, destino) //{llamada recursiva}
Mover un disco de la torre origen a la torre destino
//{mover n-1 discos de la torre auxiliar a la torre destino}
llamar metodo hanoi(n-1, axuliar, destino, origen) //{llamada recursiva}
fin
fin
Pequeño analisis del procedimiento
Supongamos que tenemos solo dos discos (N=2) en la torre ORIGEN y debemos pasarlos a la torre DESTINO.
Recordemos que un disco no puede estar sobre uno de menor tamaño, entonces no podemos mover ambos discos a la misma columna en los dos primeros movimientos, debido a que quedaria el disco mas pequeño bajo el disco mas grande, por lo tanto se requiere de tres movimientos para lograr el objetivo:
Mover disco de ORIGEN a AUXILIAR
Mover disco de ORIGEN a DESTINO
Mover disco de AUXILIAR a DESTINO
En caso de tener 3 discos, es decir N=3 se deben hacer los siguientes movimientos:
Mover disco de ORIGEN a DESTINO
Mover disco de ORIGEN a AUXILIAR
Mover disco de DESTINO a AUXILIAR
Mover disco de ORIGEN a DESTINO
Mover disco de AUXILIAR a ORIGEN
Mover disco de AUXILIAR a DESTINO
Mover disco de ORIGEN a DESTINO
Formula
Si para N=2 tenemos que realizar 3 movimientos y para N=3, son 7 movimientos, podemos concluir la siguiente ecuacion:
Donde:
NM = numero de movimientos
N= Numero de discos
Solo hace falta elegir el lenguaje para implementar el algoritmo. Si algo les hace falta haganmelo saber en los comentarios. Espero les sirva.
changos esto me ubiera servido mas hace un añejo cuando me lo dejaron de tarea hahahahaha
disculpa pero como podria hacerlo en visual basic para k sea visible
no encuentro una verga de codigos en visual basic >:c
Es pseudocodigo we, tienes que pasarlo al lenguaje que necesites, esto solo te da la logica para que lo logres. no seas flojo.
Hola quisiera ayuda para entender la recursividad de este codigo!
Class Hanoi1
{
public void Hanoi(int N1, string A1, string B1, string C1)
{
int Cont = 0;
if (N1 == 1)
{
Console.WriteLine(«Mover un Discos de » + A1 + » a » + C1);
Cont++;
}
else
{
Hanoi(N1 – 1, A1, C1, B1);
Console.WriteLine(«Mover un Disco de » + A1 + » a » + C1);
Hanoi(N1 – 1, B1, A1, C1);
Cont++;
}
}
}
Cuando n valga 1 va a mostrar el mensaje «Mover el disco de la torre A a la torre C» ¿Y qué pasa con los demás discos? Porque para que este mensaje se muestre es porque ya entro al if y una vez cumplido se sale de todo el programa (ya no hay mas instrucciones que ejecutar).
Bueno, así lo veo yo, es una duda, gracias.