Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Вычесть 3
B. Вычесть 4
C. Найти целую часть от деления на 3
Программа для исполнителя — это последовательность команд.
Сколько различных программ существует, для которых при исходном числе 50 результатом является число 6, при этом траектория вычислений не содержит число 25 и содержит 15?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы CBA при исходном числе 105 траектория будет состоять из чисел 35, 31, 28.
Способ 1 (С рекурсией)
🔹 Шаг 1. Идея решения задачи
📌 Нужно посчитать количество программ, которые:
💡 Поэтому задачу удобно разбить на два этапа:
пути от 50 до 25;
пути от 25 до 6.
И затем перемножить количества программ для этих этапов.
🔹 Шаг 2. Функция подсчёта количества программ
def f(x, y):
if x < y:
return 0
if x == 25:
return 0
if x == y:
return 1
return f(x - 3, y) + f(x - 4, y) + f(x // 3, y)
print(f(50, 15) * f(15, 6))
📌 Функция f(x, y) считает, сколько программ переводят число x в число y, соблюдая ограничения.
🔹 Шаг 3. Запрещённые и граничные случаи
📌 Объяснение:
🔹 Шаг 4. Условие успешного завершения
if x == y:
return 1
📌 Если текущее число равно целевому, значит программа успешно завершилась и найден один корректный путь.
🔹 Шаг 5. Переходы по командам исполнителя
return f(x - 3, y) + f(x - 4, y) + f(x // 3, y)
📌 Здесь учитываются все возможные команды исполнителя: A: -3, B: -4, C: ÷3 (целая часть). Складываем количество программ для всех вариантов.
🔹 Финальный шаг. Учитываем обязательное число 25
print(f(50, 15) * f(15, 6))
📌 Почему умножаем:
каждую программу 50 → 25 можно продолжить любой программой 25 → 6;
число 25 гарантированно входит в траекторию;
запрещённые значения исключаются на обоих этапах.
Способ 1 (С рекурсией)
🔹 Шаг 1. Идея решения задачи
📌 Нужно посчитать количество программ, которые:
💡 Поэтому задачу удобно разбить на два этапа:
пути от 50 до 25;
пути от 25 до 6.
И затем перемножить количества программ для этих этапов.
🔹 Шаг 2. Функция подсчёта количества программ
def f(x, y):
if x < y:
return 0
if x == 25:
return 0
if x == y:
return 1
return f(x - 3, y) + f(x - 4, y) + f(x // 3, y)
print(f(50, 15) * f(15, 6))
📌 Функция f(x, y) считает, сколько программ переводят число x в число y, соблюдая ограничения.
🔹 Шаг 3. Запрещённые и граничные случаи
📌 Объяснение:
🔹 Шаг 4. Условие успешного завершения
if x == y:
return 1
📌 Если текущее число равно целевому, значит программа успешно завершилась и найден один корректный путь.
🔹 Шаг 5. Переходы по командам исполнителя
return f(x - 3, y) + f(x - 4, y) + f(x // 3, y)
📌 Здесь учитываются все возможные команды исполнителя: A: -3, B: -4, C: ÷3 (целая часть). Складываем количество программ для всех вариантов.
🔹 Финальный шаг. Учитываем обязательное число 25
print(f(50, 15) * f(15, 6))
📌 Почему умножаем:
каждую программу 50 → 25 можно продолжить любой программой 25 → 6;
число 25 гарантированно входит в траекторию;
запрещённые значения исключаются на обоих этапах.
Способ 1 (С рекурсией)
🔹 Шаг 1. Идея решения задачи
📌 Нужно посчитать количество программ, которые:
💡 Поэтому задачу удобно разбить на два этапа:
пути от 50 до 25;
пути от 25 до 6.
И затем перемножить количества программ для этих этапов.
🔹 Шаг 2. Функция подсчёта количества программ
def f(x, y):
if x < y:
return 0
if x == 25:
return 0
if x == y:
return 1
return f(x - 3, y) + f(x - 4, y) + f(x // 3, y)
print(f(50, 15) * f(15, 6))
📌 Функция f(x, y) считает, сколько программ переводят число x в число y, соблюдая ограничения.
🔹 Шаг 3. Запрещённые и граничные случаи
📌 Объяснение:
🔹 Шаг 4. Условие успешного завершения
if x == y:
return 1
📌 Если текущее число равно целевому, значит программа успешно завершилась и найден один корректный путь.
🔹 Шаг 5. Переходы по командам исполнителя
return f(x - 3, y) + f(x - 4, y) + f(x // 3, y)
📌 Здесь учитываются все возможные команды исполнителя: A: -3, B: -4, C: ÷3 (целая часть). Складываем количество программ для всех вариантов.
🔹 Финальный шаг. Учитываем обязательное число 25
print(f(50, 15) * f(15, 6))
📌 Почему умножаем:
каждую программу 50 → 25 можно продолжить любой программой 25 → 6;
число 25 гарантированно входит в траекторию;
запрещённые значения исключаются на обоих этапах.
