Обложка Довгалюк П.М. Динамическое программирование и все-все-все: Как решать олимпиадные и 'жизненные' программистские задачи
Id: 272440
629 руб.

Динамическое программирование и все-все-все:
Как решать олимпиадные и "жизненные" программистские задачи № 258

URSS. 2021. 200 с. ISBN 978-5-9710-8865-3.
  • Твердый переплет

Аннотация

Динамическое программирование — это метод решения переборных задач. Эта книга отличается от других, посвященных динамическому программированию, тем, что оно рассматривается, начиная с математических идей, лежащих в его основе. Затем постепенно выстраивается подход к применению этих идей. Переходя от более простых задач к более сложным, читатель узнает о различных способах использования динамического программирования, поймет,...(Подробнее) как применять эти идеи при самостоятельном решении задач. В книге есть набор упражнений и задач для решения на бумаге и на компьютере. В основном текст книги и задачи отражают современную олимпиадную практику, но есть и отсылки к промышленному программированию.

Книга будет интересна всем, кто занимается прикладным программированием и принимает участие в олимпиадах по программированию, в том числе старшеклассникам, студентам и учителям информатики.


Содержание
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Глава 1. Рекуррентные соотношения . . . . . . . . . . . . . 9
1.1.Ханойская башня . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.Как решать задачи с рекуррентностями . . . . . . . . . . . 13
1.3.Задача о разрезании пиццы . . . . . . . . . . . . . . . . . . . 13
1.4.Задача Иосифа Флавия . . . . . . . . . . . . . . . . . . . . . . 16
1.5.Лягушка и шестиугольник . . . . . . . . . . . . . . . . . . . . 18
1.6.Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.7.Что еще почитать . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.8.Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.9.Ответы на задачи . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Глава 2. Вычисление рекуррентностей на компьютере . . . . . . . . . . . . . . . . . . . . . . . 29
2.1.Числа Фибоначчи . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.1.1. Рекурсивный алгоритм для вычисления чисел Фибоначчи . . . . . . . . . . . . . 30
2.1.2. Вычисление чисел Фибоначчи с помощью последовательного заполнения массива . . . . . . . . . 32
2.2.Домино . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.2.1. Покрытие прямоугольника 2 × n . . . . . . . . . . . . . 33
2.2.2. Покрытие прямоугольника 3 × n . . . . . . . . . . . . . 39
2.3.Вычисление рекуррентностей . . . . . . . . . . . . . . . . . 45
2.4.Что еще почитать . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.5.Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464 Содержание
2.6.Ответы на задачи . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.7.Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
Глава 3. Динамическое программирование . . . . . . . . 49
Глава 4. Динамическое программирование и одно целое число . . . . . . . . . . . . . . . . . . . . 53
4.1.Размен . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.2.Ход конем . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.3.Количество способов решения задачи . . . . . . . . . . . . 61
4.4.Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.5.Решения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.6.Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
Глава 5. Динамическое программирование и два целых числа . . . . . . . . . . . . . . . . . . . . . 67
5.1.Биномиальные коэффициенты . . . . . . . . . . . . . . . . . 67
5.2.Задача о лесенках . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.3.Путь в матрице . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.4.Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.5.Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
Глава 6. Динамическое программирование и одномерные массивы . . . . . . . . . . . . . . . . . 79
6.1.Наилучшее решение задачи
(задача о кузнечике со стоимостями) . . . . . . . . . . . . . 79
6.2.Сообщение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.3.Наибольшая возрастающая подпоследовательность . . . . . . . . . . . . . . . . . . . . . . 84
6.4.Наилучшее расписание . . . . . . . . . . . . . . . . . . . . . . 86
6.5.Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
6.6.Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90Содержание 5
Глава 7. Динамическое программирование и последовательности . . . . . . . . . . . . . . . . . . 93
7.1.Палиндром . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
7.2.Самый длинный палиндром . . . . . . . . . . . . . . . . . . 97
7.3.Количество палиндромов . . . . . . . . . . . . . . . . . . . . 100
7.4.Наибольшая общая подпоследовательность . . . . . . . . 101
7.5.Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
7.6.Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
Глава 8. Динамическое программирование и подмножества . . . . . . . . . . . . . . . . . . . . . . 105
8.1.Размен 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
8.2.Задача о рюкзаке . . . . . . . . . . . . . . . . . . . . . . . . . . 109
8.3.Задача линейного разбиения . . . . . . . . . . . . . . . . . . 112
8.4.Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
8.5.Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
8.5.1. Суммы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
8.5.2. Копилка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
Глава 9. Динамическое программирование и матрицы . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
9.1.Путь в матрице 2 . . . . . . . . . . . . . . . . . . . . . . . . . . 119
9.2.Маршруты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
9.3.Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
Глава 10. Динамическое программирование по профилю . . . . . . . . . . . . . . . . . . . . . . . . . 125
10.1. Снова домино . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
10.2. Задача о симпатичных узорах . . . . . . . . . . . . . . . . . 132
10.3. Изломанные профили . . . . . . . . . . . . . . . . . . . . . . . 137
10.4. Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
Глава 11. Динамическое программирование и игры с полной инфор-мацией . . . . . . . . . . 139
11.1. Игра Баше . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
11.2. Игра умножения . . . . . . . . . . . . . . . . . . . . . . . . . . 145
11.3. Игра «Ферзя в угол» . . . . . . . . . . . . . . . . . . . . . . . . 150
11.4. Крестики-нолики . . . . . . . . . . . . . . . . . . . . . . . . . . 153
11.5. Обобщенный алгоритм для анализа антагонистических игр с полной информацией . . . . . . 159
11.6. Что еще почитать . . . . . . . . . . . . . . . . . . . . . . . . . . 161
Глава 12. Динамическое программирование и все-все-все . . . . . . . . . . . . . . . . . . . . . . . . 163
12.1. Поиск кратчайшего пути . . . . . . . . . . . . . . . . . . . . . 163
12.2. Мемоизация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
12.3. Игры с полной информацией посложнее . . . . . . . . . . 165
Приложение. Исходные тексты решений задач . . . . . 167
Глава 2. Вычисление рекуррентностей на компьютере . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
2.2.Домино . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
Глава 4. Динамическое программирование и одно целое число . . . . . . . . . . . . . . . . . . . . . . . . 168
4.1.Размен . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
4.2.Ход конем . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
Глава 5. Динамическое программирование и два целых числа . . . . . . . . . . . . . . . . . . . . . . . . . 170
5.1.Биномиальные коэффициенты . . . . . . . . . . . . . . . 170
5.2.Задача о лесенках . . . . . . . . . . . . . . . . . . . . . . . 170
5.3.Путь в матрице . . . . . . . . . . . . . . . . . . . . . . . . 171
Глава 6. Динамическое программирование и одномерные массивы . . . . . . . . . . . . . . . . . . . . . 172
6.1.Кузнечик . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172Содержание 7
6.2.Сообщение . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
6.3.Наибольшая возрастающая подпоследовательность . . . 173
6.4.Наилучшее расписание . . . . . . . . . . . . . . . . . . . . 174
Глава 7. Динамическое программирование и последовательности . . .. . . . 176
7.1.Палиндром . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
7.2.Самый длинный палиндром . . . . . . . . . . . . . . . . 177
7.3.Количество палиндромов . . . . . . . . . . . . . . . . . . 179
7.4.Наибольшая общая подпоследовательность . . . . . . . 180
Глава 8. Динамическое программирование и подмножества . . 180
8.1.Размен 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
8.2.Задача о рюкзаке . . . . . . . . . . . . . . . . . . . . . . . 182
8.3.Задача линейного разбиения . . . . . . . . . . . . . . . . 182
Глава 9. Динамическое программирование и матрицы . . . . . 184
9.1.Путь в матрице 2 . . . . . . . . . . . . . . . . . . . . . . . 184
9.2.Маршруты . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
Глава 10. Динамическое программирование по профилю . . . . 187
10.1. Снова домино . . . . . . . . . . . . . . . . . . . . . . . . . 187
10.2. Задача о симпатичных узорах . . . . . . . . . . . . . . . 188
Глава 11. Динамическое программирование и игры с полной инфор-мацией . . . . . . . . . . . . . . . . 189
11.1. Игра Баше . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
11.2. Игра умножения . . . . . . . . . . . . . . . . . . . . . . . . 190
11.3. Игра «Ферзя в угол» . . . . . . . . . . . . . . . . . . . . . . 191
11.4. Крестики-нолики . . . . . . . . . . . . . . . . . . . . . . . 192
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196

Введение

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

Правильное решение для тех самых начинающих часто кажется каким-то волшебством. И непонятно, как, зная такое решение, научиться придумывать такое же волшебство самому, даже если знать, что использовалась техника, называемая «динамическим программированием».

Это самое «динамическое программирование» помогает организовать перебор ответов так, чтобы он укладывался в отведенное время. Или же решение строится совсем иначе, и перебор становится не нужен.

Динамическое программирование используется не только в искусственных олимпиадных задачах, с которыми в реальной жизни большинство программистов и не сталкивается. Сам принцип встречается довольно часто: и в разработке игр и ботов для них (например, при поиске кратчайшего пути), и в компиляторах (некоторые действительно их пишут), и в веб-программировании (в совсем уж широком смысле).

Эта книга отличается от других, посвященных динамическому программированию, тем, что мы попробуем разобраться с ним, отталкиваясь от математических идей, лежащих в основе. Алгебре учат всех, а вот рекурсии — уже нет. Также мы рассмотрим, как можно улучшить уже существующие программы, использующие полный перебор (все-таки акцент у нас будет на олимпиадные задачи, ведь не каждому захочется писать собственный компилятор).


Об авторе
Довгалюк Павел Михайлович
Кандидат технических наук, доцент Новгородского государственного университета им. Ярослава Мудрого. Имеет 17 лет стажа в промышленном программировании, 11 лет стажа работы в высшей школе. Работает в Институте системного программирования РАН над технологиями эмуляции и отладки. Более 10 лет занимается подготовкой школьников и студентов к олимпиадам по программированию и информатике.