(Л. Шастин) Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Вычесть 1
B. Вычесть 3
C. Найти целую часть от деления на 2
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 29 результатом является число 5, при этом траектория вычислений не содержит числа 17 и содержит 13?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы CBA при исходном числе 13 траектория состоит из чисел 6, 3, 2.
Способ 1 (С рекурсией)
🔹 Шаг 1. Идея решения задачи
📌 Нужно посчитать программы, которые переводят 29 → 5 командами −1, −3 и //2. Траектория должна содержать 13 и не содержать 17.
📌 Все команды уменьшают число, поэтому путь через 13 распадается на две части: 29 → 13 и 13 → 5.
🔹 Шаг 2. Функция и запретные случаи
def f(x, y):
if x < y or x == 17:
return 0
if x == y:
return 1
return f(x - 1, y) + f(x - 3, y) + f(x // 2, y)
print(f(29, 13) * f(13, 5))
📌 Функция f(x, y) считает пути из x в y. Если x < y — цель уже пропущена; если x == 17 — запретное число. В обоих случаях возвращаем 0.
🔹 Шаг 3. Успешное завершение
if x == y:
return 1
📌 Если текущее число равно целевому — найден один корректный путь.
🔹 Шаг 4. Команды исполнителя
return f(x - 1, y) + f(x - 3, y) + f(x // 2, y)
📌 Складываем варианты по командам A (−1), B (−3) и C (//2).
🔹 Финальный шаг. Через обязательное число
print(f(29, 13) * f(13, 5))
📌 Любой путь 29 → 13 можно продолжить любым путём 13 → 5, поэтому количества перемножаем.
📌 Число 17 может встретиться только в первой части (во второй все числа ≤ 13), а там оно уже отсечено.
📌 Ответ: 1836.
Способ 1 (С рекурсией)
🔹 Шаг 1. Идея решения задачи
📌 Нужно посчитать программы, которые переводят 29 → 5 командами −1, −3 и //2. Траектория должна содержать 13 и не содержать 17.
📌 Все команды уменьшают число, поэтому путь через 13 распадается на две части: 29 → 13 и 13 → 5.
🔹 Шаг 2. Функция и запретные случаи
def f(x, y):
if x < y or x == 17:
return 0
if x == y:
return 1
return f(x - 1, y) + f(x - 3, y) + f(x // 2, y)
print(f(29, 13) * f(13, 5))
📌 Функция f(x, y) считает пути из x в y. Если x < y — цель уже пропущена; если x == 17 — запретное число. В обоих случаях возвращаем 0.
🔹 Шаг 3. Успешное завершение
if x == y:
return 1
📌 Если текущее число равно целевому — найден один корректный путь.
🔹 Шаг 4. Команды исполнителя
return f(x - 1, y) + f(x - 3, y) + f(x // 2, y)
📌 Складываем варианты по командам A (−1), B (−3) и C (//2).
🔹 Финальный шаг. Через обязательное число
print(f(29, 13) * f(13, 5))
📌 Любой путь 29 → 13 можно продолжить любым путём 13 → 5, поэтому количества перемножаем.
📌 Число 17 может встретиться только в первой части (во второй все числа ≤ 13), а там оно уже отсечено.
📌 Ответ: 1836.
Способ 1 (С рекурсией)
🔹 Шаг 1. Идея решения задачи
📌 Нужно посчитать программы, которые переводят 29 → 5 командами −1, −3 и //2. Траектория должна содержать 13 и не содержать 17.
📌 Все команды уменьшают число, поэтому путь через 13 распадается на две части: 29 → 13 и 13 → 5.
🔹 Шаг 2. Функция и запретные случаи
def f(x, y):
if x < y or x == 17:
return 0
if x == y:
return 1
return f(x - 1, y) + f(x - 3, y) + f(x // 2, y)
print(f(29, 13) * f(13, 5))
📌 Функция f(x, y) считает пути из x в y. Если x < y — цель уже пропущена; если x == 17 — запретное число. В обоих случаях возвращаем 0.
🔹 Шаг 3. Успешное завершение
if x == y:
return 1
📌 Если текущее число равно целевому — найден один корректный путь.
🔹 Шаг 4. Команды исполнителя
return f(x - 1, y) + f(x - 3, y) + f(x // 2, y)
📌 Складываем варианты по командам A (−1), B (−3) и C (//2).
🔹 Финальный шаг. Через обязательное число
print(f(29, 13) * f(13, 5))
📌 Любой путь 29 → 13 можно продолжить любым путём 13 → 5, поэтому количества перемножаем.
📌 Число 17 может встретиться только в первой части (во второй все числа ≤ 13), а там оно уже отсечено.
📌 Ответ: 1836.
