Исполнитель Б22 преобразует целое число, записанное на экране. У исполнителя три команды, каждой команде присвоен номер:
1) Прибавь 1
2) Прибавь 2
3) Прибавь следующее
Первая команда увеличивает число на экране на 1, вторая увеличивает это число на 2, третья прибавляет к числу на экране число, большее на 1 (к числу 3 прибавляется 4, к числу 9 прибавляется 10 и т. д.). Программа для исполнителя Б22 — это последовательность команд. Сколько существует программ, которые число 2 преобразуют в число 10?
Обозначим число программ, преобразующих число 2 в число N как КN. Тогда число N может быть получено либо прибавление единице к N − 1, либо двойки к N − 2, либо из некоторого числа X увеличением на X + 1 (следующее число), так что N = X + X + 1, откуда X = (N − 1) / 2; так могут быть получены только нечетные числа.
Тогда для чётных чисел KN = KN − 1 + KN − 2, а для нечётных — KN = KN − 1 + KN − 2 + K(N − 1)/2. Заполним таблицу для значений от 2 до 9:
| N | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|
| KN | 1 | 2 | 4 | 6 | 11 | 17 | 30 | 47 |
Ответ: 47.
Приведём другое решение на языке Python.
def f(x, y):
if x == y:
return 1
if x > y:
return 0
else:
return f(x + 1, y) + f(x + 2, y) + f(2 * x + 1, y)
print(f(2, 10))