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