Исполнитель Июнь15 преобразует число на экране..

Задание:

Исполнитель Июнь15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Прибавить 3
Программа для исполнителя Июнь15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 4 результатом является число 15 и при этом траектория вычислений содержит число 8?

Решение:

Составим формулу от обратного:

F(n) = F(n-1) + F(n-2) + F(n-3)

F(4) = 1 - Изначально одна программа есть.
F(5) = F(4) + F(3) + F(2) = 1 + 0 + 0 = 1
F(6) = F(5) + F(4) + F(3) = 1 + 1 + 0 = 2
F(7) = F(6) + F(5) + F(4) = 2 + 1 + 1 = 4
F(8) = F(7) + F(6) + F(5) = 4 + 2 + 1 = 7

Далее аккуратно работаем только с числами, проходящими через 8.

F(9) = F(8) + F(7) + F(6) = 7, F(7) и F(6) не подходят по траектории.
F(10) = F(9) + F(8) + F(7) = 7 + 7 = 14, F(7) не подходит по траектории.
F(11) = F(10) + F(9) + F(8) = 14 + 7 + 7 = 28
F(12) = F(11) + F(10) + F(9)= 28 + 14 + 7 = 49
F(13) = F(12) + F(11) + F(10) = 49 + 28 + 14 = 91
F(14) = F(13) + F(12) + F(11) = 91 + 49 + 28 = 168
F(15 = F(14) + F(13) + F(12) = 168 + 91 + 49 = 259 + 49 = 308

Ответ: 308