Задача № 180
Исполнитель преобразует число на экране. У исполнителя есть три команды:
- Прибавить 1
- Прибавить 2
- Умножить на 3
Программа для исполнителя - это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 18, и при этом траектория вычислений содержит число 9 и не содержит числа 16?
Траектория вычислений программы - это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 4 траектория будет состоять из чисел 12, 14, 15.
ЕГКР 27 апреля 2024 года (Московский пробник)
Прокрути, чтобы прочитать решение задачи
Ты уверен, что хочешь это сделать?
Удачного чтения!
Решение
Код из видео
# функция, которая считает
# сколько есть программ, преобразующих число a в число b
def f(a, b):
# если исходное число равно результату, есть один способ преобразовать
if a == b: return 1
# большее число в меньшее преобразовать нельзя
if a > b: return 0
# по условию число 16 нужно избегать
if a == 16: return 0
# команды исполнителя
return f(a+1, b) + f(a+2, b) + f(a*3, b)
# преобразуем 2 в 9, затем 9 в 18
print(f(2, 9) * f(9, 18))