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

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ и все-все-все:
Как решать олимпиадные и "ЖИЗНЕННЫЕ" ПРОГРАММИСТСКИЕ ЗАДАЧИ № 258

Динамическое программирование и все-все-все: Как решать олимпиадные и "жизненные" программистские задачи
URSS. 2021. 200 с. ISBN 978-5-9710-8864-6.
Типографская бумага

Аннотация

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


Содержание
Введение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 ? n33
2.2.2. Покрытие прямоугольника 3 ? n39
2.3.Вычисление рекуррентностей45
2.4.Что еще почитать46
2.5.Задачи46
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
Глава 7. Динамическое программирование и последовательности93
7.1.Палиндром93
7.2.Самый длинный палиндром97
7.3.Количество палиндромов100
7.4.Наибольшая общая подпоследовательность101
7.5.Заключение103
7.6.Упражнения103
Глава 8. Динамическое программирование и подмножества105
8.1.Размен 2105
8.2.Задача о рюкзаке109
8.3.Задача линейного разбиения112
8.4.Заключение116
8.5.Упражнения117
8.5.1. Суммы117
8.5.2. Копилка117
Глава 9. Динамическое программирование и матрицы119
9.1.Путь в матрице 2119
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
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.Размен 2180
8.2.Задача о рюкзаке182
8.3.Задача линейного разбиения182
Глава 9. Динамическое программирование и матрицы184
9.1.Путь в матрице 2184
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 лет занимается подготовкой школьников и студентов к олимпиадам по программированию и информатике.