Динамическое программирование в задачах ЕГЭ.

Волошина Гульшат Мунировна,

учитель информатики МБОУ «Гимназия №26»,

город Набережные Челны

Еще недавно руководитель Федеральной комиссии разработчиков контрольно-измерительных материалов ЕГЭ по информатике и ИКТ Михаил Ройтберг утверждал, что «в ЕГЭ по информатике нет задач, требующих больших вычислений». Современная практика говорит о другом, задачи, на вычисление которых уходит много времени, появились и производимые вычисления требуют идеальной внимательности и аккуратности. Как избежать полного перебора и уменьшить количество вычислений? Возникает необходимость применять различные математические методы и один из них метод динамического программирования.

Динамическое программирование в теории управления и теории вычислительных систем - способ решения сложных задач путём разбиения их на более простые подзадачи.

Среди переборных и некоторых других задач можно выделить класс задач, обладающих одним хорошим свойством: имея решения некоторых подзадач (например, для меньшего числа n), можно практически без перебора найти решение исходной задачи.

С помощью динамического программирования решаются задачи, которые требуют полный перебор вариантов и звучат как:

• «подсчитайте количество вариантов…»

• «как оптимально распределить…»

• «найдите оптимальный маршрут…» и т.д.

Самый простейший пример реализации данного метода: определение последовательности чисел Фибоначчи: 1, 1, 2, 3, 5, 8 и т.д.

F₁ =1, F₂ =1, F₃ = F₁+ F₂

Получаем рекуррентную формулу

F_n = F_n-2+ F_n-1

Рекуррентная формула - формула, выражающая каждый член последовательности через p предыдущих членов.

Рассмотрим примеры решение 22 задачи из вариантов ЕГЭ по информатике.

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

1. Прибавь 1

2. Умножь на 3

Первая из них увеличивает число на экране на 1, вторая утраивает его. Программа для утроителя - это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число N=20?

Продумаем рекуррентные формулы для данного исполнителя:

1) K_n = K_n-1

2. K_n = K_n-1+ K_n/3 в случае, когда n кратно 3.

Мы получим две рекуррентные формулы, так как исполнитель выполняет две команды.

Далее заполним вычисления в виде таблицы, начав отсчет с «1» по условию задачи:

K₁= 1, чтобы получить n=1 используется одна программа и в данном случае она будет «пустая», без команд.

K₂ = K_2-1 = K₁= 1

K₃ = K_3-1 + K_3/3= K₂ + K₁= 1+1= 2

K₄ = K_4-1 = K₃= 2 и т.д. Необходимо произвести расчеты до тех пор, пока n не достигнет значения «20» по условию задачи.

Таблица примет вид:

Ответ: 12.

Задача №2. Исполнитель Апрель16 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

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

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

Первая команда увеличивает число на экране на 1, вторая увеличивает на 3. Программа для исполнителя Апрель16 - это последовательность команд. Сколько существует программ, для которых при исходном числе 3 результатом является число 21 и при этом траектория вычислений содержит число 12 и не содержит число 18?

Решение:

В данной задаче так же продумываем рекуррентную формулу, в данном случае, обе команды отразим в одной формуле, так ограничений к n нет:

1. K_n = K_n-1+ K_n-3

Заполним таблицу и посмотрим, как дополнительные условия отразятся на окончательном результате. Отсчет начнем с «3» по условию задачи:

K₃= 1, чтобы получить n=3 используется одна программа и в данном случае она будет «пустая», без команд.

K₄ = K_4-1 + K_4-3= K₃ + K₁ = 1+0 = 1, n=1 и n=2 существуют вне траектории наших вычислений, поэтому K₁ так же как и K₂, равны «0».

Количество программ, которое позволяет получить «12»: K₁₂ = K_12-1 + K_12-3= K₁₁ + K₉ = 13+6 = 19. Это первое обязательное условие, для дальнейших вычислений обнулим K_n при n = 3, 4, 5, … 11. Продолжим заполнение таблицы:

По условию задачи число «18» не входит в траекторию вычислений, следовательно, мы должны проигнорировать данное значение и K₁₈ = 0

Ответ: 133.

Задача №3. Исполнитель Тренер преобразует целое число, записанное на экране. У исполнителя четыре команды, каждой команде присвоен номер:

1. Прибавь 1.

2. Сделай четное.

3. Сделай нечетное.

4. Умножь на 10.

Первая из них увеличивает на «1» исходное Х, вторая умножает это число на «2», третья переводит Х в число 2х+1, четвертая умножает его на «10».

Например, вторая команда число «10» в число «20», а третья число «10» в число «21».

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

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

Решение:

Рекуррентные формулы будут следующего вида:

1. K_n = K_n-1

2. K_n = K_n-1+ K_n/2 в случае, когда n - четное.

3. K_n = K_n-1+ K_(n-1)/2 в случае, когда n - нечетное.

4. K_n = K_n-1+ K_n/2+ K_n/10 в случае, когда n - делится на «10».

Построим таблицу вычислений:

Ответ: 71.

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

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

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

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Удвоитель - это последовательность команд. Сколько существует программ, преобразующих число 4 в число 24, предпоследней командой которых является команда «1»?

Решение:

Конец программы может выглядеть: «… 12» или «… 11» по условию задачи. В первом варианте число «24» можно получить из «11»: (11+1)+2, во втором варианте из числа «22»: 22+1+1=24.

Следовательно, задача сводится к поиску количества программ, которое приводит к значению «11» и «22».

Наши рекуррентные формулы будут выглядеть:

1) K_n = K_n-1

2) Kn = Kn-1+ Kn/2 в случае, когда n - четное.

Заполним таблицу вычислений:

Ответ: 3+15=18.

Мы рассмотрели решение разнотипных задач в задании 22 из ЕГЭ по информатике.

Надо отметить, что метод динамического программирование используется и при поиске количества путей между городами в графе, а так же при определении выигрышных стратегий игроков в 26 задании ЕГЭ по информатике.

Но об этом в следующей нашей встрече.

Источники информации для подготовки данной статьи:

• kpolyakov.spb.ru/

• https://vk.com/ege_inform

• https://vk.com/ege100ballov</

• Информатика. Углубленный уровень: учебник для 11 класса: в 2ч. /К.Ю.Поляков, Е.А. Еремин.- 2-е изд. -М.:БИНОМ. Лаборатория знаний, 2014