Динамическое программирование
Динамическое
программирование
Довольно часто
на олимпиадах встречаются задачи, провоцирующие к применению алгоритмы
перебора. Но простой подсчет числа вариантов убеждает в неэффективности такого
подхода. Для решения таких задач используется метод динамического
программирования. Суть его заключается в том, что для отыскания решения
поставленной задачи решается похожая (или похожие), но более простая. При этом
осуществляется переход к еще более простым и так далее, пока не доходят до
тривиальной.
Из предыдущего
рассуждения видно, что решение можно оформить рекурсивно. Но простое применение
этого приема очень легко может привести к переполнению стека. Необходимо
позаботиться об оптимизации рекурсивных проходов и не вычислять одно и то же
значение несколько раз, сделать так называемое отсечение. Можно вообще
отказаться от рекурсии и решать задачу "наоборот" — прежде
"решить" тривиальные случаи, а затем переходить ко все более сложным.
В авторских решениях подобных задач почти всегда встречается второй путь (он
несколько быстрее), но в этом занятии рассмотрим оба — первый гораздо доступнее
для понимания.
Для решения
таких задач существует специальная теория, большая заслуга в ее создании
принадлежит Р.Беллману. В общем виде она достаточна сложна, поэтому здесь не
рассматривается. В то же время конкретные задачи, рассмотренные ниже, вполне
могут сформировать (хотя бы на интуитивном уровне) идеи, лежащие в основе
решения задач данного класса.
Первые две
задачи, строго говоря, нельзя отнести к указанному классу, но приемы,
использованные при их решении, очень сходны с таковыми у задач, рассматриваемых
на этом занятии. Остальные задачи в свое время встречались на различных
олимпиадах (а некоторые с тех пор стали "фольклорными") и расположены
(по мнению автора публикации) в порядке возрастания сложности. Для простоты
будем считать, что в большинстве задачах исходные данные таковы, что результат
поместится в тип LongInt. Справедливости ради отметим, что такое ограничение
существует не всегда, и в последних двух задачах приходится либо использовать
тип Double, либо дополнительно реализовывать "длинную арифметику".
Числа Фибоначчи
Вычислить N-ое
число в последовательности Фибоначчи, — 1, 1, 2, 3, 5, 8, ... — в которой
первые два члена равны единице, а все остальные представляют собой сумму двух
предыдущих.
Формат входных
данных
Одно число
0