ЕГЭ. Задание №22, К.Поляков. Задача №71.

Тема: динамическое программирование.

Исполнитель Май16 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1

2. Прибавить 2

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2. Сколько существует программ, для которых при исходном числе 1 результатом является число 13 и при этом траектория вычислений содержит число 7?

Решение:

Дойдём до числа 7 обычным образом:

К(13)=1

К(12)=К(12+1)+К(12+2)=К(13)+К(14)=1+0=1

К(11)=К(11+1)+К(11+2)=К(12)+К(13)=1+1=2

К(10)=К(10+1)+К(10+2)=К(11)+К(12)=2+1=3

К(9)=К(9+1)+К(9+2)=К(10)+К(11)=3+2=5

К(8)=К(8+1)+К(8+2)=К(9)+К(10)=5+3=8

К(7)=К(7+1)+К(7+2)=К(8)+К(9)=8+5=13

Теперь начинаем расчёт заново (преобразуем число 1 в число 7), но не с К(7)=1, а с К(7)=13. При этом считаем, что чисел, которые больше 7, в задаче нет.

К(7)=13

К(6)=К(6+1)+К(6+2)=К(7)+К(8)=13+0=13

К(5)=К(5+1)+К(5+2)=К(6)+К(7)=13+13=26

К(4)=К(4+1)+К(4+2)=К(5)+К(6)=26+13=39

К(3)=К(3+1)+К(3+2)=К(4)+К(5)=39+26=65

К(2)=К(2+1)+К(2+2)=К(3)+К(4)=65+39=104

К(1)=К(1+1)+К(1+2)=К(2)+К(3)=104+65=169

Ответ: 169