Количество различных чисел из 'n' чисел; числа только 5 и 9, но максимум 2 цифры подряд напнример(n=3; можно сделать такие числа :559; 599; 995; 959; 955; 595. Но нельзя 555 или 999, но можно 559955 или 995599 и т.д. например: вводится n(3) вывести(6)

Предыдущий
вопрос Следующий
вопрос

Для решения этой задачи можно воспользоваться методом динамического программирования. Создадим таблицу dp размера n на 2, где dp[i][0] будет хранить количество чисел из i цифр, заканчивающихся на 5, и dp[i][1] будет хранить количество чисел из i цифр, заканчивающихся на 9.

Инициализируем значения в таблице dp следующим образом:
dp[1][0] = dp[1][1] = 1

Далее, для каждой последующей цифры i от 2 до n, мы можем рассмотреть два случая:

Увеличение числа, заканчивающегося на 5, добавлением цифры 9 в конец. То есть dp[i][0] = dp[i-1][1]Увеличение числа, заканчивающегося на 9, добавлением цифры 5 в конец. То есть dp[i][1] = dp[i-1][0]

Итоговый ответ будет суммой значений dp[n][0] и dp[n][1].

Пример реализации на языке Python:

def countNumbersWithNoConsecutive(n):
dp = [[0, 0] for _ in range(n+1)]
dp[1][0] = dp[1][1] = 1
for i in range(2, n+1):
dp[i][0] = dp[i-1][1]
dp[i][1] = dp[i-1][0]
return sum(dp[n])
n = 3
print(countNumbersWithNoConsecutive(n)) # Output: 6

Таким образом, при n=3 количество различных чисел будет равно 6.