Задача #2125
Количество программ
(Т. Закиров) Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить d
2. Умножить на 2
Первая команда увеличивает число на экране на d(d - натуральное число), вторая умножает его на 2. Программа для исполнителя – это последовательность команд.
Посчитали количество различных программ, для которых при исходном числе 1 результатом является число 100, и при этом траектория вычислений содержит число 10 и не содержит число 30.
Укажите общее количество таких программ при всех возможных d.
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 и d = 1 траектория будет состоять из чисел 8, 16, 17.
Решение
Ответ
def f(a, b, d): if a > b or a == 30: return 0 if a == b: return 1 if a < b: return f(a + d, b, d) + f(a * 2, b, d)print(sum(f(1, 10, i) * f(10, 100, i) for i in range(1, 10)))