Окулов, О. А. Пестов ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ 2-е издание (электронное) Москва БИНОМ. <...> Множество решаемых задач, вычисляемая функция и рекуррентные соотношения . <...> При «встрече» с новой проблемой (задачей) вы будете уже интуитивно чувствовать, знать, решается она или нет методом динамического программирования. <...> Другими словами, должны быть выведены (определены) функциональные зависимости (рекуррентные соотношения) между решениями подзадач. <...> Особенность динамического программирования как метода заключается и в том, что каждая подзадача решается только один раз. <...> Идеи метода динамического программирования используются, но детального «разговора» о них нет. <...> Рекурсивный вариант решения задачи очевиден для чисел, «укладывающихся» в диапазон LongInt. <...> Function Fib(n: LongInt): LongInt; Begin If n<2 Then Fib:=n Else Fib:=Fib(n–1)+Fib(n–2); End; Логика решения проиллюстрирована на рис. <...> При этом каждая подзадача решается только один раз. <...> Другими словами, мы 1 Если число Фибоначчи входит в стандартный диапазон LongInt (Int64), то никаких проблем с вещественными числами нет. <...> Procedure FibD(n: LongInt); Var i: LongInt; Begin F[0]:=0; F[1]:=1; For i:=2 To n Do F[i]:=F[i–1]+F[i–2]; WriteLn(F[n]); End; Так как для решения очередной подзадачи требуются результаты решения только двух предыдущих подзадач, то массив F излишен, достаточно двух переменных. <...> Мы определили понятие «подзадача», мы показали, как из решения подзадач «складывается» решение исходной задачи. <...> Function Comb(n, k: LongInt): LongInt; Begin If (k=0) Or (k=n) Then Comb:=1 Else Comb:=Comb(n–1,k)+Comb(n–1, k–1); End; Прорисуем рекурсивные вызовы функции Comb при вычислении, например,C5 3 (рис. <...> Но каждая подзадача в этом случае решается один раз, и результат её решения запоминается. <...> Последовательность вызовов функции Comb при вычисленииC5 3 Итак, решение: Procedure Comb(n, k: LongInt); {k<=n} Var i <...>
Динамическое_программирование.pdf
С. М. Окулов, О. А. Пестов
ДИНАМИЧЕСКОЕ
ПРОГРАММИРОВАНИЕ
3-е издание, электронное
Москва
Лаборатория знаний
2020
Стр.2
УДК 519.85(023)
ББК 22.18
О-52
С е р и я о с н о в а н а в 2008 г.
Окулов С. М.
О-52
Динамическое программирование / С. М. Окулов,
О. А. Пестов.—3-е изд., электрон.—М. : Лаборатория
знаний, 2020.—299 с.—(Развитие интеллекта
школьников).—Систем. требования: Adobe
Reader XI ; экран 10".— Загл. с титул. экрана.—Текст :
электронный.
ISBN 978-5-00101-683-0
В данной книге систематизирован материал по одному
из методов проектирования алгоритмов в информатике—
динамическому программированию. Предлагаемые задачи
решаются фактически по одной схеме, основанной на данном
методе, однако понять, что задача решается этим методом,
очень непросто. Для этого кроме знаний требуется усилие
подготовленного к решению таких задач интеллекта. Именно
этому способствуют содержание книги и стиль изложения
материала в ней.
Разобраны задачи, предлагавшиеся школьникам на всероссийских
олимпиадах по информатике разных лет, а также
на турнирах и конкурсах.
Для учащихся старших классов, студентов и преподавателей
информатики.
УДК 519.85(023)
ББК 22.18
Деривативное издание на основе печатного аналога: Динамическое
программирование / С. М. Окулов, О. А. Пестов.—
М. : БИНОМ. Лаборатория знаний, 2012.—296 с. : ил.—
(Развитие интеллекта школьников).
ISBN 978-5-9963-0483-7
В соответствии со ст. 1299 и 1301 ГК РФ при устранении
ограничений, установленных техническими средствами защиты
авторских прав, правообладатель вправе требовать от нарушителя
возмещения убытков или выплаты компенсации
ISBN 978-5-00101-683-0
○c Лаборатория знаний, 2015
Стр.3
Оглавление
Вместо предисловия .................................. 5
Введение ............................................ 9
Глава 1. Простые задачи ............................. 13
1.1. Числа Фибоначчи ............................ 13
1.2. Биномиальные коэффициенты, или Нахождение числа
сочетаний .................................. 17
1.3. Наибольший квадрат .......................... 20
1.4. Задача о Черепашке........................... 26
Глава 2. Основной принцип и метод реализации на основе
рекуррентных соотношений........................... 33
2.1. Вводные замечания ........................... 33
2.2. Множество решаемых задач, вычисляемая функция
и рекуррентные соотношения ................... 35
2.3. Граф зависимостей задач ....................... 38
2.4. Общая схема ................................ 42
2.5. Пример решения задачи ....................... 45
Глава 3. Типы задач по динамическому
программированию .................................. 49
3.1. Табличный метод решения...................... 49
3.2. Задачи на отрезках ........................... 87
3.3. Задачи на деревьях .......................... 106
3.4. Задачи на подмножествах ..................... 140
3.5. Динамическое программирование по профилю ..... 156
Приложение I. Динамическое программирование
как метод решения задач оптимизации . . . ............. 201
Введение...................................... 201
1. Метод динамического программирования: основные
положения................................. 206
2. Примеры задач.............................. 209
2.1. Задача о распределении ресурсов ............. 209
Стр.4
4
Оглавление
2.2. Задача о рюкзаке ......................... 226
2.3. Задачи о критических путях в графе .......... 237
2.3.1. Перечисление путей в графе ................ 238
2.3.2. Кратчайший путь в графе .................. 241
2.3.3. Максимальный путь в графе ................ 249
Приложение II. Справочные данные о задачах
динамического программирования.................... 260
Стр.5