Исполнитель УВЕЛИЧИТЕЛЬ9000 преобразует целое число, записанное на экране.
У исполнителя три команды. Каждой команде присвоен номер:
1. Прибавить 1,
2. Прибавить 2,
3. Умножить на 4
Первая из них увеличивает число на экране на 1, второе - увеличивает его на 2, третья - увеличивает его в 4 раза.
Программа для УВЕЛИЧИТЕЛЯ9000 - это последовательность команд.
Сколько есть программ, которые преобразуют число 2 в число 17?
Количество программ, которые преобразуют число 2 в число n, обозначим R(n). Число 2 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 2. Значит, R(2) = 1. Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на 4, то оно может быть получено командами 1 и 2. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего возможного числа: \(R(n) = R(n-1) + R(n-2)\).
Если число делится на 4, то вариантов последней команды три: прибавить 1, прибавить 2 и умножить на 4, тогда \(R(n) = R(n-1) + R(n-2) + R(n:4)\). Заполним таблицу по данной формуле:
\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
\text{2}& 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 \\
\hline
\text{1}& 1 & 2 & 3 & 5 & 8 & 14 & 22 & 36 & 58 & 95 & 153 & 248 & 401 & 651 & 1052 \\
\hline
\end{array}\] Отсюда получаем искомое количество программ — 1052.
Ответ: 1052