Problema de la Torre Torcida de Hanoi

La versión básica de la Torre de Hanoi se puede encontrar aquí. 
Es un problema retorcido de la Torre de Hanoi. En el cual, todas las reglas son las mismas con la adición de una regla: 
no puede mover ningún disco directamente desde la primera barra a la última barra , es decir, si desea mover un disco desde la primera barra a la última barra, entonces tiene que mueva la primera barra a la barra del medio primero y luego a la última. 

Acercarse:  

• Caso base: si el número de discos es 1, muévalo primero a la barra del medio y luego muévalo a la última barra.
• Caso recursivo: en el caso recursivo, los siguientes pasos producirán la solución óptima: (Todos estos movimientos siguen las reglas del problema de la Torre torcida de Hanoi) 
  1. Moveremos los primeros n-1 discos a la última barra primero.
  2. Luego mueva el disco más grande a la barra del medio.
  3. Mueva el primer disco n-1 de la última barra a la primera barra.
  4. Mueve el disco más grande desde la barra del medio hasta la última barra.
  5. Mueva todos los discos n-1 desde la primera barra hasta la última barra.

A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation
#include <iostream>
using namespace std;
 
// Function to print the moves
void twistedTOH(int n, char first,
                char middle, char last)
{
    // Base case
    if (n == 1) {
 
        cout << "Move disk " << n
             << " from rod " << first
             << " to " << middle
             << " and then to "
             << last << endl;
 
        return;
    }
 
    // Move n-1 disks from first to last
    twistedTOH(n - 1, first, middle, last);
 
    // Move largest disk from first to middle
    cout << "Move disk " << n
         << " from rod " << first
         << " to " << middle << endl;
 
    // Move n-1 disks from last to first
    twistedTOH(n - 1, last, middle, first);
 
    // Move nth disk from middle to last
    cout << "Move disk " << n
         << " from rod " << middle
         << " to " << last << endl;
 
    // Move n-1 disks from first to last
    twistedTOH(n - 1, first, middle, last);
}
 
// Driver's Code
int main()
{
    // Number of disks
    int n = 2;
 
    // Rods are in order
    // first(A), middle(B), last(C)
    twistedTOH(n, 'A', 'B', 'C');
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Function to print the moves
static void twistedTOH(int n, char first,
                char middle, char last)
{
    // Base case
    if (n == 1)
    {
 
        System.out.println("Move disk " + n + " from rod " +
                                   first + " to " + middle +
                                    " and then to " + last);
 
        return;
    }
 
    // Move n-1 disks from first to last
    twistedTOH(n - 1, first, middle, last);
 
    // Move largest disk from first to middle
    System.out.println("Move disk " + n +
                       " from rod " + first +
                       " to " + middle);
 
    // Move n-1 disks from last to first
    twistedTOH(n - 1, last, middle, first);
 
    // Move nth disk from middle to last
    System.out.println("Move disk " + n +
                       " from rod " + middle +
                       " to " + last);
 
    // Move n-1 disks from first to last
    twistedTOH(n - 1, first, middle, last);
}
 
// Driver Code
public static void main(String[] args)
{
    // Number of disks
    int n = 2;
 
    // Rods are in order
    // first(A), middle(B), last(C)
    twistedTOH(n, 'A', 'B', 'C');
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 implementation of above approach
 
# Function to print the moves
def twistedTOH(n, first, middle, last):
     
    # Base case
    if (n == 1):
 
        print("Move disk", n, "from rod", first,
              "to", middle, "and then to", last)
 
        return
 
    # Move n-1 disks from first to last
    twistedTOH(n - 1, first, middle, last)
 
    # Move largest disk from first to middle
    print("Move disk", n, "from rod",
                 first, "to", middle)
 
    # Move n-1 disks from last to first
    twistedTOH(n - 1, last, middle, first)
 
    # Move nth disk from middle to last
    print("Move disk", n, "from rod",
                 middle, "to", last)
 
    # Move n-1 disks from first to last
    twistedTOH(n - 1, first, middle, last)
 
# Driver Code
 
# Number of disks
n = 2
 
# Rods are in order
# first(A), middle(B), last(C)
twistedTOH(n, 'A', 'B', 'C')
 
# This code is contributed by
# divyamohan123

// C# implementation of the approach
using System;
     
class GFG
{
 
// Function to print the moves
static void twistedTOH(int n, char first,
                       char middle, char last)
{
    // Base case
    if (n == 1)
    {
        Console.WriteLine("Move disk " + n + " from rod " +
                                  first + " to " + middle +
                                   " and then to " + last);
 
        return;
    }
 
    // Move n-1 disks from first to last
    twistedTOH(n - 1, first, middle, last);
 
    // Move largest disk from first to middle
    Console.WriteLine("Move disk " + n +
                      " from rod " + first +
                      " to " + middle);
 
    // Move n-1 disks from last to first
    twistedTOH(n - 1, last, middle, first);
 
    // Move nth disk from middle to last
    Console.WriteLine("Move disk " + n +
                      " from rod " + middle +
                      " to " + last);
 
    // Move n-1 disks from first to last
    twistedTOH(n - 1, first, middle, last);
}
 
// Driver Code
public static void Main(String[] args)
{
    // Number of disks
    int n = 2;
 
    // Rods are in order
    // first(A), middle(B), last(C)
    twistedTOH(n, 'A', 'B', 'C');
}
}
     
// This code is contributed by PrinciRaj1992

<script>
// Javascript program
// Function to print the moves
function twistedTOH(n, first, middle, last)
{
    // Base case
    if (n == 1) {
   
        document.write("Move disk " + n
             + " from rod " + first
             + " to " + middle
             + " and then to "
             + last + "<br>");
   
        return;
    }
   
    // Move n-1 disks from first to last
    twistedTOH(n - 1, first, middle, last);
   
    // Move largest disk from first to middle
    document.write("Move disk " + n
         + " from rod " + first
         + " to " + middle + "<br>");
   
    // Move n-1 disks from last to first
    twistedTOH(n - 1, last, middle, first);
   
    // Move nth disk from middle to last
    document.write("Move disk " + n
         + " from rod " + middle
         + " to " + last + "<br>");
   
    // Move n-1 disks from first to last
    twistedTOH(n - 1, first, middle, last);
}
 
// driver code
// Number of disks
var n = 2;
 
// Rods are in order
// first(A), middle(B), last(C)
twistedTOH(n, 'A', 'B', 'C');
 
// This code contributed by shivani
</script>

Move disk 1 from rod A to B and then to C
Move disk 2 from rod A to B
Move disk 1 from rod C to B and then to A
Move disk 2 from rod B to C
Move disk 1 from rod A to B and then to C

Fórmula de recurrencia:

T(n) = T(n-1) + 1 + T(n-1) + 1 + T(n-1)
     = 3 * T(n-1) + 2

where n is the number of disks.

Resolviendo esta recurrencia, la Complejidad del Tiempo será O(3 ⁿ ) .
Espacio Auxiliar : O(n).