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

Задание#T30258

Исполнитель РазДва преобразует число на экране.

У исполнителя есть две команды, которым присвоены номера:

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

Первая команда увеличивает число на экране на вторая умножает его на

Программа для исполнителя РазДва – это последовательность команд.

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

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

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

Нужно сначала преобразовать в затем в и в

Пусть

– количество программ, преобразующих исходное число в число Это число равно сумме

для всех из которых можно одной командой получить Будем находить значения

последовательно для всех от до :

(единственная программа, сохраняющая исходное число, – пустая)

Переход от до можно сделать без удвоений – прибавлением по (

) или с однократным удвоением, при этом удвоить можно одно из трёх чисел

или Всего получается способа перехода.

Переход от к можно сделать двумя способами: одним удвоением или многократным прибавлением

Таким образом, на первом этапе есть вариантов действий, на втором – на третьем – На каждом из этих этапов можно выбрать способ преобразования независимо, значит, общее количество вариантов равно

Ответ: 48

Это задание составили эксперты «СтатГрада» для Яндекса

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

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

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

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

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

Задание#T30258

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

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

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