Решить Tower of Hanoi Probelem в Python

Задача Ханойской башни - это фундаментальная математическая головоломка, которую с самого начала знакомят с новыми программистами, чтобы они могли дополнить свой тест на решение проблем.

Задача простая - три стержня. Один стержень содержит несколько дисков в порядке убывания, причем самый большой диск находится внизу, а самый маленький - вверху. Мы должны передать это с первого стержня на третий с помощью второго стержня.

Мы должны помнить об определенных правилах. Мы можем перемещать только один диск одновременно и должны брать диск за верхнюю часть стержня. Кроме того, мы не можем разместить диск большего размера поверх диска меньшего размера. Помня все это, мы должны решить эту задачу и подсчитать общее количество ходов, затраченных на ее решение.

В этом руководстве мы расскажем, как решить эту проблему. Мы будем использовать рекурсивный метод для решения проблемы Ханойской башни на Python.

Этот метод создаст функцию, которая будет вызывать себя рекурсивно в зависимости от некоторых условий для решения проблемы Ханойской башни. Мы реализуем эту логику в следующем коде.

def ToH(n , A, B, C):
    if n==1:
        print("Disk 1 from",A,"to",B)
        return 
    ToH(n-1, A, C, B)
    print("Disk",n,"from",A,"to",B)
    ToH(n-1, C, B, A)
          
ToH(3,'A','B','C')

Выход:

Disk 1 from A to B
Disk 2 from A to C
Disk 1 from B to C
Disk 3 from A to B
Disk 1 from C to A
Disk 2 from C to B
Disk 1 from A to B

В приведенном выше примере мы перемещаем три диска от стержня A к стержню B с помощью стержня C.

Как видите, общее количество ходов, сделанных в приведенном выше примере, равно 7. Для n дисков общее количество ходов, сделанных с использованием этого метода, всегда равно 2 ^ n -1.

Со временем появилось несколько других решений проблемы Ханойской башни с использованием стеков. Тем не менее, использовать их не рекомендуется, поскольку такие методы очень неэффективны по времени и скорости.