Исполнитель Б22 преобразует целое число, записанное на экране.
У исполнителя три команды, каждой команде присвоен номер:
1. Прибавь 1
2. Прибавь 2
3. Прибавь предыдущее
Первая команда увеличивает число на экране на 1, вторая увеличивает это число на 2, третья прибавляет к числу на экране число, меньшее на 1 (к числу 3 прибавляется 2, к числу 11 прибавляется 10 и т. д.). Программа для исполнителя Б22 – это последовательность команд.
Сколько существует программ, которые число 3 преобразуют в число 10?
Пусть R(x) — количество программ, которыми можно из 3 получить x.
Заметим, что чётное число нельзя получить с использованием команды 3, поскольку в её процессе складывается чётное и нечётное число. Также заметим, что для того, чтобы получить x с помощью команды 3, нужно применять её к числу 
Вычислим последовательно значение R:
R(0) = 0
R(1) = 0
R(2) = 0
R(3) = 1
R(4) = R(3) + R(2) = 1 + 0 = 1
R(5) = R(4) + R(3) + R(3) = 1 + 1 + 1 = 3
R(6) = R(5) + R(4) = 3 + 1 = 4
R(7) = R(6) + R(5) + R(4) = 4 + 3 + 1 = 8
R(8) = R(7) + R(6) = 8 + 4 = 12
R(9) = R(8) + R(7) + R(5) = 12 + 8 + 3 = 23
R(10) = R(9) + R(8) = 23 + 12 = 35
Ответ: 35.
Приведём другое решение на языке Python.
def f(x, y):
if x > y:
return 0
if x == y:
return 1
else:
return f(x + 1, y) + f(x + 2, y) + f(2 * x - 1, y)
print(f(3, 10))