Искаженная башня Ханоя Проблема

Опубликовано: 12 Января, 2022

Базовую версию Ханойской башни можно найти здесь.
Это запутанная проблема Ханойской башни. В котором все правила одинаковы с добавлением правила:
Вы не можете переместить диск непосредственно от первого стержня к последнему стержню, т.е. если вы хотите переместить диск от первого стержня к последнему стержню, вам нужно сначала переместить первый стержень к среднему стержню, а затем к последнему. .

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход:

Базовый случай: если количество дисков 1, сначала переместите его на средний стержень, а затем переместите на последний стержень.
Рекурсивный случай: в рекурсивном случае следующие шаги приведут к оптимальному решению: (Все эти ходы следуют правилам извращенной задачи Ханойской башни)
1. Сначала мы переместим первые n-1 дисков на последнюю штангу.
2. Затем переместите самый большой диск на средний стержень.
3. Переместите первый диск n-1 от последнего стержня к первому стержню.
4. Переместите самый большой диск от среднего стержня к последнему стержню.
5. Переместите все диски n-1 от первого стержня к последнему стержню.

Below is the implementation of the above approach:

C++

// 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

// 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

# 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#

// 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

Javascript

<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>

Output:

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

Формула повторяемости:

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.

Решив это повторение, сложность времени будет O (3 ⁿ ) .

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Алгоритмы Структуры данных

Искаженная башня Ханоя Проблема

C++

Java

Python3

C#

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ