(А. Михайлов) Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Прибавить 3
C. Умножить на 2
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 10 результатом является число 68, при этом траектория вычислений (не считая конечного числа) не содержит чисел, больших 64?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы CCA при исходном числе 4 траектория состоит из чисел 8, 16, 17.
Способ 1 (С рекурсией)
🔹 Шаг 1. Идея решения задачи
📌 Нужно посчитать количество программ, которые:
🔹 Шаг 2. Функция подсчёта количества программ
def f(x, y):
if x > y: return 0
if x == y:
return 1
if x > 64: return 0
return f(x + 1, y) + f(x + 3, y) + f(x * 2, y)
print(f(10, 68))
📌 Функция f(x, y) считает, сколько программ переводят число x в число y, соблюдая ограничения.
🔹 Шаг 3. Запрещённые и граничные случаи
if x > y: return 0
if x > 64: return 0
📌 Объяснение:
если текущее число превысило целевое, дальнейший путь невозможен.
отсекаем пути, которые нарушают ограничения задачи.
🔹 Шаг 4. Условие успешного завершения
if x == y:
return 1
📌 Если текущее число равно целевому, значит программа успешно завершилась и найден один корректный путь.
🔹 Шаг 5. Переходы по командам исполнителя
return f(x + 1, y) + f(x + 3, y) + f(x * 2, y)
📌 Здесь учитываются все возможные команды исполнителя: A: +1, B: +3, C: ×2. Складываем количество программ для всех вариантов.
🔹 Финальный шаг. Вывод ответа
print(f(10, 68))
📌 Выводим количество программ, переводящих 10 в 68: print(f(10, 68)).
Способ 1 (С рекурсией)
🔹 Шаг 1. Идея решения задачи
📌 Нужно посчитать количество программ, которые:
🔹 Шаг 2. Функция подсчёта количества программ
def f(x, y):
if x > y: return 0
if x == y:
return 1
if x > 64: return 0
return f(x + 1, y) + f(x + 3, y) + f(x * 2, y)
print(f(10, 68))
📌 Функция f(x, y) считает, сколько программ переводят число x в число y, соблюдая ограничения.
🔹 Шаг 3. Запрещённые и граничные случаи
if x > y: return 0
if x > 64: return 0
📌 Объяснение:
если текущее число превысило целевое, дальнейший путь невозможен.
отсекаем пути, которые нарушают ограничения задачи.
🔹 Шаг 4. Условие успешного завершения
if x == y:
return 1
📌 Если текущее число равно целевому, значит программа успешно завершилась и найден один корректный путь.
🔹 Шаг 5. Переходы по командам исполнителя
return f(x + 1, y) + f(x + 3, y) + f(x * 2, y)
📌 Здесь учитываются все возможные команды исполнителя: A: +1, B: +3, C: ×2. Складываем количество программ для всех вариантов.
🔹 Финальный шаг. Вывод ответа
print(f(10, 68))
📌 Выводим количество программ, переводящих 10 в 68: print(f(10, 68)).
Способ 1 (С рекурсией)
🔹 Шаг 1. Идея решения задачи
📌 Нужно посчитать количество программ, которые:
🔹 Шаг 2. Функция подсчёта количества программ
def f(x, y):
if x > y: return 0
if x == y:
return 1
if x > 64: return 0
return f(x + 1, y) + f(x + 3, y) + f(x * 2, y)
print(f(10, 68))
📌 Функция f(x, y) считает, сколько программ переводят число x в число y, соблюдая ограничения.
🔹 Шаг 3. Запрещённые и граничные случаи
if x > y: return 0
if x > 64: return 0
📌 Объяснение:
если текущее число превысило целевое, дальнейший путь невозможен.
отсекаем пути, которые нарушают ограничения задачи.
🔹 Шаг 4. Условие успешного завершения
if x == y:
return 1
📌 Если текущее число равно целевому, значит программа успешно завершилась и найден один корректный путь.
🔹 Шаг 5. Переходы по командам исполнителя
return f(x + 1, y) + f(x + 3, y) + f(x * 2, y)
📌 Здесь учитываются все возможные команды исполнителя: A: +1, B: +3, C: ×2. Складываем количество программ для всех вариантов.
🔹 Финальный шаг. Вывод ответа
print(f(10, 68))
📌 Выводим количество программ, переводящих 10 в 68: print(f(10, 68)).
