Дано: в задаче «Ханойская башня» нужно переместить стопку дисков с одного колышка на другой, следуя следующим правилам:
1) Одновременно можно перемещать только один диск.
2) Диск можно положить только на больший диск или на пустой колышек.
3) Все диски начинаются на одной колышке и должны быть перемещены на другую колышку с помощью промежуточной колышки.
Решение будет производится с помощью рекурсии, а точнее вызова 2 рекурсивных функций за один шаг.
Первый шаг. Назовём нашу функцию HanoiTower, зададим какой высоты будет наша башня - (переменная n), и подумаем откуда (переменная from) - куда (переменная to), мы хотим переместить башню. Также обозначим промежуточную колышку (переменная interim). Итого получаем:
HanoiTower(n, from, to, interim).
Второй шаг.
Дальше надо понять закономерность ходов для вызова рекурсии: Понаблюдав за водой, огнём и перемещением дисков, видно, что на абстрактном предпоследнем шаге, n-1 дисков лежат на промежуточном колышке - interim. а самый большой диск мы кладём на заданную колышку (to)
То есть первый вывод, что n-1 диск всегда надо положить на промежуточной колышке, после чего всегда кладётся самый большой диск на заданную колышку.
Соответственно вызываем нашу функцию с n-1 элементами до появления базового случая n=2 для перемещения с начальной на промежуточную колышку, а конечная колышка становится промежуточной для этой функции.
То есть первый вывод, что n-1 диск всегда надо положить на промежуточной колышке, после чего всегда кладётся самый большой диск на заданную колышку.
Соответственно вызываем нашу функцию с n-1 элементами до появления базового случая для перемещения с начальной на промежуточную колышку, а конечная колышка становится промежуточной для этой функции.
HanoiTower(n-1, from, interim, to).
Пример:
Если n=4, то нужно положить 3 верхних диска на промежуточную колышку
Дальше, чтобы переложить эти 3 диска, нужно переложить 2 диска также на промежуточную колышку, так как 3 диска должны лежать на 2 колышке, то соответственно промежуточной колышкой становится 3 колышка.
А чтобы переложить 2 диска нужно также переложить один диск на промежуточную колышку, которой стала 2 колышка.
и дальше перемещаем самую большую колышку на конечную колышку в обратном порядке... Для 2 дисков - это синий диск на 3 колышку, для 3 дисков это зелёный диск на 2 колышку, для 4 дисков это красный диск на 3 колышку. но, но перед эти развёртыванием в обратную сторону нужно сделать второй вывод, который станет второй рекурсией.
Второй вывод: Чтобы переложить n-1 колышко на конечную колышку, нужно переложить n -2 колышка на промежуточную колышку (для n-1 диска) до появления базового случая с 1 диском, когда мы кладём диск на конечную колышку.
HanoiTower(n-1, interim, to, from).
То есть, возвращаемся к примеру с n=4:
мы развернули все диски до базового случая.
Дальше у нас появляется базовый случай для n=2 дисков, кладём меньший диск на конечную колышку, дальше опять отрабатывается первая рекурсия уровня выше, и после неё вызывается вторая рекурсия для n=3, которая снова вызывает две рекурсии для n =2
после неё вызывается вторая рекурсия для n=4, которая снова вызывает две рекурсии для n =3
Общая картинка вызова рекурсий представлена ниже:
Обобщение:
Инициализируется количество дисков
Вызывается towerOfHanoi для решения головоломки.
Метод towerOfHanoi:
Базовый случай: Если имеется только 1 диск, переместите его непосредственно из исходного в конечный.
Рекурсивные шаги:
Переместите n-1 диск с исходного колышка на вспомогательный колышек.
Переместите n-й диск из исходного в целевой.
Переместите n-1 диск из вспомогательной привязки в привязку назначения.
Решение Python
def HanoiTower(height,fromPole, toPole, withPole):
if height >= 1:
HanoiTower(height-1,fromPole,withPole,toPole)
moveDisk(fromPole,toPole)
HanoiTower(height-1,withPole,toPole,fromPole)
def moveDisk(fp,tp):
print("moving disk from",fp,"to",tp)
HanoiTower(3,"A","B","C")
Временная сложность: так как каждый раз вызывается 2 рекурсии, то решение занимает O(2**n-1)
В википедии представлено циклическое решение:
Чтобы решить головоломку с чётным количеством дисков, надо многократно повторять действия: 1-2, 1-3, 2-3. Если число дисков нечётно — 1-3, 1-2, 2-3. где числа - это номер колышек.