Исполнители алгоритмов. Задача 9-2
Исполнитель преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:
- Прибавить 1
- Умножить на 3
- Прибавить 2
Сколько существует программ, для которых при исходном числе 3 результатом является число 14, и при этом траектория вычислений содержит число 9?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 10, 30.
Для решения задачи составим таблицу, в которой в одном столбце число, а во втором- количество программ, которыми можно это число получить:
Также для вычисления количества программ 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