Задание №23: Динамическое программирование (Количество программ)
Основные типы и прототипы задания №23:
Количество программ преобразования чисел
Обязательные и избегаемые этапы траектории
Условие задания
(И. Карпачев) Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены коды:
A. Вычти 2Первая команда уменьшает число на экране на 2, вторая команда уменьшает число на экране на 3, третья команда заменяет число на экране на целую часть от деления числа на 2. Сколько существует программ, для которых при исходном числе 29 результатом будет являться число 2, при этом программа соответствует маске «?B*C??» (символ «?» означает ровно один произвольный символ; символ «*» означает любую последовательность символов произвольной длины; в том числе «*» может задавать и пустую последовательность)?
B. Вычти 3
С. Найди целую часть от деления на 2
Ответ:
234
Шаблон решения на Python
# === Задание 23: Динамическое программирование (Количество программ) ===
def f(cur, target, avoid=None):
if cur > target or (avoid and cur == avoid): return 0
if cur == target: return 1
return f(cur + 1, target, avoid) + f(cur * 2, target, avoid)
# Траектория из A в B (через обязательную точку):
print("Количество программ:", f(2, 12) * f(12, 30))