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

Задание#T4860

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

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

прибавить 1
умножить на 2
прибавить 3

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

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

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

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

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

Указание:

Рассмотрите отдельно переход от до и от до .

Решение:

Пусть

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

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

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

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

(слагаемое

встречается дважды, потому что можно получить из двумя способами: умножением на и прибавлением )

Теперь рассмотрим переход от до . Очевидно, что операция умножения использоваться не может. Можно раза прибавить по или по очереди прибавить и . Прибавление и можно делать в любом порядке, это два разных способа, всего получается способа перехода от к .

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

программ.

Ответ: 96

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

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

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

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

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

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

Задание#T4860

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

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

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