Исполнитель преобразует число на экране с помощью двух команд.
- A. Прибавь 1. Увеличивает число на 1.
- B. Допиши сумму. Дописывает в начало сумму цифр числа. Команду можно выполнить, только если сумма цифр меньше 10 и чётна.
Программа для исполнителя состоит из последовательности команд. Траектория вычислений состоит из результатов выполнения всех команд программы. Например, для программы AAB при исходном числе 2 траектория состоит из чисел 3, 4, 44.
Сколько существует программ, которые преобразуют число 12 в число 999?
Решение:
def count_programs(current, target):
if current == target:
return 1
if current > target:
return 0
# Программы, которые начинаются с команды A
count = count_programs(current + 1, target)
# Программы, которые начинаются с команды B
digit_sum = sum(int(digit) for digit in str(current))
if digit_sum < 10 and digit_sum % 2 == 0:
count += count_programs(int(str(digit_sum) + str(current)), target)
return count
print(count_programs(12, 999)) # 20Ответ: 20
Ответ:
20