) Содержание книги Впервой главе задача о Ханойских башнях обсуждается в своей классической формулировке: • В разделе 1.1 рассмотрен стандартный рекурсивный вариант реализации задачи. <...> Результатом здесь является компактная нерекурсивная программа решения задачи о Ханойских башнях, состоящая из двух операторов: цикла For.To.Do и вывода данных WriteLn. <...> • В разделе 2.2 путем введения нового понятия «ханойский граф» и его рассмотрения повышается наглядность обсуждения. <...> В «несправедливых башнях» наименьшему диску запрещено появляться на среднем (вспомогательном) стержне, а в «конкретных башнях» перекладывание осуществляется за заданное количество перемещений Пр ед и с ло ви е Пр ед и с ло ви е 7 (в определенном диапазоне). <...> В «kнезаконных башнях» больший диск можно класть на меньший, но только при определенных ограничениях, а в «параллельных башнях» разрешается одновременное перемещение двух дисков с различных стержней. <...> • Раздел 2.9 полностью посвящен интересной модификации задачи, в которой наименьший диск может всегда перемещаться на любой из стержней, а другие диски — только в том случае, когда они являются соседними (им разрешен только обмен местами). <...> Материал же из третьей главы следует рассматривать как обоснование фундаментальности понятия «рекурсия»: • В разделе 3.1 излагается точка зрения авторов на фундаментальные основы школьного курса информатики. <...> • В разделе 3.3 рекурсия разъясняется как способ организации вычислительного процесса, дается историческая ссылка. <...> При сотворении мира верховный индуистский богБрахма поместил на первый стержень 64 диска из чистого золота, в порядке уменьшения их размеров, и велел монахам переместить их на третий стержень, запретив при этом за один раз переносить более одного диска и помещать больший диск на меньший. <...> 2)Workshop on the Tower of Hanoi and Related Problems, September 18–22, 2005, Maribor, Slovenia (http://www-mat.pfmb.uni-mb.si/toh2005/ index.htm). <...> «Лобовой» рекурсивный алгоритм Сделать возможным изящное <...>
Ханойские_башни_(2).pdf
С. М. Окулов, А. В. Лялин
ХАНОЙСКИЕ
БАШНИ
4-е издание, электронное
Москва
Лаборатория знаний
2025
Стр.2
УДК 519.85(023)
ББК 22.18
О-52
С е р и я о с н о в а н а в 2008 г.
Окулов С. М.
О-52 Ханойские башни / С. М. Окулов, А. В. Лялин. —
4-е изд., электрон.—М. : Лаборатория знаний, 2025.—
248 с.—(Развитие интеллекта школьников).—Систем.
требования: Adobe Reader XI ; экран 10". — Загл.
с титул. экрана.—Текст : электронный.
ISBN 978-5-93208-870-8
На материале широко известной задачи о Ханойских
башнях показано, как организовать занятия по информатике,
чтобы побудить школьника к творчеству, развить у него вкус
к решению исследовательских проблем.
Книга предназначена для школьников и преподавателей
информатики, но также будет интересна студентам, профессионально
занимающимся информатикой. Она может быть
использована как в обычных школах при проведении факультативных
занятий, так и в образовательных учреждениях
с углубленным изучением информатики и математики.
УДК 519.85(023)
ББК 22.18
Деривативное издание на основе печатного аналога: Ханойские
башни / С. М. Окулов, А. В. Лялин. —М. : БИНОМ.
Лаборатория знаний, 2008.—245 с. : ил.—(Развитие интеллекта
школьников).—ISBN 978-5-94774-729-4.
В соответствии со ст. 1299 и 1301 ГК РФ при устранении
ограничений, установленных техническими средствами защиты
авторских прав, правообладатель вправе требовать от нарушителя
возмещения убытков или выплаты компенсации
ISBN 978-5-93208-870-8
© Лаборатория знаний, 2015
Стр.3
Оглавление
Предисловие .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ... .. .. .. .. ..
Введение. Легендарная история Ханойских башен.. .. ..
3
9
Глава 1. Классические Ханойские башни .. ... .. .. .. .. .. 13
1.1. «Лобовой» рекурсивный алгоритм . .. ... .. .. .. .. .. 13
1.2. На пути к итерациям .. .. .. .. .. .. .. ... .. .. .. .. .. 23
1.3. Решения, использующие двоичное дерево. .. .. .. .. 34
1.4. От «алгоритма монахов» до первого профессионального
решения задачи . .. .. .. .. .. .. .. . .. .. .. .. .. . 43
1.5. Таинственная программа, или битовая арифметика 57
1.6. Код Грея . .. .. .. .. .. .. .. .. .. .. .. .. .. . .. .. .. .. .. . 68
1.7. Ханойские башни как комбинаторный объект . . . . . 86
Глава 2. Вариации на тему о Ханойских башнях .. .. .. . 98
2.1. Сортирующие, «заброшенные» и произвольные
башни . .. .. .. .. .. .. .. .. .. .. .. .. .. .. . .. .. .. .. .. . 98
2.2. Ханойский граф . .. .. .. .. .. .. .. .. .. ... .. .. .. .. .. 105
2.3. Головоломки по мотивам башен .. .. ... .. .. .. .. .. 114
2.4. Транзитные башни. .. .. .. .. .. .. .. .. ... .. .. .. .. .. 132
2.5. Циклические башни, башни на прямой и на графах 146
2.6. «Несправедливые» и «конкретные» башни .. .. .. .. 158
2.7. Перемешанные, k-незаконные и параллельные
башни . .. .. .. .. .. .. .. .. .. .. .. .. .. .. . .. .. .. .. .. . 167
2.8. Цветные башни.. .. .. .. .. .. .. .. .. .. ... .. .. .. .. .. 179
2.9. Обменные башни .. .. .. .. .. .. .. .. .. ... .. .. .. .. .. 193
2.10. Башни на четырех и более стержнях... .. .. .. .. .. 206
Глава 3. Что такое рекурсия .. .. .. .. .. .. .. .. . .. .. .. .. .. . 219
3.1. О фундаментальных основах информатики .. .. .. .. 219
3.2. Рекурсия как категория описания реальности . . . . . 231
3.3. Рекурсия как метод управления вычислительным
процессом . .. .. .. .. .. .. .. .. .. .. .. .. ... .. .. .. .. .. 233
3.4. Методика изучения рекурсии . .. .. .. ... .. .. .. .. .. 236
Стр.246