Динамика: количество программ исполнителя
Задание 23 · Билет 2 · ЕГЭ по информатике
Условие
Исполнитель Увеличитель преобразует число на экране. У исполнителя есть две команды: «Прибавить 2» и «Прибавить 10». Программа — последовательность команд.
Попробуйте программой
Необязательно, но удобно: напишите здесь свой код на Python, который найдёт ответ. Если не получится — откройте решение и вставьте готовую программу одной кнопкой.
Решите программой на Python
в браузереНапишите свой код, который найдёт ответ, и нажмите «Выполнить». Горячая клавиша запуска: Ctrl/⌘ + Enter.
Потренируйся считать программы: тренажёр соберёт нового исполнителя с командами и ограничениями, а вы посчитаете ответ программой на Python.
Решение
Решение
открыто шагов: 4 из 4Способ 1 · рекурсия с запоминанием
# f(x) — число программ, переводящих x в 71.
from functools import lru_cache
@lru_cache(None) # запоминаем уже посчитанные значения
def f(x):
if x == 71: # цель достигнута — это одна программа
return 1
if x > 71: # перескочили цель — программ нет
return 0
# команды: «прибавить 2» и «прибавить 10»
return f(x + 2) + f(x + 10)
print(f(7)) Способ 2 · таблица от 7 к 71
# ways[x] — сколько программ ведут из 7 в x.
ways = [0] * 81 # с запасом: последняя команда +10
ways[7] = 1 # из 7 в 7 ведёт одна (пустая) программа
for x in range(7, 71): # идём от меньших чисел к большим
ways[x + 2] += ways[x] # команда «прибавить 2»
ways[x + 10] += ways[x] # команда «прибавить 10»
print(ways[71]) Теория и другие билеты
Разбор с нуля, типовые ошибки, частые вопросы и все билеты задания 23 — на странице задания.