Ханойская башня — это игра, в которой вы перемещаете указанную выше стопку дисков с крайнего левого стержня на крайний правый стержень, соблюдая следующие правила:

  1. За один раз можно перемещать только один диск.
  2. Каждый ход состоит в том, чтобы взять верхний диск из одной стопки и поместить его поверх другой стопки или на пустой стержень.
  3. Ни один диск не может быть помещен поверх диска, который меньше его.

Легкая детская игра, да? Так думал и Билал…

Уважаемый Билал,

Поздравляем, вы официально стали кандидатом на выпускной. Вы в одном шаге от получения степени в области компьютерных наук в Университете Сайенсвилля. Как вы, возможно, знаете, Университет Сайенсвилля требует, чтобы все его кандидаты выполнили задание по своему выбору, связанное с их областью обучения. Задание, которое вы выбрали в своей выпускной форме, выглядит следующим образом:Ханойская башня. У вас есть ровно 24 часа, чтобы выполнить это задание. Ваша задача начинается сейчас.

Билал взглянул на письмо и увидел три высоких металлических столба, расположенных на расстоянии 5 футов друг от друга. Крайний левый шест содержал стопку из 64 больших каменных дисков, размер которых увеличивался по направлению к основанию шеста. Остальные 2 полюса были бездисковыми.

Потрясенный размером стопки дисков, «Боже, я думал, что это должна быть игра для маленьких детей», — подумал Билал про себя.

— Я мог бы и начать, — пробормотал Билал себе под нос. Билал хрустнул костяшками пальцев и потянулся, думая о том, как он выполнит свою задачу. «24 часа должно быть достаточно, чтобы закончить задачу, — подумал Билал, — в конце концов я ее закончу, если начну двигать диски». Он начал с того, что поднял самый верхний (1-й) диск с крайнего левого шеста, прошел к крайнему правому шесту и бросил диск на место.

«Один диск закончился, — воскликнул Билал, — осталось 63! Такими темпами я закончу через час. Он вернулся к крайнему левому полюсу, взял теперь самый верхний 2-й диск, понял, что крайний правый полюс уже содержит меньший (1-й) диск, подошел к среднему полюсу и бросил диск на место. Билал, озадаченный, пытается сообразить, как он положит второй диск на крайний правый столб и как после этого будет перемещаться третий диск. "Я знаю! Я передвину 1-й диск на средний полюс, освободив правый полюс, затем положу 3-й диск справа. Теперь, когда 3-й диск на месте, я могу переместить 1-й диск влево, а затем 2-й диск вправо. Наконец-то я могу переместить 1-й диск вправо». Билал думал про себя, выполняя движения. Это оставило 61 диск на крайнем левом полюсе и только 3 диска на крайнем правом полюсе.

Билал продолжает использовать свою стратегию перемещения дисков, пытаясь разместить 4-й и 5-й диски. Наконец, поместив первые 5 дисков на крайний правый столб, Билал замечает, что уже прошло 30 минут. «Не волнуйся, — нервно говорит себе Билал, — у меня еще полно времени. Хотя, возможно, я мог бы использовать стратегию получше. Билал решает убрать из игры первые 3 диска, чтобы разработать лучшую стратегию. Он отмечает на земле три точки, изображающие столбы, и кладет три диска на крайнее левое место.

Билал пытается упростить задачу, определяя движение диска как движение «влево» или «вправо» относительно полюса, на котором в данный момент находится диск. Чтобы это работало, жерди заворачиваются по краям. Другими словами, «левое» движение от крайнего левого полюса будет означать перемещение диска к крайнему правому полюсу. Билал играет с тремя дисками, чтобы попытаться лучше понять проблему. «Давайте установим N равным количеству дисков». Билал думает про себя. «Если N= 1, мы просто перемещаем диск влево. Если N= 2, мы перемещаем 1-й диск вправо, 2-й диск влево и 1-й диск вправо. Таким образом, казалось бы, мы перемещаем N-1 диск вправо, N-й диск влево и N-1 диск вправо. Следовательно, если N= 3, мы перемещаем 2 диска вправо, N-й диск влево и 2 диска вправо. Как бы мы переместили 2 диска правильно? Мы могли бы выполнить те же действия, что и в случае N = 2, за исключением противоположных направлений, поскольку в этом случае мы двигали 2 диска влево, а не двигали 2 диска вправо, как мы делаем сейчас. Окончательная последовательность ходов при N=3 будет следующей: 1-й диск слева, 2-й диск справа, 1-й диск слева, 3-й диск слева, 1-й диск слева, 2-й диск справа, 1-й диск слева».

Получив ценное представление о проблеме, Билал получил достаточно информации, чтобы понять, что эту проблему можно решить рекурсивно, и разработал для этого алгоритм. Его алгоритму требовались две порции информации: размер N решаемой задачи (количество перемещаемых дисков) и направление перемещения дисков (движение влево или вправо).

Чтобы проверить, работает ли его алгоритм, Билал тщательно следовал алгоритму до завершения. После завершения Билал был счастлив, что это сработало. Однако он заметил, что список ходов рос очень быстро по мере увеличения N. Билал забеспокоился, пересчитывая свои шаги: «Когда N = 1, требовался только 1 ход. Когда N= 2, ходов было 3. N= 3, 7 ходов. N= 4, 15 ходов!» Билал взглянул на свой алгоритм, чтобы увидеть, сможет ли он предсказать количество ходов, необходимых для задачи размера N. Билал понял, что каждый вызов функции, кроме самого первого вызова функции, приводит к еще двум вызовам функции. Он создал формулу для представления времени, необходимого для решения задачи размера N, на основе этого вывода: T(N) = 2 ∗ T (N −1) + 1, где T(1) = 1. Следовательно, T(N) = 2^Н -1. «Это означает, что потребуется 2^64 −1, умноженное на количество времени, которое мне потребуется, чтобы переместить 1 диск». Билал истерически говорит: «Если мне потребуется 1 секунда, чтобы переместить 1 диск, это займет БОЛЕЕ 580 МИЛЛИАРДОВ ЛЕТ! Это больше, чем возраст Вселенной!»

Билал вскидывает руки вверх, смотрит в небо и кричит: «Это невозможно решить всего за 24 часа!»

Пусть это будет уроком для Билала и всех остальных, не забывайте учитывать, что произойдет, если ваша проблема станет масштабной! Если бы Билал заранее обдумал масштаб, он бы выбрал другую проблему для своего требования к окончанию университета.