Задача
Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2.
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 1 результатом является число 20, и при этом траектория вычислений содержит число 10?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.
Решение (Рекурентная формула)
Запишем рекуррентные формулы для вычисления количества возможных программ (KN) для получения числа N из некоторого начального числа:
\[K_{N} = K_{N-1}\] |
- для всех чисел, которые не делятся на 2; |
\[K_{N} = K_{N-1}+K_{N // 2}\] |
- для чисел, которые делятся на 2. |
Все допустимые программы можно разбить на две части (т.к. число 10 должно обязательно входить в траекторию):
- получение из числа 1 числа 10;
- получение из числа 10 числа 20.
Для начального числа 1 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды K1=1.
Составим таблицу для первой части (получение числа 10 из 1):
Поскольку число 10 должно обязательно войти в траекторию, начинаем составлять таблицу для второй части с этого числа заново, считая, что все ячейки для меньших чисел равны нулю.
Ответ: 28.
