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




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

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

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

1) Прибавить 1;

2) Прибавить 2;

3) Прибавить 4.

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

Программа для исполнителя Осень16 — это последовательность команд.

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

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

Пояснение.

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

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

Переходы будут иметь вид:

dp[i] = dp[i-1] + dp[i -2] + dp[i-4].

При этом, если i-1 или i-2 или i-4 меньше 8, а i больше 8, то тогда его не нужно учитывать (поскольку тогда мы обойдем число 8, а этого нельзя делать по условию).

Далее будут значения от 1 до 15 в нашем массиве dp: 1 1 2 3 6 10 18 31 31 62 93 186 310 558 961

 

Ответ: 961.

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