Task 73. Три единицы
UniLecsЗадача: вычислить количество последовательностей длины N, состоящих только из нулей и единиц, в которых не встречается три единицы подряд.
Входные данные: N - длина последовательности (1 <= N <= 50)
Вывод: Кол-во искомых последовательностей.
Пример:
N = 4
Count = 13.
Идея: воспользуемся методом динамического программирования.
Обозначим f(n) - кол-во искомых последовательностей из 0 и 1 длины n.
- Если на первом месте последовательности будет находиться 0, то начиная со второго места можно построить f(n – 1) последовательность.
- Если на первом месте стоит 1, то на втором месте возможны оба варианта. Если там стоит 0, то на следующих n – 2 свободных местах можно построить f(n – 2) последовательности. Если 1, то на третьем месте обязательно должен находиться 0 и начиная с четвертого места можно построить f(n – 3) последовательности.
В итоге получаем формулу:
f(n) = f(n - 1) + f(n - 2) + f(n - 3)
Начальные значения будут следующими:
f(1) = 2, существуют две последовательности длины 1: 0 и 1
f(2) = 4, 4 последовательности длины 2: 00, 01, 10, 11
f(3) = 7, 7 последовательностей длины 3: 000, 001, 010, 011, 100, 101, 110.
Реализация:
https://gist.github.com/unilecs/4f37443d6e331c27c5950c19157f1be7
Тест: