Как составить алгоритм комбинаторной задачи?

#objective_c #c #cpp #алгоритм

Уже второй день не могу составить алгоритм решения данной задачи.
+Даны три буквы - Б, С, К 
+Сколько существует способов заполнить этими буквами N-количество клеток, при условии что:

1) Никакая из букв не может быть записана подряд;
2) Буква С может быть только между буквами Б и К (или К и Б).

К примеру при N=3 существует четыре способы:

БКБ КБК БСК КСБ
    

Ответы

Ответ 1

Всё просто.
Обозначим a_i количество способов, которыми можно правильно заполнить ряд из i клеток.
Попробуем найти рекуррентное соотношение на a_i.
Как можно «собрать» строку длиной i? Вы начинаете с пустой строки, приписываете каждый
раз либо один символ (Б или К), либо пару символов (СК или СБ). При этом на каждом
шаге у вас правильная строка.
Итак, какой у нас последний шаг?

Вы приписываете к строке длины i-1 один символ. Правильная строка заканчивается либо
на Б, либо на К, поэтому чтобы получить правильную строку на этом шаге, вы приписываете
«противоположный» символ: К или Б. Такой шаг вы можете провести, имея любую правильную
строку длины i-1.
Вы приписываете к строке длины i-2 два символа: С и символ, «противоположный» последнему
символу в строке. Такой шаг вы можете провести, имея любую правильную строку длины i-2.

Строки, полученные при помощи шагов типа 1 и 2 не совпадают между собой (у вторых
на предпоследнем месте С), а значит, мы получили все возможные варианты без повторений.
Отлично, теперь подсчитаем общее количество путей. Вы можете сделать шаг типа 1 начиная
от a_{i-1} правильных слов, и шаг сам по себе однозначен. Вы можете сделать шаг типа
2 начиная от a_{i-2} правильных слов, и такой шаг тоже однозначен. Итого:
a_i = a_{i-1} + a_{i - 2}

Найдём начальные значения: легко видеть, что a_1 = 2, a_2 = 2.
Дальше легко. Вы можете применить любой из стандартных методов вычисления рекуррентных
последовательностей. Например:
a = 2
a_prev = 2
repeat (n-2) times
    tmp = a
    a = a + aprev
    aprev = tmp

(который считает за O(n)). Или матричный, который считает за O(log n). Или применить
производящие функции и получить замкнутую формулу. Или заметить, что ваша последовательность
почленно вдвое больше последовательности Фибоначчи.

Заметьте, что @Михаил М предлагает по существу ту же идею, я просто расписал по-другому.

Распишу решение с производящими функциями, может, кому-то пригодится. (Это очень
мощная техника; за строгостью и теоретическим обоснованием лучше обращаться на маткод.)
Не нарушая рекуррентного соотношения, можно положить a_0 = 0. Рассмотрим формальный ряд:
G(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + ...       (*)

тогда
x G(x) =     a_0 x + a_1 x^2 + a_2 x^3 + ...       (**)
x^2 G(x) =           a_0 x^2 + a_1 x^3 + ...       (***)

отсюда вычитая (**) и (***) из (*), имеем:
G(x) (1 - x - x^2) = a_0 + (a_1 - a_0)x = 2x

то есть
G(x) = 2x / (1 - x - x^2).

Разлагаем на элементарные дроби:
G(x) = (2/sqrt(5)) [ (sqrt(5) - 1) / (sqrt(5) - 1 - 2x) -
                     (sqrt(5) + 1) / (sqrt(5) + 1 + 2x) ]

Разложим дроби в бесконечный ряд. Вспоминая ряд для геометрической прогрессии:
a / (a - x) = 1 + x/a + x^2/a^2 + ...

тут же получаем (P = sqrt(5) - 1, Q = sqrt(5) + 1, y = 2x): 
G(x) = (2/sqrt(5)) [ ( 1 + y/P + y^2/P^2 + y^3/P^3 + ... ) -
                     ( 1 - y/Q + y^2/Q^2 - y^3/Q^3 - ... ) ] =

(положим p = (sqrt(5) - 1)/2, q = -(sqrt(5) + 1)/2, продолжаем)
     = (2/sqrt(5)) [ ( 1 + x/p + x^2/p^2 + y^3/p^3 + ... ) -
                     ( 1 + x/q + x^2/q^2 + y^3/q^3 - ... ) ].

Собирая коэффициенты слева и справа при x^i, имеем
a_i = 2/sqrt(5) (1/p^i - 1/q^i).

Заметив, что pq = -1, получим окончательно в более приятном виде
a_i = 2/sqrt(5) [ ((sqrt(5) + 1)/2)^i - ((1 - sqrt(5))/2)^i ].


Ответ 2

Надо завести массив от 1 до нужного N и постепенно его заполнять. В i-й ячейке будет
написано, сколько вариантов заполнения i клеток.
Собрать вариант длины P можно из ...Б + К..., ...К + Б..., либо ...Б/К + С + К/Б...
При этом любой из фрагментов может иметь любую длину меньше P. Причём, никогда С не
будет на концах строки/подстроки. Достаточно очевидно, что ровно половина вариантов
длины i - кончается на Б, ровно половина - на K.
Таким образом, имеем внешний цикл от 2 до N по нашему массиву и внутренний цикл по
длине левой части. Суммируем, перемножаем, записываем... Например, для правила ...Б
+ К... будет V[i] += V[j] / 2 * V[i - j] / 2
Upd: 
V[0] = 0;
V[1] = 2;  // В одной клетке - либо Б, либо К
for (int i = 2; i <= N; i++)
{
  V[i] = 0;
  for (...)
  {
    V[i] += V[j] / 2 * V[i - j] / 2