Назад

Ханойская башня

 

 

 

 

 

 

 

 

Одной из самых старых и известных головоломок, является Ханойская башня.
Придумал её французский математик Эдуард Люка в 1883 году. Суть её заключается в том, что нужно перемещать диски между тремя стержнями с наименьшим числом ходом.
Изначально все диски нанизаны на один стержень по убыванию диаметра снизу вверх. Наверху находится диск с наименьшим диаметром. Задача заключается в том, чтобы за минимальное число шагов перенести эти диски на другой стержень и расположить их в том же порядке. При этом можно переносить только по одному диску.
Рассмотрим наиболее простой вариант Ханойской башни с четырьмя дисками.

Ханойская башня с 4-мя дисками


Пронумеруем диски латинскими буквами, а стержни цифрами. Будем перемещать диски: a, b, c, d между стержнями: (1), (2) и (3).
Решение задачи Ханойской башни с четырьмя дисками по шагам:
1-ый шаг: Переместить диск «а» на стержень 2.
2-ый шаг: Переместить диск «b» на стержень 3.
3-ый шаг: Переместить диск «а» на стержень 3.
4-ый шаг: Переместить диск «c» на стержень 2.
5-ый шаг: Переместить диск «а» на стержень 1.
6-ый шаг: Переместить диск «b» на стержень 2.
7-ый шаг: Переместить диск «а» на стержень 2.
8-ый шаг: Переместить диск «d» на стержень 3.
9-ый шаг: Переместить диск «а» на стержень 3.
10-ый шаг: Переместить диск «b» на стержень 1.
11-ый шаг: Переместить диск «d» на стержень 1.
12-ый шаг: Переместить диск «c» на стержень 3.
13-ый шаг: Переместить диск «а» на стержень 2.
14-ый шаг: Переместить диск «b» на стержень 3.
15-ый шаг: Переместить диск «а» на стержень 3.
Для решения этой Ханойской башни нам потребовалось 15 шагов.
Существует легенда, по которой индийский бог, создавая мир, поместил 64 золотых диска на алмазный стержень и с тех пор монахи, этого монастыря, в котором находится сооружение с дисками, перекладывают их на другой стержень. По окончании их работы мир перестанет существовать. Сколько шагов и времени нужно для выполнения этой работы?
Математическая формула, описывающая эту операцию, выглядит как 2 в степени n минус 1 , где n-количество дисков. Следовательно, число перемещений дисков будет равно 18 446 744 073 709 551 615. А если предположить, что одно перемещение диска Ханойской башни будет производиться в одну секунду, то для этого числа перемещений понадобится 580 миллиардов лет.
Оптимальной задачей является Ханойская башня с числом дисков равным 8.

 

Назад