Главная › Информатика › №13 · Подсчёт программ

ЕГЭ информатика, задание 13: №13 · Подсчёт программ

Исполнитель преобразует число на экране. У исполнителя есть команды:

1. прибавь 1

2. прибавь 2

3. умножь на 2

Программа для исполнителя — последовательность команд. Сколько существует программ, для которых при исходном числе 4 результатом является число 25 и при этом траектория вычислений содержит число 15?

Показать ответ и разбор
Ответ: 16198

Считаем динамикой: число программ до x = сумма чисел программ до чисел, из которых в x можно попасть одной командой. Через 15: (программы 4→15) × (15→25). Ответ: 16198.

Лайфхак. рекурсивная функция f(x, y) с @lru_cache на Python решает за минуту.
Потренируйся в боте. Такие задания с разбором, статистика по темам и работа над ошибками: бесплатно в Telegram.
Решить это задание в боте @infkostbot

Ещё задания по теме