ЕГЭ · ЗАДАНИЕ 23
Исполнители и количество программ · практика 9
Исполнитель умеет прибавить 1 или прибавить 2. Сколько различных программ переводят число 1 в число 15 и обязательно проходят через 6?
Учебная модель Академии С для проверки приёма. Не выдаётся за задание реального экзамена.
Источник задания
Сначала попробуй решить самостоятельно, затем открой разбор. Для автоматической проверки ответа включи JavaScript.
Показать решение по шагам
Разбор решения
Ответ: 440
Решение по шагам
- Любая допустимая программа состоит из двух частей: 1 → 6 и 6 → 15. Убывающих команд нет, поэтому 6 нельзя посетить повторно.
- Для участка длиной d обозначим число способов W(d). W(0)=1, W(1)=1, W(d)=W(d−1)+W(d−2): последний ход был +1 либо +2.
- Первый участок: W(5)=8. Второй: W(9)=55. По правилу произведения: 8 × 55 = 440.
Проверка на Python
def ways(start, finish):
dp = [0] * (finish + 1)
dp[start] = 1
for x in range(start + 1, finish + 1):
dp[x] = dp[x - 1]
if x - 2 >= start:
dp[x] += dp[x - 2]
return dp[finish]
print(ways(1, 6) * ways(6, 15))