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

С. М. Окулов, А. В. Лялин

ХАНОЙСКИЕ
БАШНИ

3-е издание, электронное

Москва
Лаборатория знаний
2020

УДК 519.85(023)
ББК 22.18

О-52

С е р и я о с н о в а н а в 2008 г.
Окулов С. М.

О-52
Ханойские башни / С. М. Окулов, А. В. Лялин. —
3-е изд., электрон. — М. : Лаборатория знаний, 2020. —
248 с. — (Развитие интеллекта школьников). — Систем.
требования:
Adobe
Reader
XI
;
экран
10".— Загл.
с титул. экрана. — Текст : электронный.
ISBN 978-5-00101-831-5
На
материале
широко
известной
задачи
о
Ханойских
башнях показано, как организовать занятия по информатике,
чтобы побудить школьника к творчеству, развить у него вкус
к решению исследовательских проблем.
Книга предназначена для школьников и преподавателей
информатики, но также будет интересна студентам, профессионально занимающимся информатикой. Она может быть
использована как в обычных школах при проведении факультативных занятий, так и в образовательных учреждениях
с углубленным изучением информатики и математики.
УДК 519.85(023)
ББК 22.18

Деривативное издание на основе печатного аналога: Ханойские башни / С. М. Окулов, А. В. Лялин. — М. : БИНОМ.
Лаборатория знаний, 2008. — 245 с. : ил. — (Развитие интеллекта школьников). — ISBN 978-5-94774-729-4.

В
соответствии
со
ст. 1299
и
1301
ГК
РФ
при
устранении
ограничений, установленных техническими средствами защиты
авторских прав, правообладатель вправе требовать от нарушителя
возмещения убытков или выплаты компенсации

ISBN 978-5-00101-831-5
c○ Лаборатория знаний, 2015

2

Предисловие

Таланты создавать нельзя,
но можно создавать культуру, то есть почву,
на которой растут и процветают таланты...

Г. Нейгауз

Любой учитель в своей профессиональной жизни нет-нет
да задает себе такие вопросы: почему один школьник, что называется, «роет землю» в поисках истины и красоты, другого
знания заботят только для получения оценки, а третьему —
вообще все безразлично? Почему изначально любознательный ребенок постепенно, в процессе жизни и учебы, превращается в человека, безразличного ко всему, кроме удовлетворения основных потребностей, навязываемых прагматикой
окружающей среды? Почему информатика как образовательный предмет, обладающий исключительным ресурсом по развитию интеллектуальных способностей школьника1), превратилась в школьную дисциплину, изучаемую в самых худших
традициях педагогики — по принципу «рассказали — заучили — пересказали — что-то запомнив, воспроизвели —
получили оценку — пошли дальше в никуда к очередным
оценкам»?
Материал этой книги построен всего на одной задаче —
но зато такой, которая удивляла и удивляет! А удивление —
это одна из причин (может быть — главная), вызывающих
активность, или, если хотите, состояние хотения познавать, узнавать. Человека можно заставить делать все, что
угодно; единственное, чего не удается, так это заставить
его хотеть что-то делать. Захотеть он может только сам,
преодолевая естественное состояние «лености», заложенное

1) Окулов С. М. Информатика: развитие интеллекта школьника. 2-е изд.,
испр. М.: БИНОМ. Лаборатория знаний, 2008.

Предисловие

в нем природой, и начав заниматься тем, что в педагогике
называют «познавательной деятельностью». Точно так же,
понять что-то человек может только сам, а задача учителя
состоит не столько в том, чтобы что-то рассказать, а, скорее,
в том, чтобы в результате совместной деятельности создать
условия для возникновения акта появления нужной мысли
у школьника. Это первое положение, лежащее в основе
данной книги. Второе же основано на понимании того, что
есть человек. «Человек — это, прежде всего, распространенное во времени усилие, постоянное усилие стать человеком.
Ведь человек — это не естественное, не от природы данное
состояние, а состояние, которое творится непрерывно»1).
Исходя из этих предположений, материал данной книги
сконструирован по типу занятий, задающих контуры совместной деятельности учителя и школьника — деятельности,
которая направлена на возникновение у школьника желания познавать. Эту деятельность можно трактовать как
постоянную среду усилий, открывающую все новые грани
удивительного явления — задачи под названием «Ханойские
башни».
В результате такой деятельности познаются фундаментальные основы информатики, а также (благодаря максимальному использованию компьютера) синтезируются в единое
целое «слово» (действия учителя) и «дело» (деятельность
школьника), — а значит, дидактический потенциал информатики как школьного предмета по развитию интеллектуального потенциала школьника задействован практически
полностью. (Может быть, мы как авторы в этом случае
проиграли в некоторой точности изложения, — но что делать: перед нами стояла задача дать «живой» материал для
занятий, и пусть читатель нам будет судьей.)

Содержание книги

В первой главе задача о Ханойских башнях обсуждается
в своей классической формулировке:

• В разделе 1.1 рассмотрен стандартный рекурсивный вариант реализации задачи. Дается анализ времени решения

1) Мамардашвили М. К. Сознание и цивилизация. Тексты и беседы. М.:
Логос, 2004.

Предисловие
5

и обсуждаются два способа чисто технического ухода от
рекурсии. Задействуется структура данных «стек» и приводятся два способа организации работы с ним.

• В разделе 1.2 приводится логика поиска закономерностей
в процессе перекладывания дисков для нахождения итерационного варианта решения задачи. Оказывается, что
практически все необходимое для ее решения «заложено»
в двоичном представлении номера перемещения!

• В разделе 1.3 для решения задачи используется двоичное
дерево перемещений и поиск по нему. Аналогия с методом динамического программирования, названная нами
«неудачной попыткой», позволяет в очередной раз уяснить
экспоненциальную природу задачи.

• В разделе 1.4 продолжается обсуждение закономерностей
для поиска простого способа «ручного» перекладывания
дисков. Анализируется логика перемещения наименьшего
диска, очередность освобождения стержней, совместного
расположения четных и нечетных дисков. Раздел завершается первым приближением к профессиональному решению задачи. (Изложение здесь, как и во всей книге, объединено с программным кодом, который является неотъемлемой частью текста, что, в частности, позволяет развивать умения и навыки чтения листингов программ —
видения того, что стоит за этим программным кодом.)

• В разделе 1.5 рассматривается битовая арифметика. Этот
материал углубляет знание по теме; его достаточно для
организации и проведения занятия. Результатом здесь
является компактная нерекурсивная программа решения
задачи о Ханойских башнях, состоящая из двух операторов: цикла For...To...Do и вывода данных WriteLn.

• В разделе 1.6 наше обсуждение задачи делает неожиданный, на первый взгляд, поворот: достаточно подробно
изучается широко известный код Франка Грея, а затем
устанавливается связь между ним и Ханойскими башнями.

• В разделе 1.7 проводится аналогия между Ханойскими
башнями и такими классическими комбинаторными задачами, как подсчет количества комбинаторных объектов,

Предисловие

генерация объектов в соответствии с введенным отношением порядка, вычисление номера конкретного объекта
и определение объекта по его номеру.

Во второй главе решаются задачи, получающиеся при
изменении условий классической формулировки Ханойских
башен:

• В
разделе
2.1 рассмотрены «сортирующие
башни» —
задача, в которой четные и нечетные диски требуется
разложить по разным стержням; «заброшенные башни»,
где требуется из некой произвольной раскладки дисков
получить окончательную раскладку на третьем стержне;
«произвольные башни» — из некой разрешенной (допустимой) раскладки требуется найти следующую разрешенную
раскладку.

• В разделе 2.2 путем введения нового понятия «ханойский граф» и его рассмотрения повышается наглядность
обсуждения. Для вариаций задачи о Ханойских башнях
находятся аналоги в алгоритмах на графах.

• В разделе 2.3 анализируются задачи, очень просто сводящиеся к Ханойским башням либо, как задача о «вращающихся фигурках», требующие для своего решения
значительных усилий.

• Раздел 2.4 полностью посвящен «транзитным башням».
Это задача, в которой перекладывания дисков осуществляются через средний (вспомогательный) стержень. Ее
решению предшествует вспомогательная, но также очень
интересная задача о перемещении шашек. Устанавливается связь этих задач с кодами Грея.

• В разделе 2.5 рассмотрена задача о «циклических башнях»
(где направление переноса должно быть одинаковым для
всех дисков), которая в итоге обобщается до задач на связных ориентированных графах из трех вершин.

• В разделе 2.6 изучаются очередные модификации Ханойских башен. В «несправедливых башнях» наименьшему
диску запрещено появляться на среднем (вспомогательном) стержне, а в «конкретных башнях» перекладывание осуществляется за заданное количество перемещений

Предисловие
7

(в определенном диапазоне). Решение таких задач позволяет углубить понимание проблемы.

• В разделе 2.7 в задаче о «перемешанных башнях» на первом стержне задается раскладка дисков в произвольном порядке и требуется, с соблюдением правил, получить правильную башню на третьем стержне. В «kнезаконных башнях» больший диск можно класть на меньший, но только при определенных ограничениях, а в «параллельных башнях» разрешается одновременное перемещение двух дисков с различных стержней.

• В разделе 2.8 обсуждение задачи о «двуцветных башнях»
построено по другой схеме: из восьми вариантов решения,
оценив и разобрав их, требуется выбрать наилучшие.
Затем дается их разбор и рассматривается вариант задачи
для «трехцветных» башен.

• Раздел 2.9 полностью посвящен интересной модификации
задачи, в которой наименьший диск может всегда перемещаться на любой из стержней, а другие диски — только
в том случае, когда они являются соседними (им разрешен только обмен местами). Без привлечения ханойского
графа объяснение этой задачи проигрывает в доступности
и наглядности.

• В разделе 2.10 рассматривается обобщение задачи для
четырех стержней.

Материал же из третьей главы следует рассматривать как
обоснование фундаментальности понятия «рекурсия»:

• В разделе 3.1 излагается точка зрения авторов на фундаментальные основы школьного курса информатики. Материал здесь построен по принципу: «аксиома — тезис —
антитезис — синтез».

• В разделе 3.2 в сжатом виде излагается взгляд на рекурсию как на категорию описания реальности.

• В разделе 3.3 рекурсия разъясняется как способ организации вычислительного процесса, дается историческая
ссылка.

Предисловие

• В разделе 3.4 описывается методика изучения рекурсии
на основе учебника одного из авторов1).

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

1) Окулов С. М. Основы программирования. 3-е изд. М.: БИНОМ. Лаборатория знаний, 2006.

Введение

Легендарная история
Ханойских башен

Поколения сменяют поколения,
Не меркнут лишь преданья
старины.

А. Шамиссо

Согласно легенде, в одном из храмов индийского города
Бенареса установлена бронзовая плита с тремя алмазными
стержнями (рис.1). При сотворении мира верховный индуистский бог Брахма поместил на первый стержень 64 диска из
чистого золота, в порядке уменьшения их размеров, и велел
монахам переместить их на третий стержень, запретив при
этом за один раз переносить более одного диска и помещать
больший диск на меньший. С тех пор монахи день и ночь,
сменяя друг друга, трудятся над этой задачей. Как только
они закончат, храм рассыплется в прах и завершится жизнь
Брахмы. (Примерный понятный нам аналог — «конец света».)
Затем родится новый Брахма и все циклически повторится
сначала.
Согласитесь: красивая история.. . блеск золота и алмазов, неожиданная развязка...
А придумал ее французский
математик Эдуард Люка. Как сказал однажды Карл Вейер
2
1
3

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

Введение. Легендарная история Ханойских башен

штрасс, «нельзя быть настоящим математиком, не будучи
немного поэтом».
Легенда Люка была своего рода рекламным трюком для
его изящной, но более прозаичной головоломки, выполненной
из дерева и состоящей из восьми дисков. В 1883 г. ее продавали в Европе как забавную игрушку: первоначально — под
названием «Профессор Клаус (Claus)», но вскоре обнаружилось, что таинственный профессор — не более чем анаграмма
фамилии изобретателя игры — профессора Люка (Lucas)1).
Позже вместе с названием головоломки («Башни Брахмы»,
«Головоломка о Конце света», «Пагода-головоломка») неоднократно менялось и место действия легенды (Индия, Бенарес;
Вьетнам, Ханой; Китай, Тибет). А сейчас головоломка более
известна как Ханойские башни (те самые).

Рис. 2. Франсуа Эдуард
Анатоль Люка

Скажем
несколько
слов
и
об
изобретателе
нестареющих
«башен»2).
Франсуа
Эдуард
Анатоль
Люка (1842–1891) родился в Амьене,
во
Франции. По
окончании учебы
работал в Парижской обсерватории.
В качестве артиллерийского офицера
участвовал во франко-прусской войне
(1870–1871). После поражения французов стал профессором математики
в Париже. Важнейшие его работы
относятся к теории чисел и неопределенному анализу.
Ханойские
башни
—
это
лишь
одна из многих идей, с которыми связывают имя Люка, — и некоторые из этих идей имеют не
менее успешную судьбу. Например, Люка предложил тест
для определения, простым или составным является число
Мерсенна Mp = 2p − 1. Применяя свой метод, в 1876 г.
Люка установил, что M127 = 2127 − 1 — простое число,
и это огромное 39-значное число, по всей видимости, останется наибольшим простым числом, когда-либо найденным
«с карандашом в руках». (Пять новых простых чисел были
обнаружены только в 1952 г., но уже с помощью компьютера.

1) Гарднер М. Математические головоломки и развлечения. М.: Мир, 1999.
2) http://en.wikipedia.org/wiki/Edouard_Lucas.htm