Рефетека.ру / Информатика и програм-ие

Реферат: Динамическое программирование

Динамическое программирование

Довольно часто на олимпиадах встречаются задачи, провоцирующие к применению алгоритмы перебора. Но простой подсчет числа вариантов убеждает в неэффективности такого подхода. Для решения таких задач используется метод динамического программирования. Суть его заключается в том, что для отыскания решения поставленной задачи решается похожая (или похожие), но более простая. При этом осуществляется переход к еще более простым и так далее, пока не доходят до тривиальной.

Из предыдущего рассуждения видно, что решение можно оформить рекурсивно. Но простое применение этого приема очень легко может привести к переполнению стека. Необходимо позаботиться об оптимизации рекурсивных проходов и не вычислять одно и то же значение несколько раз, сделать так называемое отсечение. Можно вообще отказаться от рекурсии и решать задачу "наоборот" — прежде "решить" тривиальные случаи, а затем переходить ко все более сложным. В авторских решениях подобных задач почти всегда встречается второй путь (он несколько быстрее), но в этом занятии рассмотрим оба — первый гораздо доступнее для понимания.

Для решения таких задач существует специальная теория, большая заслуга в ее создании принадлежит Р.Беллману. В общем виде она достаточна сложна, поэтому здесь не рассматривается. В то же время конкретные задачи, рассмотренные ниже, вполне могут сформировать (хотя бы на интуитивном уровне) идеи, лежащие в основе решения задач данного класса.

Первые две задачи, строго говоря, нельзя отнести к указанному классу, но приемы, использованные при их решении, очень сходны с таковыми у задач, рассматриваемых на этом занятии. Остальные задачи в свое время встречались на различных олимпиадах (а некоторые с тех пор стали "фольклорными") и расположены (по мнению автора публикации) в порядке возрастания сложности. Для простоты будем считать, что в большинстве задачах исходные данные таковы, что результат поместится в тип LongInt. Справедливости ради отметим, что такое ограничение существует не всегда, и в последних двух задачах приходится либо использовать тип Double, либо дополнительно реализовывать "длинную арифметику".

Числа Фибоначчи

Вычислить N-ое число в последовательности Фибоначчи, — 1, 1, 2, 3, 5, 8, ... — в которой первые два члена равны единице, а все остальные представляют собой сумму двух предыдущих.

Формат входных данных

Одно число 0

Похожие работы:

  1. • Динамическое программирование (задача о загрузке)
  2. • Задача динамического программирования
  3. • Динамическое программирование
  4. • Динамическое программирование
  5. • Динамическое программирование и вариационное исчисление
  6. •  ... целочисленного, нелинейного и динамического программирования.
  7. •  ... метода динамического программирования и метода ветвей ...
  8. • Реализация на ЭВМ решения задачи оптимальной политики ...
  9. • Задачи математического программирования
  10. • Определение оптимального плана замены оборудования
  11. • Динамическое программирование, алгоритмы на графах
  12. • Моделирование систем массового обслуживания
  13. • Оптимальное распределение средств на расширение ...
  14. • Линейное и динамическое программирование
  15. • Модель распределения ресурсов
  16. • Нахождение оптимального плана производства продукции ...
  17. • Экономико-математические методы
  18. • Билеты математические методы исследования экономики
  19. • Математическое программирование и моделирование в экономике и ...
Рефетека ру refoteka@gmail.com