Torre de Hanoi es un rompecabezas matemático. Tradicionalmente , consta de tres postes y una serie de discos de diferentes tamaños que pueden deslizarse sobre cualquier poste. El rompecabezas comienza con el disco en una pila ordenada en orden ascendente de tamaño en un polo, el más pequeño en la parte superior, formando así una forma cónica. El objetivo del rompecabezas es mover todos los discos de un polo (por ejemplo, ‘polo de origen’) a otro polo (por ejemplo, ‘polo de destino’) con la ayuda del tercer polo (por ejemplo, polo auxiliar).
El rompecabezas tiene las siguientes dos reglas:
1. No puede colocar un disco más grande en un disco más pequeño
2. Solo se puede mover un disco a la vez
Ya hemos discutido la solución recursiva para la Torre de Hanoi con complejidad de tiempo O(2^n). Usando 4 varillas, el mismo enfoque muestra una disminución significativa en la complejidad del tiempo.
Ejemplos:
Input : 3 Output : Move disk 1 from rod A to rod B Move disk 2 from rod A to rod C Move disk 3 from rod A to rod D Move disk 2 from rod C to rod D Move disk 1 from rod B to rod D Input : 5 Output : Move disk 1 from rod A to rod C Move disk 2 from rod A to rod D Move disk 3 from rod A to rod B Move disk 2 from rod D to rod B Move disk 1 from rod C to rod B Move disk 4 from rod A to rod C Move disk 5 from rod A to rod D Move disk 4 from rod C to rod D Move disk 1 from rod B to rod A Move disk 2 from rod B to rod C Move disk 3 from rod B to rod D Move disk 2 from rod C to rod D Move disk 1 from rod A to rod D
C++
// C++ Recursive program for Tower of Hanoi#include using namespace std;// Recursive function to solve Tower// of Hanoi puzzlevoid towerOfHanoi(int n, char from_rod, char to_rod,char aux_rod1, char aux_rod2){if (n == 0)return;if (n == 1){cout << "\n Move disk" <C// Recursive program for Tower of Hanoi#include // Recursive function to solve Tower// of Hanoi puzzlevoid towerOfHanoi(int n, char from_rod, char to_rod,char aux_rod1, char aux_rod2){if (n == 0)return;if (n == 1) {printf(“\n Move disk %d from rod %c to rod %c”,n, from_rod, to_rod);return;}towerOfHanoi(n – 2, from_rod, aux_rod1, aux_rod2,to_rod);printf(“\n Move disk %d from rod %c to rod %c “,n – 1, from_rod, aux_rod2);printf(“\n Move disk %d from rod %c to rod %c “,n, from_rod, to_rod);printf(“\n Move disk %d from rod %c to rod %c “,n – 1, aux_rod2, to_rod);towerOfHanoi(n – 2, aux_rod1, to_rod, from_rod,aux_rod2);}// driver programint main(){int n = 4; // Number of disks// A, B, C and D are names of rodstowerOfHanoi(n, ‘A’, ‘D’, ‘B’, ‘C’);return 0;}Java// Recursive program for Tower of Hanoipublic class GFG {// recursive function to solve// Tower of Hanoi puzzlestatic void towerOfHanoi(int n, char from_rod,char to_rod, char aux_rod1,char aux_rod2){if (n == 0)return;if (n == 1) {System.out.println(“Move disk ” + n +” from rod ” + from_rod +” to rod ” + to_rod);return;}towerOfHanoi(n – 2, from_rod, aux_rod1, aux_rod2,to_rod);System.out.println(“Move disk ” + (n – 1) +” from rod ” + from_rod +” to rod ” + aux_rod2);System.out.println(“Move disk ” + n +” from rod ” + from_rod +” to rod ” + to_rod);System.out.println(“Move disk ” + (n – 1) +” from rod ” + aux_rod2 +” to rod ” + to_rod);towerOfHanoi(n – 2, aux_rod1, to_rod, from_rod,aux_rod2);}// Driver methodpublic static void main(String args[]){int n = 4; // Number of disks// A, B, C and D are names of rodstowerOfHanoi(n, ‘A’, ‘D’, ‘B’, ‘C’);}}Python 3# Recursive program for Tower of Hanoi# Recursive function to solve Tower# of Hanoi puzzledef towerOfHanoi(n, from_rod, to_rod, aux_rod1,aux_rod2):if (n == 0):returnif (n == 1):print(“Move disk”, n, “from rod”,from_rod, “c to rod”, to_rod)returntowerOfHanoi(n – 2, from_rod, aux_rod1,aux_rod2, to_rod)print(“Move disk”, n-1, “from rod”, from_rod,“c to rod”, aux_rod2)print(“Move disk”, n, “from rod”, from_rod,“c to rod”, to_rod)print(“Move disk”, n-1, “from rod”, aux_rod2,“c to rod”, to_rod)towerOfHanoi(n – 2, aux_rod1, to_rod,from_rod, aux_rod2)# driver programn = 4 # Number of disks# A, B, C and D are names of rodstowerOfHanoi(n, ‘A’, ‘D’, ‘B’, ‘C’)# This code is contributed by Smitha.C#// Recursive program for Tower of Hanoiusing System;public class GFG {// recursive function to solve// Tower of Hanoi puzzlestatic void towerOfHanoi(int n, char from_rod,char to_rod, char aux_rod1,char aux_rod2){if (n == 0)return;if (n == 1) {Console.WriteLine(“Move disk ” + n +” from rod ” + from_rod +” to rod ” + to_rod);return;}towerOfHanoi(n – 2, from_rod, aux_rod1,aux_rod2, to_rod);Console.WriteLine(“Move disk ” + (n – 1)+ ” from rod ” + from_rod+ ” to rod ” + aux_rod2);Console.WriteLine(“Move disk ” + n +” from rod ” + from_rod+ ” to rod ” + to_rod);Console.WriteLine(“Move disk ” + (n – 1)+ ” from rod ” + aux_rod2+ ” to rod ” + to_rod);towerOfHanoi(n – 2, aux_rod1, to_rod,from_rod, aux_rod2);}// Driver methodpublic static void Main(){int n = 4; // Number of disks// A, B, C and D are names of rodstowerOfHanoi(n, ‘A’, ‘D’, ‘B’, ‘C’);}}// This code is contributed by Anant Agarwal.PHP
C
// Recursive program for Tower of Hanoi#include // Recursive function to solve Tower// of Hanoi puzzlevoid towerOfHanoi(int n, char from_rod, char to_rod,char aux_rod1, char aux_rod2){if (n == 0)return;if (n == 1) {printf(“\n Move disk %d from rod %c to rod %c”,n, from_rod, to_rod);return;}towerOfHanoi(n – 2, from_rod, aux_rod1, aux_rod2,to_rod);printf(“\n Move disk %d from rod %c to rod %c “,n – 1, from_rod, aux_rod2);printf(“\n Move disk %d from rod %c to rod %c “,n, from_rod, to_rod);printf(“\n Move disk %d from rod %c to rod %c “,n – 1, aux_rod2, to_rod);towerOfHanoi(n – 2, aux_rod1, to_rod, from_rod,aux_rod2);}// driver programint main(){int n = 4; // Number of disks// A, B, C and D are names of rodstowerOfHanoi(n, ‘A’, ‘D’, ‘B’, ‘C’);return 0;}
Java
// Recursive program for Tower of Hanoipublic class GFG {// recursive function to solve// Tower of Hanoi puzzlestatic void towerOfHanoi(int n, char from_rod,char to_rod, char aux_rod1,char aux_rod2){if (n == 0)return;if (n == 1) {System.out.println(“Move disk ” + n +” from rod ” + from_rod +” to rod ” + to_rod);return;}towerOfHanoi(n – 2, from_rod, aux_rod1, aux_rod2,to_rod);System.out.println(“Move disk ” + (n – 1) +” from rod ” + from_rod +” to rod ” + aux_rod2);System.out.println(“Move disk ” + n +” from rod ” + from_rod +” to rod ” + to_rod);System.out.println(“Move disk ” + (n – 1) +” from rod ” + aux_rod2 +” to rod ” + to_rod);towerOfHanoi(n – 2, aux_rod1, to_rod, from_rod,aux_rod2);}// Driver methodpublic static void main(String args[]){int n = 4; // Number of disks// A, B, C and D are names of rodstowerOfHanoi(n, ‘A’, ‘D’, ‘B’, ‘C’);}}
Python 3
# Recursive program for Tower of Hanoi# Recursive function to solve Tower# of Hanoi puzzledef towerOfHanoi(n, from_rod, to_rod, aux_rod1,aux_rod2):if (n == 0):returnif (n == 1):print(“Move disk”, n, “from rod”,from_rod, “c to rod”, to_rod)returntowerOfHanoi(n – 2, from_rod, aux_rod1,aux_rod2, to_rod)print(“Move disk”, n-1, “from rod”, from_rod,“c to rod”, aux_rod2)print(“Move disk”, n, “from rod”, from_rod,“c to rod”, to_rod)print(“Move disk”, n-1, “from rod”, aux_rod2,“c to rod”, to_rod)towerOfHanoi(n – 2, aux_rod1, to_rod,from_rod, aux_rod2)# driver programn = 4 # Number of disks# A, B, C and D are names of rodstowerOfHanoi(n, ‘A’, ‘D’, ‘B’, ‘C’)# This code is contributed by Smitha.
C#
// Recursive program for Tower of Hanoiusing System;public class GFG {// recursive function to solve// Tower of Hanoi puzzlestatic void towerOfHanoi(int n, char from_rod,char to_rod, char aux_rod1,char aux_rod2){if (n == 0)return;if (n == 1) {Console.WriteLine(“Move disk ” + n +” from rod ” + from_rod +” to rod ” + to_rod);return;}towerOfHanoi(n – 2, from_rod, aux_rod1,aux_rod2, to_rod);Console.WriteLine(“Move disk ” + (n – 1)+ ” from rod ” + from_rod+ ” to rod ” + aux_rod2);Console.WriteLine(“Move disk ” + n +” from rod ” + from_rod+ ” to rod ” + to_rod);Console.WriteLine(“Move disk ” + (n – 1)+ ” from rod ” + aux_rod2+ ” to rod ” + to_rod);towerOfHanoi(n – 2, aux_rod1, to_rod,from_rod, aux_rod2);}// Driver methodpublic static void Main(){int n = 4; // Number of disks// A, B, C and D are names of rodstowerOfHanoi(n, ‘A’, ‘D’, ‘B’, ‘C’);}}// This code is contributed by Anant Agarwal.
PHP
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA