Разбор номера 21420 #kege по информатике #ЕГЭ23

Автор: Досрочная волна 2024
Уровень: Базовый

Условие задачи:

У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Прибавить 2
C. Умножить на 2

Сколько существует программ, которые преобразуют число 7 в число 51, и при этом траектория вычислений содержит числа 13 и 15, но не содержит числа 35?

Теоретическая справка:

Довольно забавная программа, так как у некоторых ребят на стареньких компьютерах она считается долго. И можно воспользоваться кэшированием из 16 номера для ускорения вычислений!

Код решения:

Ответ: 174034068

Комментарии к коду:

1. from functools import *
   Импортируется модуль functools, который содержит полезные инструменты для работы с функциями (в частности - декоратор lru_cache).
2. @lru_cache(None)
   Декоратор, который запоминает результаты всех вызовов функции F.
   Благодаря этому при повторных вызовах с теми же аргументами программа работает быстрее, не пересчитывая одно и то же.
3. def F(a, b):
   Определяется рекурсивная функция F, принимающая два параметра — a (начальное число) и b (конечное число).
4. if a >= b or a == 35:
   Проверяется условие остановки рекурсии:
   - если a стало больше или равно b,
   - либо если a достигло числа 35,
   то дальнейшие шаги не выполняются.
5. return a == b
   Возвращает True (1), если a равно b, и False (0) — в остальных случаях.
   Таким образом, функция подсчитывает количество способов дойти до b.
6. return F(a + 1, b) + F(a + 2, b) + F(a * 2, b)
   Если условие не выполнено, функция рекурсивно вызывает саму себя, рассматривая три возможных шага из числа a:
   - добавить 1,
   - добавить 2,
   - умножить на 2.
   Сумма этих трёх вызовов возвращает количество всех возможных путей от a до b.
7. print(F(7, 13) * F(13, 15) * F(15, 51))
   Вычисляется произведение количества путей:
   - от 7 до 13,
   - от 13 до 15,
   - от 15 до 51.
   Затем результат выводится на экран.
   

Больше разборов на эту и другие задачи вы можете найти в нашем Телеграм канале: Информатика ЕГЭ | itpy 👨‍💻

Подписывайтесь на наш канал по теории Python: Азим вкатывается в IT | itpy 💻  Вы найдете тут много полезного!