- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Олимпиадные задачи. Динамическое программирование презентация
Содержание
- 1. Олимпиадные задачи. Динамическое программирование
- 2. Задача «Таблица»
- 4. Первый способ
- 5. Второй способ С диагоналями. Нужен, чтобы хранить
- 6. L R B Что должно получиться
- 7. L R B Что должно получиться
- 8. L R B Что должно получиться
- 9. L R B Что должно получиться
- 10. L R B Что должно получиться
- 11. L R B Что должно получиться
- 12. L R B Что должно получиться
- 13. L R B Что должно получиться
- 14. L R B Что должно получиться
- 15. L R B Что должно получиться
Задача «Таблица»
Слайд 5Второй способ
С диагоналями. Нужен, чтобы хранить не 3 строки одной таблицы
(B), а по две строки трех таблиц (L, R, B)
Слайд 6L
R
B
Что должно
получиться
Первую строку заполняем первой строкой из А
Заполняем вторую строку
B по-честному
Слайд 7L
R
B
Что должно
получиться
Первую строку заполняем первой строкой из А
Заполняем вторую строку
B по-честному
Слайд 8L
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[i, j] = L[i-1,j-1] + B[i,j]
R[i, j] = R[i-1,j+1] + B[i,j]
Заполняем вторую строку L и R по формулам
Слайд 9L
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]
R[i, j] = R[i-1,j+1] + B[i,j]
Теперь можно и третью строку В заполнить
Слайд 10L
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]
R[i, j] = R[i-1,j+1] + B[i,j]
Теперь можно и третью строку В заполнить
Слайд 11L
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]
R[i, j] = R[i-1,j+1] + B[i,j]
Теперь можно и третью строку В заполнить
Слайд 12L
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[i, j] = L[i-1,j-1] + B[i,j]
R[i, j] = R[i-1,j+1] + B[i,j]
Слайд 13L
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]
L[i, j] = L[i-1,j-1] + B[i,j]
R[i, j] = R[i-1,j+1] + B[i,j]
Слайд 14L
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]
Слайд 15L
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]
