Рекурсия — одно из самых распространенных алгоритмических понятий. Если говорить просто, то рекурсивным алгоритм становится, если вызывает сам себя.
Головоломка Ханойские башни состоит из трёх стержней, пронумеруем их слева направо: 1, 2 и 3. Также в головоломке используется стопка дисков с отверстием посередине. Радиус дисков уменьшается снизу вверх. Изначально диски расположены на левом стержне (стержень 1), самый большой диск находится внизу. Диски в игре перемещаются по одному со стержня на стержень. Диск можно надеть на стержень, только если он пустой или верхний диск на нём большего размера, чем перемещаемый. Цель головоломки — перенести все диски со стержня 1 на стержень 3. Попробуйте нашу интерактивную версию Ханойских башен и узнайте, как переместить все диски с одного стержня на другой.
Ханойские башни: Вывод списка действий, необходимых для решения головоломки «Ханойские башни».
- Входные данные: Целое число .
- Выходные данные: Последовательность ходов для решения головоломки «Ханойские башни» из дисков.
Решить головоломку с одним диском легко — просто переместите его на правый стержень. Головоломка на два диска ненамного сложнее. Сначала нужно переместить маленький диск на стержень посередине, а большой — на стержень справа. Затем переместить маленький диск на большой на правом стержне.
Версия на три диска чуть сложнее, но и ее можно решить с помощью следующих семи шагов:
- Переместить диск со стержня 1 на стержень 3
- Переместить диск со стержня 1 на стержень 2
- Переместить диск со стержня 3 на стержень 2
- Переместить диск со стержня 1 на стержень 3
- Переместить диск со стержня 2 на стержень 1
- Переместить диск со стержня 2 на стержень 3
- Переместить диск со стержня 1 на стержень 3
Теперь давайте посчитаем, сколько шагов потребуется для решения версии на четыре диска. Нам нужно обязательно переместить самый большой диск, но для этого придётся сперва поместить все остальные диски на пустой стержень. Если у нас не три диска, а четыре, то нужно переложить три верхних диска на пустой стержень (7 действий), а затем переместить самый большой диск (1 действие). Теперь нужно снова переместить три диска с «временного» стержня на самый большой диск (еще 7 действий). Весь процесс будет состоять из действий.
Обобщим. Чтобы переместить дисков с левого стержня на правый, сначала необходимо переместить дисков на стержень посередине. Затем, когда диск под номером , самый большой, оказывается на правом стержне, нужно переместить на него оставшиеся диски со стержня посередине. Чтобы переместить дисков со стержня посередине направо, нужно сначала переместить дисков на стержень слева, затем переместить -й диск вправо, потом переместить дисков с левого стержня на правый и так далее.
На первый взгляд задача «Ханойские башни» может показаться сложной. Тем не менее данный рекурсивный алгоритм находит нужные перемещения дисков всего за 8 строк!
HanoiTowers(n,fromPeg,toPeg)
if n = 1:
output “Move disk from peg fromPeg to peg toPeg”
return
unusedPeg = 6 - fromPeg - toPeg
HanoiTowers(n−1,fromPeg,unusedPeg)
output “Move disk from peg fromPeg to peg toPeg”
HanoiTowers(n−1,unusedPeg,toPeg)
Переменные и указывают на три разных стержня. Таким образом, HanoiTowers(n, 1, 3) перемещает диски ( шт.) с первого стержня на третий. Переменная указывает, какой из трёх стержней можно использовать для временного хранения первых () дисков. Обратите внимание, что всегда равняется . Таким образом, значение переменной можно определить как . Представленная таблица показывает результаты для всех возможных переменных и .
|
fromPeg |
toPeg |
unusedPeg |
|
1 |
2 |
3 |
|
1 |
3 |
2 |
|
2 |
1 |
3 |
|
2 |
3 |
1 |
|
3 |
1 |
2 |
|
3 |
2 |
1 |
Определив как , операторы
HanoiTowers(n−1,fromPeg,unusedPeg)
output “Move disk from peg fromPeg to peg toPeg”
HanoiTowers(n−1,unusedPeg,toPeg)
выполняют более простую задачу: они сначала перемещают дисков на временный стержень, затем перекладывают большой диск, а потом складывают на него оставшиеся дисков. Обратите внимание, что нет необходимости указывать, какой диск игрок должен переложить с на : перемещается всегда тот диск, что является верхним на .
💡 Остановитесь и подумайте:
Сколько нужно действий, чтобы переместить дисков?
Хотя решение Ханойских башен можно уложить в 9 строк псевдокода, его выполнение займет на удивление много времени. Решение головоломки на пять дисков состоит из 31 действия. А в решении башни из сотни дисков количество действий будет исчисляться “страшными” нонилионами. Такое резкое увеличение числа действий для HanoiTowers неудивительно. Заметим, что каждый раз, когда вызывается HanoiTowers(n, 1, 3), алгоритм дважды вызывает сам себя для перемещения дисков, что запускает четыре вызова для перемещения дисков и так далее.
Это можно проиллюстрировать с помощью рекурсивного дерева, изображенного на рис.. Вызов HanoiTowers(4, 1, 3) приводит к вызовам HanoiTowers(3, 1, 2) и HanoiTowers(3, 2, 3); каждый из них вызывает HanoiTowers(2, 1, 3), HanoiTowers(2, 3, 2) и HanoiTowers(2, 2, 1), HanoiTowers(2, 1, 3) и так далее. Каждый вызов подпрограммы HanoiTowers занимает определенное время. Мы хотим узнать, сколько времени уйдёт на такой алгоритм.
Чтобы вычислить время выполнения HanoiTowers размера , мы введём в рассмотрение функцию — количество перемещений дисков, которые выполняет HanoiTowers(n). Получается следующее уравнение:
Начиная с , это рекуррентное соотношение задаёт последовательность:
и так далее. Мы можем вычислить , прибавив 1 с обеих сторон и обнаружив, что
Если мы введём новое обозначение, , то . Таким образом, нужно решить следующее рекуррентное соотношение:
Начиная с , получаем последовательность
То есть, и . Следовательно, HanoiTowers(n) — экспоненциальный алгоритм.