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

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

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

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

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

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

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

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

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

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

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

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

F1 =1, F2 =1, F3 = F1+ F2

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

Fn = Fn-2+ Fn-1

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

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

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

1. Прибавь 1

2. Умножь на 3

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

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

1) Kn = Kn-1

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

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

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

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

K2 = K2-1 = K1= 1

K3 = K3-1 + K3/3= K2 + K1= 1+1= 2

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

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

Ответ: 12.

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

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

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

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

Решение:

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

1. Kn = Kn-1+ Kn-3

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

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

K4 = K4-1 + K4-3= K3 + K1 = 1+0 = 1, n=1 и n=2 существуют вне траектории наших вычислений, поэтому K1 так же как и K2, равны «0».

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

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

Ответ: 133.

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

1. Прибавь 1.

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

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

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

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

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

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

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

Решение:

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

1. Kn = Kn-1

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

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

4. Kn = Kn-1+ Kn/2+ Kn/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) Kn = Kn-1

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

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

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

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

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

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

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

• [link]

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