Алгоритмические головоломки

АЛГОРИТМИЧЕСКИЕ
ГОЛОВОЛОМКИ

Algorithmic
PUZZLES

ANANY LEVITIN
MARIA LEVITIN

Алгоритмические
ГОЛОВОЛОМКИ

АНАНИЙ ЛЕВИТИН
МАРИЯ ЛЕВИТИНА

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

Перевод с английского
Ж. А. Меркуловой,
Н. А. Меркулова

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

УДК 51-028.41+794
ББК 22.1я92
Л36

Левитин А.
Л36
Алгоритмические головоломки / А. Левитин, М. Левитина ; пер. с англ. Ж. А. Меркуловой, Н. А. Меркулова. — 3-е изд., электрон. — М. : Лаборатория знаний,
2023. — 328 с. — Систем. требования: Adobe Reader XI ;
экран 10". — Загл. с титул. экрана. — Текст : электронный.
ISBN 978-5-93208-640-7
Книга является уникальной коллекцией 150 головоломок,
каждая из которых снабжена указанием и решением. Задачи
сгруппированы в зависимости от уровня сложности. Издание
дополнено
двумя
обучающими
разделами
по
стратегиям
разработки и анализа алгоритмов.
В
настоящее
время
алгоритмические
головоломки
часто
используются
на
собеседованиях
при
приеме
на
работу.
Они
призваны
развить
аналитическое
мышление
и
просто
разнообразить досуг.
Для всех любителей математики.
УДК 51-028.41+794
ББК 22.1я92

Деривативное издание на основе печатного аналога: Алгоритмические
головоломки
/
А. Левитин,
М. Левитина
;
пер. с англ. Ж. А. Меркуловой, Н. А. Меркулова. — 2-е изд. —
М. : Лаборатория знаний, 2019. — 325 с. : ил.
ISBN 978-5-00101-188-0

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

ISBN 978-5-93208-640-7
© 2011 by Oxford University Press.
Algorithmic Puzzles, First Edition by Anany Levitin and Maria
Levitin. Впервые опубликовано на английском языке в 2011 г.
Этот перевод опубликован по договоренности с «Оксфорд
Юниверсити Пресс». ООО «Лаборатория знаний» несет полную
ответственность за этот перевод оригинального произведения,
и «Оксфорд Юниверсити Пресс» не несет ответственности
за любые ошибки, упущения, неточности или двусмысленности
в этом переводе или за убытки, причиненные в связи с его
использованием.
Algorithmic Puzzles, First Edition by Anany Levitin and Maria
Levitin was originally published in English in 2011. This
translation is published by arrangement with Oxford University
Press. BKL Publishers is solely responsible for this translation from
the original work and Oxford University Press shall have
no liability for any errors, omissions or inaccuracies or ambiguities
in such translation or for any losses caused by reliance thereon.

© Лаборатория знаний, 2017

Посвящается Максу с любовью

ОГЛАВЛЕНИЕ

Предисловие в вопросах и ответах . . . . . . . . . . . . . . . . . . . . . .
7

О чем эта книга?
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7

Для кого эта книга?
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7

Какие головоломки включены в книгу?
. . . . . . . . . . . . . . .
9

Подсказки, решения и комментарии
. . . . . . . . . . . . . . . . . .
10

Что представляет собой учебный раздел? . . . . . . . . . . . . . .
11

Почему в книге два указателя?
. . . . . . . . . . . . . . . . . . . . . . .
11

Благодарности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12

Список головоломок . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13

Головоломки учебного раздела
. . . . . . . . . . . . . . . . . . . . . . . .
13

Головоломки основного раздела
. . . . . . . . . . . . . . . . . . . . . . .
14

Головоломка в качестве эпиграфа: кто это сказал?
. . . .
18

Глава 1. Учебный раздел . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19

Общие стратегии разработки алгоритмов . . . . . . . . . . . . . .
19

Методы анализа алгоритмов . . . . . . . . . . . . . . . . . . . . . . . . . . .
42

Глава 2. Головоломки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
55

Лёгкие головоломки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
55

Головоломки средней сложности
. . . . . . . . . . . . . . . . . . . . . .
68

Сложные головоломки
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
87

Глава 3. Подсказки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
Глава 4. Решения
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

Лёгкие головоломки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
Головоломки средней сложности
. . . . . . . . . . . . . . . . . . . . . . 159

Сложные головоломки
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232

Список литературы
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304

Указатель
головоломок,
сгруппированных по
методам
разработки и анализа алгоритмов
. . . . . . . . . . . . . . . 315

Анализ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
Инварианты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
Поиск с возвратом . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
Уменьшай и властвуй
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317

Разделяй и властвуй
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319

Динамическое программирование
. . . . . . . . . . . . . . . . . . . . . 319

Полный перебор
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319

Жадный подход
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319

Итерационное улучшение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
Преобразуй и властвуй . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
Другие методы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322

Предметно-именной указатель . . . . . . . . . . . . . . . . . . . . . . . . . . 323

ПРЕДИСЛОВИЕ В ВОПРОСАХ
И ОТВЕТАХ

О ЧЕМ ЭТА КНИГА?

Эта книга представляет собой сборник алгоритмических головоломок — головоломок, для решения которых требуются,
в явном или неявном виде, чётко определённые процедуры
решения
задач.
Книга
представляет
собой
уникальный
сборник
таких
головоломок.
В
неё
включены
как
старые
классические
задачи,
вошедшие
в
фольклор
математиков
и специалистов по информатике, так и новые головоломки,
которые
предлагают
решить
во
время
собеседования
в крупных компаниях при приёме на работу.
У этой книги есть две цели:

♦ развлечь
широкий
круг
читателей,
интересующихся
головоломками;

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

ДЛЯ КОГО ЭТА КНИГА?

Эта книга может быть интересна для трёх больших категорий читателей:

♦ любителей головоломок;

♦ тех,
кто
хочет
развить
алгоритмическое
мышление,
в том числе учителей и учащихся;

Предисловие в вопросах и ответах

♦ тех,
кто
готовится
к
собеседованию
при
приёме
на
работу,
во
время
которого
предлагают
головоломки,
а также тех, кто проводит эти собеседования.

Любителям головоломок понравится этот сборник, содержащий головоломки разных типов и тем. Они встретят как
головоломки, любимые во все времена, так и малоизвестные
«жемчужины». Никаких знаний по информатике или даже
интереса к ней не требуется. Читатель, не обладающий такими знаниями, может просто пропустить описание стратегий разработки и анализа алгоритмов в разделе «Решения».
В последнее время термин «алгоритмическое мышление»
очень часто употребляется преподавателями по информатике, и не без оснований: повсеместное распространение компьютеров в современном мире действительно делает необходимым овладение навыками алгоритмического мышления
практически
для
каждого
студента.
Головоломки — идеальное средство для приобретения этих важных навыков в силу
двух причин.
Во-первых, головоломки — это
занятно
и человек обычно готов приложить больше усилий для решения головоломок, чем для решения обычных скучноватых
упражнений.
Во-вторых,
алгоритмические
головоломки
заставляют мыслить на более абстрактном уровне. Даже студенты,
обучающиеся информатике,
чаще
думают
о
решении алгоритмических задач в терминах компьютерного языка, который они знают, и не пытаются применить общие
стратегии
разработки
и
анализа
алгоритмов.
Головоломки
помогают восполнить этот существенный недостаток.
Головоломки в этой книге, безусловно, можно использовать для самостоятельного обучения. Вместе с обучающим
материалом
они,
на
наш
взгляд,
позволяют
ознакомиться
с основными алгоритмическими понятиями и методами. Головоломки могут использовать и преподаватели компьютерных курсов как в университетах, так и в средней школе,
в качестве вспомогательных упражнений
и материала
для
проектов. Эта книга также может быть интересна для обучения на курсах по принятию решений, особенно на тех
курсах, которые основаны на решении головоломок.
Для людей, готовящихся к собеседованию, эта книга будет полезна по двум причинам. Во-первых, в ней есть много
примеров головоломок, с которыми они могут встретиться,
с полным решением и комментариями. Во-вторых, в книге

Какие головоломки включены в книгу?
9

содержится краткий учебный материал по стратегиям разработки и методам анализа алгоритмов. По словам менеджеров, предлагающих на собеседовании решить головоломки,
для них в большей степени важно увидеть правильный подход к решению головоломки, а не само решение. На потенциального работодателя произведёт очень хорошее впечатление, если вы продемонстрируете ваш опыт в применении
общих стратегий разработки алгоритмов.

КАКИЕ ГОЛОВОЛОМКИ ВКЛЮЧЕНЫ В КНИГУ?

Алгоритмические головоломки составляют малую часть среди
тысяч
математических
головоломок,
придуманных
на
протяжении
многих
лет.
Подбирая
головоломки
для
этой
книги, мы руководствовались следующими критериями.
Во-первых, мы хотели, чтобы головоломки иллюстрировали некоторые общие принципы разработки и анализа алгоритмов.
Во-вторых, мы хотели, чтобы они были красивыми и элегантными, хотя эти качества, конечно, субъективны.
В-третьих, мы хотели, чтобы головоломки были различного уровня сложности. Сложность головоломки трудно точно определить; иногда головоломки, которые легко решают
ученики средней школы, ставят в тупик профессоров математики. Тем не менее, мы поделили нашу книгу на три
раздела — головоломки лёгкие, средней сложности и сложные — чтобы помочь читателю оценить уровень головоломки. В пределах каждого раздела мы также отсортировали
головоломки по уровню сложности. Для решения головоломок из раздела «Лёгкие головоломки» нужна только математика средней школы. Для решения некоторых задач из
следующих двух разделов применяется метод индукции, но
в общем, чтобы решить все головоломки в книге, будет достаточно школьной математики. Кроме того, во второй части учебного раздела вкратце освещаются такие темы, как
бинарные числа и простые рекуррентные соотношения. Конечно, это не означает, что все головоломки в книге — лёгкие. Некоторые из них — особенно в конце последнего раздела — являются по-настоящему сложными. Но их трудность
вовсе не в том, что они требуют сложной математики, поэтому они не должны отпугивать читателя.
В-четвёртых, мы чувствовали себя обязанными включить
несколько
головоломок,
имеющих
историческое
значение.

Предисловие в вопросах и ответах

В заключение отметим, что мы включили в книгу головоломки только с ясной постановкой задачи и решением, избегая таких трюков, как преднамеренная двусмысленность,
игра слов и т. д.
Нужно сделать ещё одно замечание. Многие головоломки
из этой книги можно решить с помощью полного перебора или поиска с возвратом (эти стратегии описаны в первой
части учебного раздела). Однако, это не тот подход, которым нужно наслаждаться при решении этих головоломок.
Он требуется только в случаях, когда это специально указано. Поэтому мы исключили такие категории головоломок,
как
судоку и
криптарифмы,
которые можно
решить или
полным перебором (перебором с возвратом), или же благодаря гениальной проницательности и озарению. Мы также
решили не включать головоломки, относящиеся к физическим объектам, которые не очень легко описать, такие как
Китайские кольца и кубик Рубика.

ПОДСКАЗКИ, РЕШЕНИЯ И КОММЕНТАРИИ

В книге для каждой головоломки приведены подсказка, решение и комментарии. Книги по головоломкам редко включают подсказки, но мы считаем их ценным дополнением.
Они могут слегка подтолкнуть в правильном направлении,
оставляя, тем не менее, шанс читателю самому решить головоломку. Все подсказки собраны в отдельном разделе.
К каждой головоломке приведено решение. Как правило,
оно начинается с короткого ответа. Это сделано для того,
чтобы дать
читателю
последнюю возможность самому
решить головоломку: если ответ читателя не тот, что в решении, он может прекратить чтение решения и попытаться
снова решить головоломку.
Алгоритмы
описаны
без
использования
специального
формата или псевдокода. Акцент делается на идеях, а не на
незначительных деталях. Переписать решения в более формальном виде — это уже само по себе полезное упражнение.
Большинство комментариев обращают внимание на общую
идею алгоритма, которую демонстрируют головоломка и её
решение. Иногда в комментариях также есть ссылки на похожие головоломки из этой книги или из других источников.
В большинстве книг, посвящённых головоломкам, не указывается происхождение головоломки. Обычно это объясняется
тем, что пытаться найти автора головоломки — всё равно, что