Эта книга представляет собой сборник алгоритмических головоломок—головоломок, для решения которых требуются, в явном или неявном виде, чётко определённые процедуры решения задач. <...> Книга представляет собой уникальный сборник таких головоломок. <...> Во-первых, в ней есть много примеров головоломок, с которыми они могут встретиться, с полным решением и комментариями. <...> По словам менеджеров, предлагающих на собеседовании решить головоломки, для них в большей степени важно увидеть правильный подход к решению головоломки, а не само решение. <...> В книгу включён учебный раздел, где на примерах головоломок описаны общие стратегии разработки и методы анализа алгоритмов. <...> Если читатель—специалист по информатике, то он вряд ли найдёт там для себя что-то новое, разве что примеры головоломок. <...> Мартин Гарднер (1914–2010), американский писатель, особенно хорошо известный по рубрике «Математические игры» в журнале Scientific American и книгам по занимательной математике. <...> Тогда решение головоломки для общего случая не только принесёт большее удовлетворение, но может оказаться проще. <...> Таблица 3Ч3, которую нужно заполнить целыми числами от 1 до 9, чтобы получился магический квадрат Магический квадрат. <...> В любом случае У ч е б н ы й р а з д е л О б щ и е с т р а т е г и и р а з р а б о т ки а л г о р и т м о в 27 Головоломка «Фальшивая монета из восьми» (№10) из основного раздела книги иллюстрирует стратегию «уменьшай в постоянное число раз», вариант стратегии «уменьшай и властвуй». <...> Примером является первое решение головоломки «Разделение прямоугольника» (№3) в основном разделе книги. <...> Тримино должны покрыть все клетки, кроме отсутствующей, без наложения друг на друга. <...> Хорошее упражнение для читателя—решение двух версий головоломки «Задача Баше о гирях» (№115), в которых используется двоичная и вариация троичной систем соответственно. <...> В качестве примера рассмотрим вариант очень старой и известной головоломки. <...> Граф пространства состояний для этой <...>
Алгоритмические_головоломки.pdf
УДК 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
Стр.5
ОГЛАВЛЕНИЕ
Предисловие в вопросах и ответах . . . . . . . . . . . . . . . . . . . . . . 7
О чем эта книга? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Для кого эта книга? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Какие головоломки включены в книгу? . . . . . . . . . . . . . . .
Подсказки, решения и комментарии . . . . . . . . . . . . . . . . . . 10
Что представляет собой учебный раздел? . . . . . . . . . . . . . . 11
Почему в книге два указателя? . . . . . . . . . . . . . . . . . . . . . . . 11
Благодарности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Список головоломок . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Головоломки учебного раздела . . . . . . . . . . . . . . . . . . . . . . . . 13
Головоломки основного раздела . . . . . . . . . . . . . . . . . . . . . . . 14
Головоломка в качестве эпиграфа: кто это сказал? . . . . 18
Глава1. Учебный раздел . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Общие стратегии разработки алгоритмов . . . . . . . . . . . . . . 19
Методы анализа алгоритмов . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
Глава2. Головоломки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
Лёгкие головоломки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
Головоломки средней сложности . . . . . . . . . . . . . . . . . . . . . . 68
Сложные головоломки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
9
Глава3. Подсказки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
Глава4. Решения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
Лёгкие головоломки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
Головоломки средней сложности . . . . . . . . . . . . . . . . . . . . . . 159
Сложные головоломки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
Указатель головоломок, сгруппированных по методам
разработки и анализа алгоритмов . . . . . . . . . . . . . . . 315
Анализ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
Инварианты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
Поиск с возвратом . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
Уменьшай и властвуй . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
Разделяй и властвуй . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
Динамическое программирование . . . . . . . . . . . . . . . . . . . . . 319
Полный перебор . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
Жадный подход . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
Итерационное улучшение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
Преобразуй и властвуй . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
Другие методы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
Предметно-именной указатель . . . . . . . . . . . . . . . . . . . . . . . . . . 323
Стр.7