Задача по информатике Сколько всего существует штрих-кодов из 6 штрихов, Некоторые из которых закрашенных, а некоторые нет, но при этом крайне штрихи закрашенны и нет никаких трёх идущих подряд закрашенных штрихов ?

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

Для решения этой задачи можно использовать метод динамического программирования.

Обозначим количество штрихов из 6 штрихов, оканчивающихся на закрашенный штрих, как DP1, количество штрихов, оканчивающихся на не закрашенный штрих, как DP2.

Итак, у нас есть два случая:

Если следующий (6-й) штрих закрашенный, то:

DP1 = DP2
DP2 = DP1;

Если следующий (6-й) штрих не закрашенный, то:

DP1 = DP2
DP2 = DP1 + DP2.

Теперь заполним таблицу для всех 6 штрихов, начиная с одного штриха:

Изначально:

DP1 = 1 (так как начальный штрих может быть как закрашенным, так и не закрашенным)
DP2 = 1.

После второго штриха:

DP1 = 1 (закрашенный) + 1 (не закрашенный) = 2
DP2 = 1 + 1 = 2.

После каждого следующего штриха применяем формулы выше и получаем ответ:

DP1
1 -> 1 -> 2 -> 3 -> 5 ->
DP2
1 -> 2 -> 3 -> 5 -> 8 -> 13

Итак, количество штрих-кодов из 6 штрихов, удовлетворяющих условиям задачи, равно 8 + 13 = 21.