Исполнитель РазДваТри преобразует число на экране.
У исполнителя есть три команды, которым присвоены номера:
прибавить 1
умножить на 2
прибавить 3
Первая команда увеличивает число на экране на , вторая умножает его на , третья увеличивает на .
Программа для исполнителя РазДваТри – это последовательность команд.
Сколько существует программ, которые преобразуют исходное число в число и при этом траектория вычислений содержит число ?
Траектория вычислений – это последовательность результатов выполнения всех команд программы. Например, для программы 312 при исходном числе траектория будет состоять из чисел , , .
Показать разбор и ответ
Указание:
Рассмотрите отдельно переход от до и от до .
Решение:
Пусть – количество программ, преобразующих число в число . Это число равно сумме для всех , из которых можно одной командой получить . Будем находить значения последовательно для всех от до :
(единственная программа, сохраняющая исходное число – пустая)
(слагаемое встречается дважды, потому что можно получить из двумя способами: умножением на и прибавлением )
Теперь рассмотрим переход от до . Очевидно, что операция умножения использоваться не может. Можно раза прибавить по или по очереди прибавить и . Прибавление и можно делать в любом порядке, это два разных способа, всего получается способа перехода от к .
Всего получается программы перехода от к и программы перехода от к . Любую из первых программ можно совместить с любой из вторых, всего получается программ.
Ответ: 96
Это задание составили эксперты «СтатГрада» для Яндекса
Это задание решали 4 тыс. раз. С ним справились 48% пользователей.