СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости




Задания
Версия для печати и копирования в MS Word
Задание 22 № 13633

Исполнитель А17 преобразует число на экране.

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

1. Прибавить 1

2. Умножить на 2

3. Умножить на 3

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

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

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

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

Решение.

Используем динамическое программирование. Заведем массив dp, где dp[i] — количество способов получить число i.

База динамики dp[2] = 1.

Переходы:

dp[i] = dp[i-1] + dp[i/2](если i - четно) + dp[i/3] (если i кратно 3).

При этом если i > 15, а i-1 или i/2 или i/3 меньше 15, то этими значениями будем пренебрегать, т.к. тогда не будет выполнено условие траектории. Далее будут показаны значения массива dp от 2 до 30:

1 1 2 2 4 4 6 7 9 9 15 15 19 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 42

 

Ответ:42.

Источник: Тренировочная работа по ИНФОРМАТИКЕ 11 класс 18 января 2017 года Вариант ИН10303, Тренировочная работа по ИНФОРМАТИКЕ 11 класс 12 мая 2017 года Вариант ИН10504