Задание №23: Динамическое программирование (Количество программ)
Основные типы и прототипы задания №23:
Количество программ преобразования чисел
Обязательные и избегаемые этапы траектории
Условие задания
(Б. Михлин) Исполнитель К22 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
Примечание. Числа Фибоначчи – это ряд чисел, в котором первое и второе число равны единице, а каждое следующее число равно сумме двух предыдущих чисел ряда: 1, 1, 2, 3, 5, 8, 13, ...
1. Прибавь 1Первая из них увеличивает число на экране на 1, вторая увеличивает число на 4. Третья команда увеличивает число на ближайшее число из ряда Фибоначчи не меньшее, чем число на экране (например, для числа 3 будет получено 6 = 3 + 3, а для числа 6 будет получено 14 = 6 + 8). Программа для исполнителя – это последовательность команд. Сколько существует программ, которые преобразуют исходное число 1 в число 17?
2. Прибавь 4
3. Прибавь число Фибоначчи
Примечание. Числа Фибоначчи – это ряд чисел, в котором первое и второе число равны единице, а каждое следующее число равно сумме двух предыдущих чисел ряда: 1, 1, 2, 3, 5, 8, 13, ...
Ответ:
362
Шаблон решения на 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))