Статья по подготовке к ЕГЭ по информатике (задача 22).

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

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

 учитель информатики МБОУ «Гимназия №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» по условию задачи.

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

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
Kn	1	1	2	2	2	3	3	3	5	5	5	7	7	7	9	9	9	12	12	12

Ответ: 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».

n	3	4	5	6	7	8	9	10	11	12
Kn	1	1	1	2	3	4	6	9	13	19

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

n	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
Kn	0	0	0	0	0	0	0	0	0	19	19	19	38	57	76	114

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

n	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21
Kn	0	0	0	0	0	0	0	0	0	19	19	19	38	57	76	0	57	133	133

Ответ: 133.

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

1.      Прибавь 1.

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

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

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

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

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

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

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

Решение:

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

₁₎               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».

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

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14
Kn	1	2	3	5	7	10	13	18	23	31	38	48	58	71

Ответ: 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 - четное.

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

n	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
Kn	1	1	1	1	2	2	3	3	4	4	5	5	7	7	9	9	12	12	15

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

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

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

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

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

·                    http://kpolyakov.spb.ru/

·                    https://vk.com/ege_inform

·                    https://vk.com/ege100ballov

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

Краткое описание документа:

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

Автор ссылается на материалы Константина Юрьевича Полякова и представляет свое решение задач.