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

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

  1. Прибавить 1
  2. Умножить на 3
  3. Прибавить 2

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

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 10, 30.

 

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

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

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

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

n(i)  = n(i-1) + n(i/3)(если i/3 целое число и i/3 ≥ 3 и i/3 ≠ 4) + n(i-2)(если i-2 ≥ 3 и i-2 ≠ 8)

n(3) = 1
n(4) = n(3) = 1
n(5) = n(4) + n(3) = 2
n(6) = n(5) + n(4) = 3
n(7) = n(6) + n(5) = 5
n(8) = n(7) + n(6) = 8
n(9) = n(8) + n(3) + n(1) = 14
n(10) = n(9) = 14
n(11) = n(10) + n(9) = 28
n(12) = n(11) + n(10) = 42
n(13) = n(12) + n(11) = 70
n(14) = n(13) + n(12) = 112