У исполнителя Калькулятор три команды..

Задание:

У исполнителя Калькулятор три команды, которым присвоены номера:
1. прибавь 1
2. прибавь 3
3. прибавь 6
Программа для исполнителя – это последовательность команд. Сколько существует программ, которые число 21 преобразуют в число 30?

Ответ: 25

Решение:

* Составим формулу: F(n) = F(n-1) + F(n-3) + F(n - 6)
* Из 21 получить 30:
  21 = 1 - так как изначально одна программа есть.
  22 = F(22-1) + F(22-3) + F(22-6) = F(21) + F(19) + F(16) = 1 + 0 + 0 = 1
  23 = F(22) + F(20) + F(17) = 1 + 0 + 0 = 1
  24 = F(23) + F(21) + F(18) = 1 + 1 + 0 = 2
  25 = F(24) + F(22) + F(19) = 2 + 1 + 0 = 3
  26 = F(25) + F(23) + F(20) = 3 + 1 + 0 = 4
  27 = F(26) + F(24) + F(21) = 4 + 2 + 1 = 7
  28 = F(27) + F(25) + F(22) = 7 + 3 + 1 = 11
  29 = F(28) + F(26) + F(23) = 11 + 4 + 1 = 16
  30 = F(29) + F(27) + F(24) = 16 + 7 +  2 = 25