Категория
Информатика
Тип
реферат
Страницы
2 стр.
Дата
22.10.2009
Формат файла
.rtf — Rich Text Format (Wordpad)
Архив
21327.zip — 9.48 kb
  • dinamicheskoe-programmirovanie_21327_1.rtf — 60.68 Kb
  • Readme_docus.me.txt — 125 Bytes
Рейтинг
10  из 10
Оценок
1
Оцените работу
Хорошо  или  Плохо


Текст работы

primer;
otstup;
program;
otst Динамическое программирование
Динамическое программирование
Довольно часто на олимпиадах встречаются задачи, провоцирующие к применению алгоритмы перебора. Но простой подсчет числа вариантов убеждает в неэффективности такого подхода. Для решения таких задач используется метод динамического программирования. Суть его заключается в том, что для отыскания решения поставленной задачи
решается похожая (или похожие), но более простая. При этом осуществляется
переход к еще более простым и так далее, пока не доходят до тривиальной.
Из предыдущего рассуждения видно, что решение можно оформить рекурсивно. Но простое применение этого приема очень легко может привести к переполнению стека. Необходимо позаботиться об оптимизации рекурсивных проходов и не вычислять одно и то же значение несколько раз, сделать так называемое отсечение. Можно вообще отказаться от рекурсии и решать задачу "наоборот" — прежде "решить" тривиальные случаи, а затем переходить ко все более сложным. В авторских решениях подобных задач почти всегда встречается второй путь (он несколько быстрее), но в этом занятии рассмотрим оба —
первый гораздо доступнее для понимания.
Для решения таких задач существует специальная теория, большая заслуга
в ее создании принадлежит Р.Беллману. В общем виде она достаточна сложна,
поэтому здесь не рассматривается. В то же время конкретные задачи, рассмотренные ниже, вполне могут сформировать (хотя бы на интуитивном уровне)
идеи, лежащие в основе решения задач данного класса.
Первые две задачи, строго говоря, нельзя отнести к указанному классу, но приемы, использованные при их решении, очень сходны с таковыми у задач, рассматриваемых на этом занятии. Остальные задачи в свое время



Ваше мнение



CAPTCHA