Задача “Цветочный магазин” (Рекуррентное соотношение с двумя параметрами)

Условие задачи: ссылка
Основная идея: Данная задача была представлена на IOI’99. Разбор этой задачи можно найти в первой книги Михаила Долинского и в  “Методике решения задач по информатике”. Рекомендую ознакомится.
Пусть f(i,j) – максимальная эстетическая ценность размещения i букетов по j вазам.
Рассмотри первоначальная таблицу a:

Задача “Двоичные числа” (Рекуррентное соотношение с одним параметром )

Условие задачи: ссылка
Основная идея: Чтобы прочувствовать решение задачи предлагаю начать с более простого случая, когда K=2. Обозначим K(n) – количество n битных чисел без 2-ых подряд идущих единиц. K(1) = 2 – факт очевидный. Найдем решение для n=2. На вторую позицию можно поставить либо ноль, либо единицу. Ноль можно ставить смело, а вот единица может образовать запрещенную комбинацию, если на первой позиции также стояла единица. Проанализируем таблицу:

Задача “Треугольник” (Рекуррентное соотношение с двумя параметрами)

Условие задачи: ссылка
Основная идея:  Данная задача является интерпретацией классической задачи “Черепашка”. Сначала давайте разберемся как будем хранить наш дивный треугольник в памяти. По условию задачи он выглядит так:
          7
        3   8
      8   1   0
    2   7   4   4
  4   5   2   6   5
Нам бы хотелось иметь более дружественный вид. Например в виде матрицы:
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

Задача “Видеосалон” (Рекуррентное соотношение с одним параметром)

Условие задачи: ссылка
Основная идея:  Для успешного решения задачи было бы неплохо знать подход к решению классической задачи “Рюкзак” на Динамическое программирование. Все решение сводится к заполнению трех массивов: s,ns,ms (авторские названия).
Массив s:
s[i] == 1, если можно набрать суммарное время i, используя один или несколько фильмов.
s[i] == 0, в противном случае.
Массив ns:
ns[i] – количество способов, которыми можно набрать суммарное время i одним или несколькими фильмами. ns[i] не равен нулю только в том случае, если s[i] не равно нулю.
Массив ms:
ms[i] == 1, если время i было промежуточным для получения бОльшего времени I.
ms[i] == 0, в противном случае.

Исходный код: здесь

P.S: Признаюсь долго приходило понимание решения этой задачи. Основные моменты: строка 35 и способ формирования ответа.

Задача “Отбор в разведку” (Рекуррентное соотношение с одним параметром)

Условие задачи: ссылка
Основная идея:  Обозначим K(N) – ответ на задачу, а именно количество групп из 3 человек, которых можно послать в разведку из первоначальных N человек. Определим терминальное условие: K(1) = 0; K(2) = 0; K(3) = 1. Теперь рассмотрим шеренгу солдат для N=6 и N=7. Пусть N будет равно 6. Занумеруем солдат слева направо в порядке возрастания:

Полная шеренга(N=6):	1 2 3 4 5 6
Только четные:	2 4 6
Только нечетные:	1 3 5

Полная шеренга (N=7)	1 2 3 4 5 6 7
Только четные:	2 4 6
Только нечетные:	1 3 5 7

Вывод можно сделать однозначный. Если N-четное, то K(N) = K(N/2) + K(N/2) = 2*K(N/2).  В качестве первого слагаемого была шеренга, составленная из четных солдат, в качестве второго – из нечетных. Т.е. K(6) = 2*K(3) = 2*1 = 2.
Если N-нечетное, то можно формулу можно записать так: K(N) = K(N/2) + K(N-N/2). Слагаемые такие же и в первом случае. Т.е. K(7)= K(3) + K(4) = K(3) + K(2) + K(2) = 1 + 0 + 0 = 1.
Справедливости ради стоит заметить, что формула полученная для нечетного N также работает и для четного N.
Исходный код: здесь

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

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

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

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

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

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

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

Задача “Суммы” (Рекуррентные соотношения с одним параметром)

Условие задачи:  ссылка
Основная идея:  Идея, предложенная автором, помогает прочувствовать задачу максимально эффективно. Опишу ее вкратце (когда перечитывал пост целиком, улыбнуло слово “вкратце”):
1)  Итак, ручками составляем ответы для N в интервале от [1,8].
2) Обозначим  K(i) – ответ на задачу, т.е. количество разложений числа i на слагаемые, которые являются степенями двойки
3) Рассмотрим ответы, составленные на пункте 1) для N=4 и N=5.

N = 4	N=5
4	4+1
2+2	2+2+1
2+1+1	2+1+1+1
1+1+1+1	1+1+1+1+1

Что может сразу броситься в глаза?

Страничка по ИИ

Здесь буду публиковать интересные ссылки по тематике ИИ.

1) Алгоритм A* для новичков. Очень популярное объяснение + работающий визуализатор с функцией пошаговой работы алгоритма.