Задача о Ханойских башнях

Скажите, а вы ждали конец света в 2012 году, когда подошел к концу легендарный календарь Майя, или считаете это выдумкой и несмешной шуткой? Что ж, как бы то ни было, 2012 год мы пережили, однако Майя были далеко не единственным народом, предсказывавшим конец света.

По легенде, где-то на севере Индии, высоко в горах, за непроходимыми джунглями, полными свирепых хищников, стоит уединённый монастырь, посвященный богу Браме. При сотворении мира в центре главного храма Брама установил драгоценную святыню – 3 алмазных стержня, на один из которых были нанизаны 64 тяжелых золотых диска. Внизу лежал самый большой диск, а каждый следующий был всё меньше и меньше, но все равно каждый из них весил более сотни килограммов. Европейские путешественники, которым удалось добраться до монастыря, называли эти стержни Ханойскими Башнями, по названию местности.

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

С сотворения мира прошло уже немало лет, а третья Ханойская Башня все еще не собрана. Монахи, служащие Браме – истинные мудрецы, и точно знают, что поставленная перед ними задача решаема. Вопрос только во времени. Давайте же и мы с вами вычислим, сколько времени отмерил человечеству неведомый бог Брама из индийских лесов?

Чтобы выяснить, за сколько шагов решается задача, необходимо выяснить, как именно ее решать. Если решить «в лоб» задачу не получилось, математика предлагает нам два диаметрально противоположных подхода: начать решать с конца ту же задачу, или попробовать решить в лоб, но взять гораздо меньше элементов. А какой подход ближе вам?

Начнем с очевидного! Пусть на первом стержне у нас всего два диска. Как бы мы их не перекладывали, один из стержней будет свободен, а потому условием на диаметр дисков на одном стержне мы не ограничены. Дальше интереснее: если дисков будет три, потратив немного времени на подбор решения, мы с вами запросто переложим «пирамиду» с одного стержня на другой:

Однако обратите внимание: в какой-то момент все три диска у нас просто разложены по разным стержням! Уже с четырьмя дисками так не получится, и подбор последовательности действий будет куда более длительным и, вполне возможно, неоптимальным. Что же делать?

Точно! У нас с вами остается второй вариант: попробовать решить задачу с конца! Что это означает? На самом деле, все очень просто: если идти по решению задачи «наоборот», начинать надо с результата: все диски лежат на третьем стержне. А теперь вопрос со звездочкой: с чего начинается этот результат?

Ответ на самом деле прост: башня строится снизу – с самого большого диска. То есть, в определенный момент времени нам нужно будет переложить диск номер n с первого стержня на третий – и никак иначе. Необходимым условием для этого шага является отсутствие всех остальных дисков на первом и третьем стержнях, а значит, они должны быть сложены на втором. При этом они должны быть сложены в виде башни от максимального к минимальному, ведь иначе это будет противоречить второму условию!

Получается, мы свели задачу перемещения башни из n дисков на третий стержень к задаче перемещения n-1 дисков сначала с первого на второй, а после со второго на третий стержни – с теми же самыми условиями, ведь наличие самого большого диска внизу стержня никак не влияет на перекладывание. Задача о Ханойских башнях оказалась рекурсивной!

Остался самый важный вопрос: сколько же шагов нужно совершить, чтобы переместить 64 диска? Идем по той же траектории: посчитаем, сколько нужно совершить шагов для перемещения башни из 63 дисков, прибавим 1 – перенос самого большого диска, и прибавим то же количество шагов еще раз – ведь башню из 63 дисков нужно еще перенести со второго диска на третий. Такую цепочку вычислений можно записать в виде рекурсивной функции:

Если мы попробуем посчитать первые 64 значения данной функции, у нас вновь уйдет на это очень много времени. Попробуем привести ее к явному виду:

Мы получили формулу, которая позволяет найти следующий на любом расстоянии от заданного член последовательности. Теперь учтем, что нам известен первый член этого ряда, и выведем формулу для него. Пусть k = n + 1, тогда:

Отлично, мы получили лаконичную явную формулу! Осталось подставить в нее количество дисков – 64. Постойте-ка… Это же показательная функция – неизвестная переменная находится в показателе дроби - а такая функция очень быстро растет! В нашем случае значение  составит больше, чем  18446744073709551615 шагов. Если перекладывать тяжелые диски монахам удастся хотя бы по одному в минуту без перерывов на сон и еду, то решение поставленной задачи займет у них  лет! Более 35 000 миллиардов лет! Будьте уверены: поклонники этой легенды могут спать спокойно, ведь Брама отмерил нам еще немало времени.