Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 2
B. Прибавить 5
C. Умножить на 2
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 3 результатом является число 53, и при этом траектория вычислений содержит число 40 и не содержит числа 42?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы CBA при исходном числе 7 траектория состоит из чисел 14, 19, 21.
Способ 1 (С рекурсией)
🔹 Шаг 1. Идея решения задачи
📌 Нужно посчитать количество программ, которые:
💡 Поэтому задачу удобно разбить на два этапа:
пути от 3 до 40;
пути от 40 до 53.
И затем перемножить количества программ для этих этапов.
🔹 Шаг 2. Функция подсчёта количества программ
def f(x, y):
if x == 42 or x > y:
return 0
if x == y:
return 1
return f(x + 2, y) + f(x + 5, y) + f(x * 2, y)
print(f(3, 40) * f(40, 53))
📌 Функция f(x, y) считает, сколько программ переводят число x в число y, соблюдая ограничения.
🔹 Шаг 3. Запрещённые и граничные случаи
📌 Объяснение:
🔹 Шаг 4. Условие успешного завершения
if x == y:
return 1
📌 Если текущее число равно целевому, значит программа успешно завершилась и найден один корректный путь.
🔹 Шаг 5. Переходы по командам исполнителя
return f(x + 2, y) + f(x + 5, y) + f(x * 2, y)
📌 Здесь учитываются все возможные команды исполнителя: A: x + 2, B: x + 5, C: ×2. Складываем количество программ для всех вариантов.
🔹 Финальный шаг. Учитываем обязательное число 40
print(f(3, 40) * f(40, 53))
📌 Почему умножаем:
каждую программу 3 → 40 можно продолжить любой программой 40 → 53;
число 40 гарантированно входит в траекторию;
запрещённые значения исключаются на обоих этапах.
Способ 1 (С рекурсией)
🔹 Шаг 1. Идея решения задачи
📌 Нужно посчитать количество программ, которые:
💡 Поэтому задачу удобно разбить на два этапа:
пути от 3 до 40;
пути от 40 до 53.
И затем перемножить количества программ для этих этапов.
🔹 Шаг 2. Функция подсчёта количества программ
def f(x, y):
if x == 42 or x > y:
return 0
if x == y:
return 1
return f(x + 2, y) + f(x + 5, y) + f(x * 2, y)
print(f(3, 40) * f(40, 53))
📌 Функция f(x, y) считает, сколько программ переводят число x в число y, соблюдая ограничения.
🔹 Шаг 3. Запрещённые и граничные случаи
📌 Объяснение:
🔹 Шаг 4. Условие успешного завершения
if x == y:
return 1
📌 Если текущее число равно целевому, значит программа успешно завершилась и найден один корректный путь.
🔹 Шаг 5. Переходы по командам исполнителя
return f(x + 2, y) + f(x + 5, y) + f(x * 2, y)
📌 Здесь учитываются все возможные команды исполнителя: A: x + 2, B: x + 5, C: ×2. Складываем количество программ для всех вариантов.
🔹 Финальный шаг. Учитываем обязательное число 40
print(f(3, 40) * f(40, 53))
📌 Почему умножаем:
каждую программу 3 → 40 можно продолжить любой программой 40 → 53;
число 40 гарантированно входит в траекторию;
запрещённые значения исключаются на обоих этапах.
Способ 1 (С рекурсией)
🔹 Шаг 1. Идея решения задачи
📌 Нужно посчитать количество программ, которые:
💡 Поэтому задачу удобно разбить на два этапа:
пути от 3 до 40;
пути от 40 до 53.
И затем перемножить количества программ для этих этапов.
🔹 Шаг 2. Функция подсчёта количества программ
def f(x, y):
if x == 42 or x > y:
return 0
if x == y:
return 1
return f(x + 2, y) + f(x + 5, y) + f(x * 2, y)
print(f(3, 40) * f(40, 53))
📌 Функция f(x, y) считает, сколько программ переводят число x в число y, соблюдая ограничения.
🔹 Шаг 3. Запрещённые и граничные случаи
📌 Объяснение:
🔹 Шаг 4. Условие успешного завершения
if x == y:
return 1
📌 Если текущее число равно целевому, значит программа успешно завершилась и найден один корректный путь.
🔹 Шаг 5. Переходы по командам исполнителя
return f(x + 2, y) + f(x + 5, y) + f(x * 2, y)
📌 Здесь учитываются все возможные команды исполнителя: A: x + 2, B: x + 5, C: ×2. Складываем количество программ для всех вариантов.
🔹 Финальный шаг. Учитываем обязательное число 40
print(f(3, 40) * f(40, 53))
📌 Почему умножаем:
каждую программу 3 → 40 можно продолжить любой программой 40 → 53;
число 40 гарантированно входит в траекторию;
запрещённые значения исключаются на обоих этапах.
