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

Задание#T30175

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

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

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

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

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

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

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

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

Пусть

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

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

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

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

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

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

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

Ответ: 42

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

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

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

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

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

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

Задание#T30175

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

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

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