Задача по информатике Сколько всего существует штрих-кодов из 6 штрихов, Некоторые из которых закрашенных, а некоторые нет, но при этом крайне штрихи закрашенны и нет никаких трёх идущих подряд закрашенных штрихов ?
Задача по информатике Сколько всего существует штрих-кодов из 6 штрихов, Некоторые из которых закрашенных, а некоторые нет, но при этом крайне штрихи закрашенны и нет никаких трёх идущих подряд закрашенных штрихов ?
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Для решения этой задачи можно использовать метод динамического программирования.
Обозначим количество штрихов из 6 штрихов, оканчивающихся на закрашенный штрих, как DP1, количество штрихов, оканчивающихся на не закрашенный штрих, как DP2.
Итак, у нас есть два случая:
Если следующий (6-й) штрих закрашенный, то:DP1 = DP2;
Если следующий (6-й) штрих не закрашенный, то:DP2 = DP1;
DP1 = DP2;
DP2 = DP1 + DP2.
Теперь заполним таблицу для всех 6 штрихов, начиная с одного штриха:
Изначально:DP1 = 1 (так как начальный штрих может быть как закрашенным, так и не закрашенным);
После второго штриха:DP2 = 1.
DP1 = 1 (закрашенный) + 1 (не закрашенный) = 2;
После каждого следующего штриха применяем формулы выше и получаем ответ:DP2 = 1 + 1 = 2.
DP1:
1 -> 1 -> 2 -> 3 -> 5 -> 8
DP2:
1 -> 2 -> 3 -> 5 -> 8 -> 13
Итак, количество штрих-кодов из 6 штрихов, удовлетворяющих условиям задачи, равно 8 + 13 = 21.