Динамическое программирование. Олимпиадные задачи. - презентация

1 Динамическое программирование. Олимпиадные задачи.

2 Олимпиадные задачи по информатике отличаются тематическим разнообразием. Однако, можно выделить наиболее часто встречающиеся разделы информатики, по которым разрабатываются олимпиадные задачи. К ним можно отнести: перебор вариантов и методы его сокращения;перебор вариантов и методы его сокращения; динамическое программирование;динамическое программирование; комбинаторика;комбинаторика; сортировка и поиск;сортировка и поиск; обработка последовательностей;обработка последовательностей; элементы вычислительной геометрии;элементы вычислительной геометрии; алгоритмы на графах.алгоритмы на графах.

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

4 Метод динамического программирования сверху это простое запоминание результатов решения тех подзадач, которые могут повторно встретиться в дальнейшем. Динамическое программирование снизу включает в себя переформулирование сложной задачи в виде рекурсивной последовательности более простых подзадач. Метод динамического программирования сверху это простое запоминание результатов решения тех подзадач, которые могут повторно встретиться в дальнейшем. Динамическое программирование снизу включает в себя переформулирование сложной задачи в виде рекурсивной последовательности более простых подзадач.

5 Только вправо или вниз ( Игровое поле N x M заполняется целыми числами, одно неотрицательное целое число в каждой клетке. Цель игры состоит в том, чтобы пройти по любому разрешенному пути от верхнего левого угла до правого нижнего. Целое число в каждой клетке указывает, какой длины шаг должен быть из текущей клетки. Все шаги могут быть или направо или вниз. Если в результате какого-либо шага игрок покидает пределы поля, такой шаг запрещается. На рис. 1 приведен пример игрового поля 3 x 4, где сплошная окружность показывает положение начала, а пунктирная окружность – цель. Рис. 2 показывает три возможных пути от начала до цели для рассматриваемого примера игрового поля, с удаленными промежуточными числами.

6 Требуется написать программу, которая определит число различных вариантов путей от верхнего левого угла до правого нижнего. INPUT.TXTOUTPUT.TXT

7 Входные данные Входной файл INPUT.TXT содержит в первой строке размеры поля N (1 N 70) и M (1 M 70). В последующих N строках входного файла, каждая из которых описывает отдельную строку игрового поля, записаны через пробел по M целых чисел – длины шагов из клеток данной строки. Выходные данные Выходной файл OUTPUT.TXT должен содержать одно число - число различных вариантов путей от верхнего левого угла до правого нижнего. Для каждого поля будет менее чем 2 31 различных путей.

8 Рис.2

9 b[1,1]:=1; for i:=1 to n do for j:=1 to m do begin if b[i,j]>0 then begin if (i+a[i,j] 0) then b[i+a[i,j],j]:=b[i+a[i,j],j]+b[i,j]; if (j+a[i,j] 0) then b[i,j+a[i,j]]:=b[i,j+a[i,j]]+b[i,j]; end; end;

10 Саша, не сделал домашнюю работу, зато купил шоколадку. И, по глупости, начал распечатывать ее прямо на уроке... Шелест золотинки услышала учительница. Она хотела вызвать в школу родителей, но Саша уговорил ее не вызывать их, а дать дополнительное задание. Учительница внимательно посмотрела на шоколадку (она была размером 3х4 плиток), разделила на кусочки по две плитки и угостила всех, кто сделал домашнюю работу. А Сашу попросила написать программу, которая определяет, сколько существует способов деления шоколадки размером 3×N плиток на кусочки по две плитки. Для выполнения задания Саше нужна помощь. Шоколадка

11 N=2 N=4

12 function F(x:integer):longint; begin if x mod 2 =1 then F:=0 else if x = 0 then F:=1 else if x=2 then F:=3 else F:=4*F(x-2)-F(x-4); end; Функция вычисления кол-ва вариантов деления шоколадки

13

14 Когда Миша и Маша покупали подарок, возникла интересная ситуация. У них была в распоряжении только одна большая купюра, а у продавца – некоторое количество мелочи. Дело происходило утром, поэтому продавцу нужно было экономить мелочь, и он хотел отдать сдачу минимальным количеством монет. Подумав некоторое время, они точно определили, с каким количеством монет продавцу придется расстаться. А вы сможете решить такую задачу? Сдача

15 Входные данные В первой строке входного файла INPUT.TXT записано число N (1

16 Примеры INPUT.TXTOUTPUT.TXT

17 i123 a[i]157 a[i] номинал монеты. i b[i] i b[i] I требуемая сумма. b[i] минимальное кол-во монет.

18 b[0]:=0; for i:=1 to k do begin b[i]:= ; for j:=1 to n do begin if a[j]>i then continue; if b[i-a[j]]+1

19 Литература Беллман Р. Динамическое программирование. М.: Изд-во иностранной литературы, Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 15. Динамическое программирование // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. 2-е изд. М.: Вильямс, с. ISBN Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. М.: Издательский дом «Вильямс», Акулич И.Л. Глава 4. Задачи динамического программирования // Математическое программирование в примерах и задачах. М.: Высшая школа, с. ISBN Габасов Р., Кириллова Ф. М. Основы динамического программирования. Мн.: Изд-во БГУ, с.