Виктор Викторович Тарапата - Конструируем роботов на Lego Mindstorms Education EV3. Ханойская башня

изобретателей прошлого! Почему в настоящее время такое стало возможно? Можно ли изобрести
что-нибудь новое, не зная, какие машины и механизмы существовали в
прошлом? Как интереснее работать —
одному или вместе с другом?

Тайна Ханойской башни

Независимо от возраста многие любят решать головоломки. Одной из
самых любимых и занимательных головоломок считается «Ханойская
башня», имеющая к тому же захватывающую легенду. Самое интересное
в её легенде то, что там нет Ханоя. Эту игру в 1883 году представил
миру Франсуа Эдуард Анатоль Люка (1842–1891), математик и предприниматель. Он стал продавать игрушку, которую сопроводил аннотацией в виде рассказа путешественника — некоего профессора Клауса
из университета Ли-Су-Стьян (Li-Sou-Stian), посетившего индуистский
монастырь в далёком городе Бенарес. Вскоре первая дополнительная
головоломка была разгадана — покупатели поняли, что имя профессора
(Claus) было анаграммой собственного имени Франсуа Люка (Lucas).
Вернёмся к игре. По легенде, сопровождающей головоломку, в начале времён могущественный индуистский бог Брахма, олицетворяющий
творческое начало, решил наказать провинившихся монахов Великого
храма Бенареса, в котором находился бронзовый диск, отмечавший середину мира. В ярости бог воздвиг на диске три алмазных стержня и на
один из них возложил 64 диска из чистого золота — от самого большого
у основания стержня до крошечного на его конце. Священнослужители

Рис. 1. Игрушка «Ханойские башни»
из дерева (источник: google.com)

Рис. 2. Портрет Франсуа Люка
(источник: ru.Wikipedia.org)

5

должны перенести все диски на другой стержень с единственным условием: больший диск не должен никогда лежать на меньшем. Когда все
64 диска будут перенесены, наступит конец света! И монахи стараются
изо дня в день, не покладая рук…
Странная ситуация: после окончания игры произойдёт конец света,
а монахи стараются приблизить этот момент. Дело в том, что в легенде подразумевается конец этого света, то есть мира, в котором
есть страдания, боль и несправедливость. Когда игра закончится, все
попадут в мир бесконечной радости и счастья. То есть наказание монахов заключается как раз в том, что конец света не может случиться раньше, чем они перенесут диски. Всего они должны совершить
18 446 744 073 709 551 615 перемещений, что отодвигает их цель на
сотни миллиардов лет, даже если они будут работать без сна, отдыха
и очень быстро. Город для действия легенды был выбран далеко не
случайно. Бенарес (он же Варанаси) в индуистской космологии является центром Земли. Для буддистов он имеет такое же значение, как
Ватикан — для католиков. В этом городе, главном и оттого великом,
всегда пребывали наиболее мудрые и учёные последователи Брахмы.
Как ты можешь знать, многие великие открытия и достижения в математике и смежных областях были сделаны в Индии. Например, там
появились шахматы и десятичная система счисления.
Легенда за годы обрастала новыми подробностями, меняла место
действия, количество дисков, изменялись другие детали сюжета. Подробнее узнать о легенде и авторе игры ты можешь в книге С. М. Окулова и А. В. Лялина «Ханойские башни».
Классический вариант игры предусматривает три стержня и различающиеся по размеру кольца. Рекурсивный алгоритм для решения го-

Рис. 3. Вид на современный Бенарес (источник: pixabay.com)

6

ловоломки с тремя стержнями и n
дисками таков.
Кстати! Знакомая всем с детства и встре1. Перенести башню из n-1 дисков
чаемая фактически в каждой газете или
на второй стержень.
журнале головоломка — кроссворд — была
2. Перенести самый большой, n-й,
изобретена в 1913 году Артуром Винном.
диск на третий стержень.
3. Перенести башню из n-1 дисков
на третий стержень.
Минимальное количество ходов для решения составит 2n – 1, где n —
это число дисков. В информатике задачу «Ханойская башня» часто
рассматривают на уроках программирования при изучении рекурсии.
Раз речь зашла о программировании, значит, процесс можно автоматизировать. Ж. Арсак в книге «Программирование игр и головоломок» опубликовал рассказ «Ханойские башни. Печальный конец
Паскаля-младшего». В нём главный герой утверждает, что легенда
о задаче «Ханойская башня» реальна. В письме к своему бывшему
преподавателю он описывает своё путешествие в Индию в составе туристической группы. К нему как к программисту обратились с просьбой --">