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

Задание#T29793

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

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

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

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

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

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

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

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

Нужно сначала преобразовать 1 в 14, а затем 14 в 50, не заходя в 16.

Пусть F(b) – количество программ, преобразующих исходное число 1 в число Это число равно сумме F(x) для всех из которых можно одной командой получить Будем находить значения F(b) последовательно для всех от 1 до 14:

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

F(2) = F(1) + F(1) = 2 (от 1 можно перейти к 2 двумя способами)

F(3) = F(2) + F(1) = 2 + 1 = 3

F(4) = F(3) + F(2) = 3 + 2 = 5

F(5) = F(4) = 5

F(6) = F(5) + F(3) + F(2) = 5 + 3 + 2 = 10

F(7) = F(6) = 10

F(8) = F(7) + F(4) = 10 + 5 = 15

F(9) = F(8) + F(3) = 15 + 3 = 18

F(10) = F(9) + F(5) = 18 + 5 = 23

F(11) = F(10) = 23

F(12) = F(11) + F(6) + F(4) = 23 + 10 + 5 = 38

F(13) = F(12) = 38

F(14) = F(13) + F(7) = 38 + 10 = 48

Рассмотрим теперь переход от 14 к 50. Чтобы «обойти» число 16, нужно выполнить умножение. Можно умножить 14 на 2 или на 3, получится 28 или 42. В любом из этих случаев дальнейшее умножение невозможно – получится число больше 50, поэтому придётся прибавлять по 1 до 50. Можно увеличить 14 на 1, получится 15, после этого можно выполнить умножение на 2 или на 3 и далее прибавлять по 1 до 50. Всего получается 4 способа перехода от 14 к 50 без захода в 16.

Любой из способов перехода от 1 к 14 можно совместить с любым из способов перехода от 14 к 50, всего получается 48 · 4 = 192 программы.

Ответ: 192

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

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

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

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

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

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

Задание#T29793

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

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

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