Добрый вечер! Предлагаю Вам, пожалуй, самый простой способ решения задач B13 в ЕГЭ.

Рассмотрим две задачи.

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

1. прибавить 1
2. умножить на 2

Сколько есть программ, которые число 1 преобразуют в число 16?


Последнее значение - это число 16. Запишем, что

F(16) = 1, т.е. из числа 16 можно сделать 1 программу.
F(15) = F(15+1) (предыдущая) + F(15*2) = F(16)+F(30) = 1 (т.к. значения F(30) у нас нет, то 0.
 
              +1             *2

F(14) = F(14+1) + F(14*2) = 1+0=1
F(13) = F(14) + F(13*2) = 1+0=1
F(12) = F(13) + F(12*2) = 1+0=1
F(11) = F(12) + F(11*2) = 1+0=1
F(10) = F(11) + F(10*2) = 1+0=1
F(9) = F(10) + F(9*2) = 1+0=1
F(8) = F(9) + F(8*2) = 1+1=2
F(7) = F(8) + F(7*2) = 2+1=3
F(6) = F(7) + F(6*2) = 3+1=4
F(5) = F(6) + F(5*2) = 4+1=5
F(4) = F(5) + F(4*2) = 5+2=7
F(3) = F(4) + F(3*2) = 7+4=11
F(2) = F(3) + F(2*2) = 11+7=18
F(1) = F(2) + F(1*2) = 18+18=36

Ответ: 36 программ.


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

1. прибавь 1
2. прибавь 3
3. умножить на 2

Сколько есть программ, которые число 3 преобразуют в число 15.


Всё очень похоже на предыдущий пример!

Мы имеем    +1              +3             *2

F(15)=1
F(14)=      F(14+1) +  F(14+3)  +  F(14*2) = F(15)+F(17)+F(28)=1+0+0=1
F(13)=      F(13+1) +  F(13+3)  +  F(13*2) = F(14)+F(16)+F(26)=1+0+0=1
F(12)=      F(12+1) +  F(12+3)  +  F(12*2) = F(13)+F(15)+F(24)=1+1+0=2
F(11)=      F(11+1) +  F(11+3)  +  F(11*2) = F(12)+F(14)+F(22)=2+1+0=3
F(10)=      F(11)+F(13)+F(20)=3+1+0=4
F(9) =       F(10)+F(12)+F(18)=4+2+0=6
F(8)=        F(9)+F(11)+F(16)=6+3+0=9
F(7)=        F(8)+F(10)+F(14)=9+4+1=14
F(6)=        F(7)+F(9)+F(12)=14+6+2=22
F(5)=        F(6)+F(8)+F(10)=22+9+4=35
F(4)=        F(5)+F(7)+F(8)=35+14+9=58
F(3)=        F(4)+F(6)+F(6)=58+22+22=102

Ответ: 102 программы.