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

Сентябрь 7, 2022

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

Содержание

2. Задача «Возрастающая подпоследовательность»
3. Пример
4. Решение
5. Детали реализации
6. Сдать можно как задачу №613 http://informatics.mccme.ru/mod/statements/view3.php?chapterid=613#1
7. Задача «Таблица»
9. Первый способ
10. Второй способ С диагоналями. Нужен, чтобы хранить не 3 строки одной таблицы (B), а по две
11. L R B Что должно получиться Первую строку заполняем первой строкой из А Заполняем вторую строку
12. L R B Что должно получиться Первую строку заполняем первой строкой из А Заполняем вторую строку
13. L R B Что должно получиться Теперь можно и третью строку В заполнить B[i, j] =
14. L R B Что должно получиться B[i, j] = 2*B[i-1,j] + L[i-1,j-1] + R[i+1,j+1] L[i, j]
15. L R B Что должно получиться B[i, j] = 2*B[i-1,j] + L[i-1,j-1] + R[i+1,j+1] L[i, j]
16. L R B Что должно получиться B[i, j] = 2*B[i-1,j] + L[i-1,j-1] + R[i+1,j+1] L[i, j]
17. L R B Что должно получиться Теперь можно и третью строку В заполнить B[i, j] =
18. L R B Что должно получиться Далее заполняем по формулам третьи строки L и R B[i,
19. L R B Что должно получиться Далее заполняем по формулам третьи строки L и R и
20. L R B Что должно получиться Далее заполняем по формулам третьи строки L и R и
21. Задача «Черепашка»
22. Решение задачи «Черепашка». П.П. Полный перебор вариантов – универсальный способ решения. Но рассмотрим его потенциальные возможности
23. Длительность вычислений
24. Решение задачи «Черепашка». Д.П.
25. Код (на паскале)
26. Вычисление пути
27. Вычисление пути
29. Скачать презентацию

Слайд 2

Задача «Возрастающая подпоследовательность»

Слайд 3

Пример

Слайд 4

Решение

Слайд 5

Детали реализации

Слайд 6

Сдать можно как задачу №613
http://informatics.mccme.ru/mod/statements/view3.php?chapterid=613#1

Слайд 7

Задача «Таблица»

Слайд 8

Слайд 9

Первый способ

Слайд 10

Второй способ
С диагоналями. Нужен, чтобы хранить не 3 строки одной таблицы

(B), а по две строки трех таблиц (L, R, B)

Слайд 11

L
R
B
Что должно
получиться
Первую строку заполняем первой строкой из А
Заполняем вторую строку

B по-честному

Слайд 12

L
R
B
Что должно
получиться
Первую строку заполняем первой строкой из А
Заполняем вторую строку

B по-честному

Слайд 13

L
R
B
Что должно
получиться
Теперь можно и третью строку В заполнить
B[i, j] =

2*B[i-1,j] + L[i-1,j-1] + R[i+1,j+1]
L[i, j] = L[i-1,j-1] + B[i,j]
R[i, j] = R[i-1,j+1] + B[i,j]

Заполняем вторую строку L и R по формулам

Слайд 14

L
R
B
Что должно
получиться
B[i, j] = 2*B[i-1,j] + L[i-1,j-1] + R[i+1,j+1]
L[i, j]

= L[i-1,j-1] + B[i,j]
R[i, j] = R[i-1,j+1] + B[i,j]

Теперь можно и третью строку В заполнить

Слайд 15

L
R
B
Что должно
получиться
B[i, j] = 2*B[i-1,j] + L[i-1,j-1] + R[i+1,j+1]
L[i, j]

= L[i-1,j-1] + B[i,j]
R[i, j] = R[i-1,j+1] + B[i,j]

Теперь можно и третью строку В заполнить

Слайд 16

L
R
B
Что должно
получиться
B[i, j] = 2*B[i-1,j] + L[i-1,j-1] + R[i+1,j+1]
L[i, j]

= L[i-1,j-1] + B[i,j]
R[i, j] = R[i-1,j+1] + B[i,j]

Теперь можно и третью строку В заполнить

Слайд 17

L
R
B
Что должно
получиться
Теперь можно и третью строку В заполнить
B[i, j] =

2*B[i-1,j] + L[i-1,j-1] + R[i+1,j+1]
L[i, j] = L[i-1,j-1] + B[i,j]
R[i, j] = R[i-1,j+1] + B[i,j]

Слайд 18

L
R
B
Что должно
получиться
Далее заполняем по формулам третьи строки L и R
B[i,

j] = 2*B[i-1,j] + L[i-1,j-1] + R[i+1,j+1]
L[i, j] = L[i-1,j-1] + B[i,j]
R[i, j] = R[i-1,j+1] + B[i,j]

Слайд 19

L
R
B
Что должно
получиться
Далее заполняем по формулам третьи строки L и R

и т.д.

B[i, j] = 2*B[i-1,j] + L[i-1,j-1] + R[i+1,j+1]
L[i, j] = L[i-1,j-1] + B[i,j]
R[i, j] = R[i-1,j+1] + B[i,j]

Слайд 20

L
R
B
Что должно
получиться
Далее заполняем по формулам третьи строки L и R

и т.д.

B[i, j] = 2*B[i-1,j] + L[i-1,j-1] + R[i+1,j+1]
L[i, j] = L[i-1,j-1] + B[i,j]
R[i, j] = R[i-1,j+1] + B[i,j]

Слайд 21

Задача «Черепашка»

Слайд 22

Решение задачи «Черепашка». П.П.
Полный перебор вариантов – универсальный способ решения. Но

рассмотрим его потенциальные возможности
Пусть дана таблица 4х4. Любой путь состоит из трёх перемещений вверх и трех перемещений вправо, т.е. длина пути равна шести. Другими словами, дано 6 шагов, из них 3 выбираются для перемещений вверх, оставшиеся 3 – для перемещений вправо определяются однозначно. Т.о. количество способов выбора трех перемещений из шести
При нахождении суммы (стоимости) пути потребуется 5 операци сложения, всего 100 операций. Оценим время решения задачи для компьютера с миллионным быстродействием (см. презентация предыдущих занятий о сложности алгоритмов и быстродействии на примере задачи о тупоугольном треугольнике)

Слайд 23