Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера: Прибавить 2 Умножить на 2 Прибавить 3 Первая из них увеличивает число на экране на 2,... | Яндекс.Репетитор

Задание#T801

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

Прибавить
Умножить на
Прибавить

Первая из них увеличивает число на экране на , вторая умножает его на , третья увеличивает его на .

Программа для Вычислителя – это последовательность команд.

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

Примечание. Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.

Пример. Для программы

при исходном числе траектория будет состоять из чисел

Показать разбор и ответ

Для решения задачи воспользуемся методом динамического программирования. Выпишем в ряд все числа от до , записывая над каждым количество программ, с помощью которых это число может быть получено:

В частности, количество способов получить число указанными командами равно нулю. Но, например, число могло быть получено командой «прибавить » из числа , командой «умножить на » из числа и командой «прибавить » из числа . При этом число до этого могло было быть получено двумя способами, число — также двумя способами, а число — одним способом, следовательно, общее количество способов получить число равно

Произведём аналогичные действия для чисел от до :

Каждой из десяти траекторий, по которой из числа может быть получено число , подходит любая из десяти траекторий, по которой из числа может быть получено число . По правилу произведения комбинаторики получим ответ

Ответ: 100

Это задание взято из демовариантов ФИПИ 2018-2020

Это задание решали 8 тыс. раз. С ним справились 39% пользователей.

Это задание в разделах:

Умение анализировать алгоритм, содержащий ветвление и цикл

Это задание в тестах:

Тренировочный вариант ЕГЭ по информатике №1

Задание#T801

Это задание в разделах:

Это задание в тестах:

Рекомендованные задания