Найдите количество 5-значных чисел, составленных из цифр 8 и 9, в которых никакие две девятки не стоят рядом. Необходимо привести развёрнутое решение.

: 13

у нас для длины n = 1 может получиться только 8 и 9 - 2 числа

для n = 2 может получиться только 89, 88, 98 - 3 числа

что мы можем сделать для n = 3?

к предыдущим числам длиной 2 добавить 8

898

888

988

а также мы можем добавить 9 тогда, если последняя цифра числа не 9. Это получается только тогда, когда мы для чисел длиной 1 добавляли 8(

88, 98).

колво чисел для 3 = колво чисел для 2 + колво чисел для 1 = 2 + 3 = 5.

Получаем рекусивное соотношение

то есть чтобы узнать сколько получится чисел длиной n, нам надо добавить к кол-ву чисел длиной n - 1 добавить 8(эти числа могут гарантированно быть т. к. 9 нету) и прибавить количество чисел длиной n - 2 (то есть мы к ним добавили 8 и их длина получилась n - 1 и к ним еще добавили девятку (их длина стала n), чтобы гарантированно не было двух девяток подряд)

и так для 4 получается = кол-во 3 + кол-во 2 = 3 + 5 = 8

для 5 получается = кол-во 4 + кол-во3 = 8 + 5 = 13

ну кароче что то вроде последовательности Фибоначчи

и так можно написать программу которая вычислит колво для любой длины