≡ информатика
сайты - меню - вход - новости




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

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

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

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

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

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

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

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

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

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 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 > 14, а i-1 или i/2 или i/3 меньше 14, то этими значениями пренебрегаем, т.к. тогда не будет выполнено условие траектории. Далее будут показаны значения массива dp от 2 до 28:

1 1 2 2 4 4 6 7 9 9 15 15 19 19 19 19 19 19 19 19 19 19 19 19 19 19 38.

 

Ответ:38.

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