🔥 «Как решить задачу на динамическое программирование в ЕГЭ и не сойти с ума: разбор на примере Python»

Вступление:
📌 «Динамическое программирование» звучит сложно? На самом деле это просто способ разбить большую проблему на маленькие шаги. Сегодня разберем задачу, которая встречается в ЕГЭ каждый год, и докажем, что алгоритмы — это логично и даже красиво!

«Исполнитель может умножать число на 2, добавлять 1 или 3. Сколько существует программ, преобразующих число 1 в число 15, если в промежуточных действиях не должно быть числа 10?»

Шаг 1: Понимание условия

🔍 Что нужно найти?
Количество уникальных последовательностей команд, ведущих от 1 к 15, минуя 10.

💡 Почему это типично для ЕГЭ?
Задачи на подсчет путей с ограничениями проверяют умение строить рекуррентные соотношения — ключевой навык для программиста.

Шаг 2: Решение „в лоб“ (и почему это плохая идея)

Можно попытаться перебрать все варианты вручную, но:
❌ Это займет часы.
❌ Легко допустить ошибку.
✅ Решение через динамическое программирование сократит время до 5 минут!

Шаг 3: Алгоритм на Python

def count_programs():
dp = [0] * 16 # Массив для хранения количества путей до каждого числа
dp[1] = 1 # Начальное условие: из 1 в 1 — 1 способ

for n in range(1, 15):
if n == 10: # Пропускаем запрещенное число
continue
next_numbers = [n*2, n+1, n+3]
for next_n in next_numbers:
if next_n <= 15:
dp[next_n] += dp[n]

return dp[15]

print("Ответ:", count_programs())

Что делает код?

1. Создает массив dp, где dp[i] — число способов получить число i.
2. Для каждого числа от 1 до 14 (кроме 10) считает, сколько путей ведет к числам, которые можно получить командами ×2, +1, +3.

Результат: 98 способов.

Шаг 4: Как это пригодится на экзамене?

✅ Динамическое программирование встречается в 3-5 задачах ЕГЭ.
✅ Этот подход учит декомпозиции — разбивать сложное на простые части.
✅ Код на Python можно адаптировать под любую похожую задачу.

Советы от SvetIT:

1. Тренируйтесь на реальных задачах: Берите варианты прошлых лет.
2. Пишите код сразу: Не надейтесь на ручной подсчет — это риск.
3. Учите теорию: Понимание рекуррентных формул спасет даже в нестандартных задачах.

Проверь себя!

✏️ Модифицируйте код, чтобы найти количество путей от 2 до 20 с запретом числа 5. Ответ напишите в комментариях!

Почему мы?
В SvetIT не зубрят шаблоны — учат думать. Наши ученики:
→ Решают задачи на 20% быстрее благодаря алгоритмическому мышлению.
→ Поступают в топовые IT-вузы (МФТИ, ВШЭ, ТулГУ).
→ Пишут код, который понимают, а не копируют.

Хотите так же?
👉 Подписывайтесь на канал, чтобы не пропустить разборы задач и секреты подготовки.
👉 Первым 10 подписчикам — чек-лист «5 ошибок на ЕГЭ по информатике» в личные сообщения!

#ЕГЭ_информатика #Python_программирование #ДинамическоеПрограммирование #SvetIT

P.S. В следующей статье разберем, как оптимизировать код для задач с большими числами. Оставайтесь с нами! 💻🚀