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




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

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

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

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

2. Прибавить 5

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

Сколько существует программ, которые число 1 преобразуют в число 20?

Пояснение.

Используем метод динамического программирования. Возьмем массив dp, где dp[i] - кол-во способов получить число i из единицы с помощью данных команд.

База динамики:

dp[1]=1;

Переход:

dp[i]=dp[i-2]+dp[i-5].

Тогда значения в нашем массиве будут следующие(от 1 до 20): 1 0 1 0 1 1 1 2 1 3 2 4 4 5 7 7 11 11 16 18.

 

Ответ: 18.

Источник: ЕГЭ — 2017. До­сроч­ная волна по информатике