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