рекурсия << На главную или назад  

помогите с задачей, правильно ли я ее решил?

Определить число n-последовательностей из (0, 1, 2), в которых отсутствует две подряд стоящих 1.

Решение: после постановки первого элемента, вариантов поставить второй и третий элемент – 2Q(n-2), если выбраны два первых элемента, то вариантов поставить третий – Q(n-1). Общее число n-последовательностей:

Q(n)=2Q(n-2)+Q(n-1)

База рекурсии:

Q(1)=3