1. • Динамическое программирование (задача о загрузке)
  2. • Задача динамического программирования
  3. • Динамическое программирование
  4. • Динамическое программирование
  5. •  ... целочисленного, нелинейного и динамического программирования.
  6. • Определение оптимального плана замены оборудования
  7. • Линейное и динамическое программирование
  8. • Исследование операций
  9. • Билеты математические методы исследования экономики
  10. • Математическое программирование и моделирование в экономике и ...
  11. • Экзаменационные вопросы и билеты по предмету МАТЕМАТИЧЕСКИЕ ...
  12. • Задача квадратичного программирования с параметром в правых ...
  13. • Курсовая: Формирование инвестиционного портфеля
  14. • Шпаргалка: 5 различных задач по программированию
  15. • Организация РРЛ
  16. • Минимизация стоимостей перевозок
  17. • Динамическое и линейное программирование
  18. • Прикладная математика

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

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

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

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

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

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

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

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

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

Одно число 0

©2007—2016 Пуск!by | По вопросам сотрудничества обращайтесь в contextus@mail.ru