воскресенье, 17 января 2010 г.

Рекуррентные соотношения

На прошлых занятиях мы научились пользоваться рекурсией. Теперь применим свои знания при изучении текущей темы. Многое из данного материала может показаться очень знакомым. Так это и хорошо. Будет легче разбираться. Всех новичков попрошу не торопиться смотреть решения задач, а предварительно максимально полно прочувствовать способ получения решения. Итак преступим.
Рекуррентные соотношения часто бывают незаменимы в тех случаях, когда задача решается методом динамического программирования, которому будут посвящены отдельные темы. Общая идея такова: для решения более полной задачи мы используем решения небольших подзадач. Эти соотношения обычно записывают в виде формулы. Например, для вычисление факториала это будет fact(N) = fact(N-1) * N. Как и для любой рекурсии, рекуррентная формула должна содержать терминальное условие.
На практике обычно складывается такая ситуация: для придумывания формулы уходит довольно много времени, а написание программы занимает считанные минуты. Это нормальная ситуация. Поэтому новичкам просьба быть к этому готовыми.
Более подробную вводную часть читайте в книге Михаила Долинского.

В данной теме рассмотрим ряд очень полезных задач

Рекуррентное соотношение с одним параметром:
3.  Суммы
2.  Отбор в разведку
6.  Видеосалон
5.  Двоичные числа (в авторской версии рассматривается реализация с двумя параметрами)


Рекуррентное соотношение с двумя параметрами:
10. Треугольник (IOI 1994)
12. Цветочный магазинчик (IOI 1999)

1.  Лабиринт
4.  Методист О.Г. 
7.  Палиндром
8.  Производство касет
9.  Юбилей 
11. Торговые скидки

Все задачи по мере решения будут разобраны в отдельных постах.

Комментариев нет:

Отправить комментарий