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

Автор: Статград
Уровень: Сложный

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

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

Сколько существует программ, которые преобразуют исходное число 1 в число 17 и при этом траектория вычислений содержит не более 4 четных чисел?

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

На картинке я прикрепил два своих решения одной и той же задачи, но позже заметил, что, несмотря на то что оба варианта дают правильный ответ, один из них неверный! А именно первый вариант является неправильным, так как в нем рассматриваются все цифры, а не числа. Правильным подходом будет разбить все числа с помощью c+' '+str(a), чтобы таким образом рассматривать лишь четные числа. Будьте внимательны!

Код решения:

Ответ: 8

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

1. def F(a, b, c):
   Объявление функции F с тремя параметрами: a, b и c.
2. if a >= b:
   Проверка, если значение a больше или равно b.
3. M = [int(x) for x in c.split() if int(x) % 2 == 0]
   Создание списка M, который содержит четные числа из строки c, преобразуя их в целые значения.
4. return a == b and len(M) <= 4
   Возвращение результата: True, если a равно b и количество четных чисел в M не превышает 4.
5. return F(a+1, b, c+' '+str(a)) + F(a*2, b, c+' '+str(a))
   Рекурсивный вызов функции F для двух случаев: увеличивая a на 1 и удваивая a, добавляя текущий a в строку c.
6. print(F(1, 17, ''))
   Вызов функции F с параметрами 1, 17 и пустой строкой, вывод результата на экран.
   

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

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