Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
Прибавить
Умножить на
Прибавить
Первая из них увеличивает число на экране на , вторая умножает его на , третья увеличивает его на .
Программа для Вычислителя – это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное число в число и при этом траектория вычислений программы содержит число ?
Примечание. Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Пример. Для программы при исходном числе траектория будет состоять из чисел .
Показать разбор и ответ
Для решения задачи воспользуемся методом динамического программирования. Выпишем в ряд все числа от до , записывая над каждым количество программ, с помощью которых это число может быть получено:
В частности, количество способов получить число указанными командами равно нулю. Но, например, число могло быть получено командой «прибавить » из числа , командой «умножить на » из числа и командой «прибавить » из числа . При этом число до этого могло было быть получено двумя способами, число — также двумя способами, а число — одним способом, следовательно, общее количество способов получить число равно .
Произведём аналогичные действия для чисел от до :
Каждой из десяти траекторий, по которой из числа может быть получено число , подходит любая из десяти траекторий, по которой из числа может быть получено число . По правилу произведения комбинаторики получим ответ .