При переработке радиоактивных материалов образуются отходы трех видов — особо опасные (тип A), неопасные (тип B) и совсем не опасные (тип C). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры последние укладываются

Добавлена: 14.04.2026
Обновлена: 14.04.2026
Предмет: Высшая математика
Автор: Кэмп

#Дискретная математика
#Теория графов

Условие:

При переработке радиоактивных материалов образуются отходы трех видов — особо опасные (тип A), неопасные (тип B) и совсем не опасные (тип C). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более одного контейнера типа A. Стопка считается безопасной, если она не является взрывоопасной. Для заданного количества контейнеров N определить число безопасных стопок.

Решение:

Чтобы решить задачу о количестве безопасных стопок контейнеров с отходами, мы можем использовать динамическое программирование (DP). Давайте разберем задачу по шагам.

Шаг 1: Определим состояние

Мы будем использовать массив dp, где dp[n] будет хранить количество безопасных стопок длиной n.

Шаг 2: Базовые случаи

Для N = 1 (один контейнер) возможные варианты: A, B, C. Все они безопасны. Таким образом, dp[1] = 3.

Шаг 3: Рекуррентное соотношение

Для длины n мы можем добавить контейнеры к уже безопасным стопкам длины n-1:

Если добавляем контейнер типа B или C, то...

Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит

Попробуй решить по шагам

Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение

Какое рекуррентное соотношение правильно описывает количество безопасных стопок контейнеров $dp[n]$ для длины $n$, если стопка считается взрывоопасной при наличии более одного контейнера типа A подряд?

$dp[n] = dp[n-1] + dp[n-2]$