На прошлых занятиях мы научились пользоваться рекурсией. Теперь применим свои знания при изучении текущей темы. Многое из данного материала может показаться очень знакомым. Так это и хорошо. Будет легче разбираться. Всех новичков попрошу не торопиться смотреть решения задач, а предварительно максимально полно прочувствовать способ получения решения. Итак преступим.
Рекуррентные соотношения часто бывают незаменимы в тех случаях, когда задача решается методом динамического программирования, которому будут посвящены отдельные темы. Общая идея такова: для решения более полной задачи мы используем решения небольших подзадач. Эти соотношения обычно записывают в виде формулы. Например, для вычисление факториала это будет fact(N) = fact(N-1) * N. Как и для любой рекурсии, рекуррентная формула должна содержать терминальное условие.
На практике обычно складывается такая ситуация: для придумывания формулы уходит довольно много времени, а написание программы занимает считанные минуты. Это нормальная ситуация. Поэтому новичкам просьба быть к этому готовыми.
Более подробную вводную часть читайте в книге Михаила Долинского.
В данной теме рассмотрим ряд очень полезных задач
Рекуррентное соотношение с одним параметром:
3. Суммы
2. Отбор в разведку
6. Видеосалон
5. Двоичные числа (в авторской версии рассматривается реализация с двумя параметрами)
Рекуррентное соотношение с двумя параметрами:
10. Треугольник (IOI 1994)
12. Цветочный магазинчик (IOI 1999)
1. Лабиринт
4. Методист О.Г.
7. Палиндром
8. Производство касет
9. Юбилей
11. Торговые скидки
Все задачи по мере решения будут разобраны в отдельных постах.
Комментариев нет:
Отправить комментарий