Dado un número entero positivo N que representa el número de discos en la Torre de Hanoi , la tarea es resolver el rompecabezas de la Torre de Hanoi utilizando representaciones binarias .
Ejemplos:
Entrada: N = 3
Salida:
Mover el disco 1 a la siguiente varilla circular derecha
Mover el disco 2 a la siguiente varilla circular derecha
Mover el disco 1 a la siguiente varilla circular derecha
Mover el disco 3 a la siguiente varilla circular derecha
Mover el disco 1 a la siguiente varilla circular barra derecha
Mueva el disco 2 a la siguiente barra circular derecha
Mueva el disco 1 a la siguiente barra circular derechaEntrada: N = 4
Salida:
Mover el disco 1 a la siguiente varilla circular derecha
Mover el disco 2 a la siguiente varilla circular derecha
Mover el disco 1 a la siguiente varilla circular derecha
Mover el disco 3 a la siguiente varilla circular derecha
Mover el disco 1 a la siguiente varilla circular varilla derecha
Mueva el disco 2 a la siguiente varilla circular derecha
Mueva el disco 1 a la siguiente varilla circular derecha
Mueva el disco 4 a la siguiente varilla circular derecha
Mueva el disco 1 a la siguiente varilla circular derecha
Mueva el disco 2 a la siguiente varilla circular derecha
Mueva el 1 el disco a la siguiente barra circular derecha
Mueva el disco 3 a la siguiente barra circular derecha
Mueva el disco 1 a la siguiente barra circular derecha
Mueva el disco 2 a la siguiente barra circular derecha
Mueva el disco 1 a la siguiente barra circular derecha
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- Se puede observar que para mover el N -ésimo disco, es necesario mover (N – 1) -ésimo disco. Por lo tanto, para mover (N – 1) el disco, es necesario mover (N – 2) el disco. Este proceso continúa recursivamente .
- El procedimiento anterior es similar a configurar el bit no configurado más a la derecha , ya que requiere configurar primero todos los bits a la derecha.
- Por lo tanto, la idea es imprimir todos los pasos intermedios, configurando cada vez el bit más a la derecha incrementando el número actual en 1 .
Siga los pasos a continuación para resolver el problema:
- Inicialice una array , digamos contador[] , de tamaño N , para almacenar el estado actual del problema.
- Itere sobre el rango [0, 2 N – 1] , establezca el bit no establecido más a la derecha y desactive todos los bits a la derecha.
- En cada iteración del paso anterior, imprima la posición del bit no establecido más a la derecha como el número del disco que se va a mover.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to increment binary counter
int increment(int* counter, int n)
{
int i = 0;
while (true) {
// Stores the Bitwise XOR of
// the i-th bit of N and 1
int a = counter[i] ^ 1;
// Stores the Bitwise AND of
// the i-th bit of N and 1
int b = counter[i] & 1;
// Swaps the i-th bit of N
counter[i] = a;
// If b is equal to zero
if (b == 0)
break;
// Increment i by 1
i = i + 1;
}
// Return i
return i;
}
// Function to print order of movement
// of disks across three rods to place
// all disks on the third rod from the
// first rod
void TowerOfHanoi(int N)
{
// Stores the binary representation
// of a state
int counter[N] = { 0 };
// Traverse the range [0, 2^N - 1]
for (int step = 1;
step <= pow(2, N) - 1; step++) {
// Stores the position of the
// rightmost unset bit
int x = increment(counter, N) + 1;
// Print the Xth bit
cout << "Move disk " << x
<< " to next circular"
<< " right rod \n";
}
}
// Driver Code
int main()
{
int N = 3;
TowerOfHanoi(N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to increment binary counter
static int increment(int[] counter, int n)
{
int i = 0;
while (true)
{
// Stores the Bitwise XOR of
// the i-th bit of N and 1
int a = counter[i] ^ 1;
// Stores the Bitwise AND of
// the i-th bit of N and 1
int b = counter[i] & 1;
// Swaps the i-th bit of N
counter[i] = a;
// If b is equal to zero
if (b == 0)
break;
// Increment i by 1
i = i + 1;
}
// Return i
return i;
}
// Function to print order of movement
// of disks across three rods to place
// all disks on the third rod from the
// first rod
static void TowerOfHanoi(int N)
{
// Stores the binary representation
// of a state
int[] counter=new int[N];
// Traverse the range [0, 2^N - 1]
for(int step = 1;
step <= Math.pow(2, N) - 1;
step++)
{
// Stores the position of the
// rightmost unset bit
int x = increment(counter, N) + 1;
// Print the Xth bit
System.out.println("Move disk " + x +
" to next circular" +
" right rod");
}
}
// Driver code
public static void main(String[] args)
{
// Given inputs
int N = 3;
TowerOfHanoi(N);
}
}
// This code is contributed by offbeat
Python3
# Python program for the above approach
import math
# Function to increment binary counter
def increment(counter, n):
i = 0
while (True):
# Stores the Bitwise XOR of
# the i-th bit of N and 1
a = counter[i] ^ 1
# Stores the Bitwise AND of
# the i-th bit of N and 1
b = counter[i] & 1
# Swaps the i-th bit of N
counter[i] = a
# If b is equal to zero
if (b == 0):
break
# Increment i by 1
i = i + 1
return i
# Function to print order of movement
# of disks across three rods to place
# all disks on the third rod from the
# first rod
def TowerOfHanoi(N):
# Stores the binary representation
# of a state
counter=[0 for i in range(N)]
# Traverse the range [0, 2^N - 1]
for step in range(1,int(math.pow(2,N))):
# Stores the position of the
# rightmost unset bit
x = increment(counter, N) + 1
#Print the Xth bit
print("Move disk ",x," to next circular"," right rod")
# Driver code
N = 3
TowerOfHanoi(N)
# This code is contributed by rag2127
C#
// C# program for the above approach
using System;
class GFG
{
// Function to increment binary counter
static int increment(int[] counter, int n)
{
int i = 0;
while (true)
{
// Stores the Bitwise XOR of
// the i-th bit of N and 1
int a = counter[i] ^ 1;
// Stores the Bitwise AND of
// the i-th bit of N and 1
int b = counter[i] & 1;
// Swaps the i-th bit of N
counter[i] = a;
// If b is equal to zero
if (b == 0)
break;
// Increment i by 1
i = i + 1;
}
// Return i
return i;
}
// Function to print order of movement
// of disks across three rods to place
// all disks on the third rod from the
// first rod
static void TowerOfHanoi(int N)
{
// Stores the binary representation
// of a state
int[] counter = new int[N];
// Traverse the range [0, 2^N - 1]
for (int step = 1;
step <= (int)(Math.Pow(2, N) - 1); step++)
{
// Stores the position of the
// rightmost unset bit
int x = increment(counter, N) + 1;
// Print the Xth bit
Console.WriteLine("Move disk " + x
+ " to next circular"
+ " right rod ");
}
}
// Driver Code
public static void Main()
{
int N = 3;
TowerOfHanoi(N);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// Javascript implementation for the above approach
// Function to increment binary counter
function increment(counter, n)
{
let i = 0;
while (true)
{
// Stores the Bitwise XOR of
// the i-th bit of N and 1
let a = counter[i] ^ 1;
// Stores the Bitwise AND of
// the i-th bit of N and 1
let b = counter[i] & 1;
// Swaps the i-th bit of N
counter[i] = a;
// If b is equal to zero
if (b == 0)
break;
// Increment i by 1
i = i + 1;
}
// Return i
return i;
}
// Function to print order of movement
// of disks across three rods to place
// all disks on the third rod from the
// first rod
function TowerOfHanoi(N)
{
// Stores the binary representation
// of a state
let counter= Array.from({length: N}, (_, i) => 0);
// Traverse the range [0, 2^N - 1]
for(let step = 1;
step <= Math.pow(2, N) - 1;
step++)
{
// Stores the position of the
// rightmost unset bit
let x = increment(counter, N) + 1;
// Print the Xth bit
document.write("Move disk " + x +
" to next circular" +
" right rod" + "<br/>");
}
}
// Driver Code
// Given inputs
let N = 3;
TowerOfHanoi(N);
// This code is contributed by sanjoy_62.
</script>
Move disk 1 to next circular right rod Move disk 2 to next circular right rod Move disk 1 to next circular right rod Move disk 3 to next circular right rod Move disk 1 to next circular right rod Move disk 2 to next circular right rod Move disk 1 to next circular right rod
Complejidad de Tiempo: O(N * 2 N )
Espacio Auxiliar: O(N)
Enfoque eficiente: el enfoque anterior se puede optimizar en función de las observaciones de que para M en el rango [1, 2 N – 1] , la barra de origen es igual a (m & (m – 1)) % 3 y la barra de destino es igual a (m | (m – 1) + 1) % 3 . Por lo tanto, la idea es iterar sobre el rango [1, 2 N – 1] e imprimir el valor de (i & (i – 1))%3 como varilla fuente y (i | (i – 1) + 1)% 3 como varilla de destino.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print order of movement
// of N disks across three rods to place
// all disks on the third rod from the
// first-rod using binary representation
void TowerOfHanoi(int N)
{
// Iterate over the range [0, 2^N - 1]
for (int x = 1;
x <= pow(2, N) - 1; x++) {
// Print the movement
// of the current rod
cout << "Move from Rod "
<< ((x & x - 1) % 3 + 1)
<< " to Rod "
<< (((x | x - 1) + 1) % 3 + 1)
<< endl;
}
}
// Driver Code
int main()
{
int N = 3;
TowerOfHanoi(N);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to print order of movement
// of N disks across three rods to place
// all disks on the third rod from the
// first-rod using binary representation
static void TowerOfHanoi(int N)
{
// Iterate over the range [0, 2^N - 1]
for(int x = 1;
x <= Math.pow(2, N) - 1; x++)
{
// Print the movement
// of the current rod
System.out.print("Move from Rod " +
((x & x - 1) % 3 + 1) + " to Rod " +
(((x | x - 1) + 1) % 3 + 1) + "\n");
}
}
// Driver Code
public static void main (String[] args)
{
int N = 3;
TowerOfHanoi(N);
}
}
// This code is contributed by jana_sayantan
Python3
# Python program for the above approach
import math
# Function to print order of movement
# of N disks across three rods to place
# all disks on the third rod from the
# first-rod using binary representation
def TowerOfHanoi(N):
# Iterate over the range [0, 2^N - 1]
for x in range(1,int(math.pow(2, N)) ):
# Print the movement
# of the current rod
print("Move from Rod " ,
((x & x - 1) % 3 + 1) , " to Rod " ,
(((x | x - 1) + 1) % 3 + 1) )
# Driver Code
N=3
TowerOfHanoi(N)
# This code is contributed by avanitrachhadiya2155
C#
// C# program for the above approach
using System;
class GFG{
// Function to print order of movement
// of N disks across three rods to place
// all disks on the third rod from the
// first-rod using binary representation
static void TowerOfHanoi(int N)
{
// Iterate over the range [0, 2^N - 1]
for(int x = 1;
x <= Math.Pow(2, N) - 1; x++)
{
// Print the movement
// of the current rod
Console.Write("Move from Rod " +
((x & x - 1) % 3 + 1) + " to Rod " +
(((x | x - 1) + 1) % 3 + 1) + "\n");
}
}
// Driver Code
static void Main()
{
int N = 3;
TowerOfHanoi(N);
}
}
// This code is contributed by SoumikMondal
Javascript
<script>
// Javascript program for the above approach
// Function to print order of movement
// of N disks across three rods to place
// all disks on the third rod from the
// first-rod using binary representation
function TowerOfHanoi(N)
{
// Iterate over the range [0, 2^N - 1]
for (let x = 1;
x <= Math.pow(2, N) - 1; x++) {
// Print the movement
// of the current rod
document.write("Move from Rod "
+ ((x & x - 1) % 3 + 1)
+ " to Rod "
+ (((x | x - 1) + 1) % 3 + 1)
+ "<br>");
}
}
// Driver Code
let N = 3;
TowerOfHanoi(N);
</script>
Move from Rod 1 to Rod 3 Move from Rod 1 to Rod 2 Move from Rod 3 to Rod 2 Move from Rod 1 to Rod 3 Move from Rod 2 to Rod 1 Move from Rod 2 to Rod 3 Move from Rod 1 to Rod 3
Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por scorchingeagle y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA