Исполнители алгоритмов. Задача 9-1

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

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

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 3. Программа для исполнителя Май17 — это последовательность команд.

Сколько существует программ, для которых при исходном числе 1 результатом является число 17 и при этом траектория вычислений содержит число 9? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.

Например, для программы 12 при исходном числе 7 траектория будет состоять из чисел 8, 11, 12.

Ответ
169
Решение

Для решения задачи составим таблицу, в которой в одном столбце число, а во втором- количество программ, которыми можно это число получить:

Исполнители алгоритмов. Таблица подсчета программ

Также для вычисления количества программ n для очередного числа i можно воспользоваться формулой:

n(i)  = n(i-1) + n(i-3) (если i-3 ≥ 1 и i-3 ≠ 7 и i-3 ≠ 8)

n(1) = 1
n(2) = n(1) = 1
n(3) = n(2) = 1
n(4) = n(3) + n(1) = 2
n(5) = n(4) + n(2) = 3
n(6) = n(5) + n(3) = 4
n(7) = n(6) + n(4) = 6
n(8) = n(7) + n(5) = 9
n(9) = n(8) + n(6) = 13
n(10) = n(9) = 13
n(11) = n(10) = 13
n(12) = n(11) + n(9) = 26 
n(13) = n(12) + n(10) = 39 
n(14) = n(13) + n(11) = 52 
n(15) = n(14) + n(12) = 78 
n(16) = n(15) + n(13) = 117 
n(17) = n(16) + n(14) = 169