(А. Михайлов) Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавь 1
B. Умножь на 2
C. Умножь на 3
Команда A увеличивает число на экране на 1; команда B увеличивает число на экране в два раза; команда C увеличивает число в 3 раза.
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 30 и при этом траектория вычислений содержит число 10 или число 20, но не оба числа одновременно?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Способ 1 (С рекурсией)
🔹 Шаг 1. Идея решения задачи
📌 Нужно посчитать программы, которые переводят 2 → 30 командами +1, ×2 и ×3, и при этом в траектории есть 10 или 20, но не оба числа.
📌 Разбиваем на два непересекающихся случая: пути через 10 без 20 и пути через 20 без 10.
🔹 Шаг 2. Функция с запретным числом
def f(x, y, ban=None):
if ban is not None and x == ban:
return 0
if x > y:
return 0
if x == y:
return 1
return f(x + 1, y, ban) + f(x * 2, y, ban) + f(x * 3, y, ban)
print(f(2, 10) * f(10, 30, ban=20) + f(2, 20, ban=10) * f(20, 30))
📌 Функция f(x, y, ban=None) считает пути из x в y. Параметр ban — число, которое нельзя встречать. Если x == ban или x > y — возвращаем 0.
🔹 Шаг 3. Успешное завершение
if x == y:
return 1
📌 Если текущее число равно целевому — найден один корректный путь.
🔹 Шаг 4. Команды исполнителя
return f(x + 1, y, ban) + f(x * 2, y, ban) + f(x * 3, y, ban)
📌 Складываем варианты по командам A (+1), B (×2) и C (×3).
🔹 Финальный шаг. Два случая «или, но не оба»
print(f(2, 10) * f(10, 30, ban=20) + f(2, 20, ban=10) * f(20, 30))
📌 Через 10 без 20: f(2, 10) * f(10, 30, ban=20).
📌 Через 20 без 10: f(2, 20, ban=10) * f(20, 30).
📌 Складываем оба случая — это и есть ответ 83.
Способ 1 (С рекурсией)
🔹 Шаг 1. Идея решения задачи
📌 Нужно посчитать программы, которые переводят 2 → 30 командами +1, ×2 и ×3, и при этом в траектории есть 10 или 20, но не оба числа.
📌 Разбиваем на два непересекающихся случая: пути через 10 без 20 и пути через 20 без 10.
🔹 Шаг 2. Функция с запретным числом
def f(x, y, ban=None):
if ban is not None and x == ban:
return 0
if x > y:
return 0
if x == y:
return 1
return f(x + 1, y, ban) + f(x * 2, y, ban) + f(x * 3, y, ban)
print(f(2, 10) * f(10, 30, ban=20) + f(2, 20, ban=10) * f(20, 30))
📌 Функция f(x, y, ban=None) считает пути из x в y. Параметр ban — число, которое нельзя встречать. Если x == ban или x > y — возвращаем 0.
🔹 Шаг 3. Успешное завершение
if x == y:
return 1
📌 Если текущее число равно целевому — найден один корректный путь.
🔹 Шаг 4. Команды исполнителя
return f(x + 1, y, ban) + f(x * 2, y, ban) + f(x * 3, y, ban)
📌 Складываем варианты по командам A (+1), B (×2) и C (×3).
🔹 Финальный шаг. Два случая «или, но не оба»
print(f(2, 10) * f(10, 30, ban=20) + f(2, 20, ban=10) * f(20, 30))
📌 Через 10 без 20: f(2, 10) * f(10, 30, ban=20).
📌 Через 20 без 10: f(2, 20, ban=10) * f(20, 30).
📌 Складываем оба случая — это и есть ответ 83.
Способ 1 (С рекурсией)
🔹 Шаг 1. Идея решения задачи
📌 Нужно посчитать программы, которые переводят 2 → 30 командами +1, ×2 и ×3, и при этом в траектории есть 10 или 20, но не оба числа.
📌 Разбиваем на два непересекающихся случая: пути через 10 без 20 и пути через 20 без 10.
🔹 Шаг 2. Функция с запретным числом
def f(x, y, ban=None):
if ban is not None and x == ban:
return 0
if x > y:
return 0
if x == y:
return 1
return f(x + 1, y, ban) + f(x * 2, y, ban) + f(x * 3, y, ban)
print(f(2, 10) * f(10, 30, ban=20) + f(2, 20, ban=10) * f(20, 30))
📌 Функция f(x, y, ban=None) считает пути из x в y. Параметр ban — число, которое нельзя встречать. Если x == ban или x > y — возвращаем 0.
🔹 Шаг 3. Успешное завершение
if x == y:
return 1
📌 Если текущее число равно целевому — найден один корректный путь.
🔹 Шаг 4. Команды исполнителя
return f(x + 1, y, ban) + f(x * 2, y, ban) + f(x * 3, y, ban)
📌 Складываем варианты по командам A (+1), B (×2) и C (×3).
🔹 Финальный шаг. Два случая «или, но не оба»
print(f(2, 10) * f(10, 30, ban=20) + f(2, 20, ban=10) * f(20, 30))
📌 Через 10 без 20: f(2, 10) * f(10, 30, ban=20).
📌 Через 20 без 10: f(2, 20, ban=10) * f(20, 30).
📌 Складываем оба случая — это и есть ответ 83.
