Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Информатика / Статьи / Статья «Динамическое программирование в задачах ЕГЭ» (задача 22).

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

Международный конкурс по математике «Поверь в себя»

для учеников 1-11 классов и дошкольников с ЛЮБЫМ уровнем знаний

Задания конкурса по математике «Поверь в себя» разработаны таким образом, чтобы каждый ученик вне зависимости от уровня подготовки смог проявить себя.

К ОПЛАТЕ ЗА ОДНОГО УЧЕНИКА: ВСЕГО 28 РУБ.

Конкурс проходит полностью дистанционно. Это значит, что ребенок сам решает задания, сидя за своим домашним компьютером (по желанию учителя дети могут решать задания и организованно в компьютерном классе).

Подробнее о конкурсе - https://urokimatematiki.ru/


Идёт приём заявок на самые массовые международные олимпиады проекта "Инфоурок"

Для учителей мы подготовили самые привлекательные условия в русскоязычном интернете:

1. Бесплатные наградные документы с указанием данных образовательной Лицензии и Свидeтельства СМИ;
2. Призовой фонд 1.500.000 рублей для самых активных учителей;
3. До 100 рублей за одного ученика остаётся у учителя (при орг.взносе 150 рублей);
4. Бесплатные путёвки в Турцию (на двоих, всё включено) - розыгрыш среди активных учителей;
5. Бесплатная подписка на месяц на видеоуроки от "Инфоурок" - активным учителям;
6. Благодарность учителю будет выслана на адрес руководителя школы.

Подайте заявку на олимпиаду сейчас - https://infourok.ru/konkurs

  • Информатика

Поделитесь материалом с коллегами:

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

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

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

  1. 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 задании ЕГЭ по информатике.

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

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


Самые низкие цены на курсы профессиональной переподготовки и повышения квалификации!

Предлагаем учителям воспользоваться 50% скидкой при обучении по программам профессиональной переподготовки.

После окончания обучения выдаётся диплом о профессиональной переподготовке установленного образца (признаётся при прохождении аттестации по всей России).

Обучение проходит заочно прямо на сайте проекта "Инфоурок".

Начало обучения ближайших групп: 18 января и 25 января. Оплата возможна в беспроцентную рассрочку (20% в начале обучения и 80% в конце обучения)!

Подайте заявку на интересующий Вас курс сейчас: https://infourok.ru/kursy



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

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

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

Автор
Дата добавления 26.11.2016
Раздел Информатика
Подраздел Статьи
Просмотров54
Номер материала ДБ-390647
Получить свидетельство о публикации

УЖЕ ЧЕРЕЗ 10 МИНУТ ВЫ МОЖЕТЕ ПОЛУЧИТЬ ДИПЛОМ

от проекта "Инфоурок" с указанием данных образовательной лицензии, что важно при прохождении аттестации.

Если Вы учитель или воспитатель, то можете прямо сейчас получить документ, подтверждающий Ваши профессиональные компетенции. Выдаваемые дипломы и сертификаты помогут Вам наполнить собственное портфолио и успешно пройти аттестацию.

Список всех тестов можно посмотреть тут - https://infourok.ru/tests


Включите уведомления прямо сейчас и мы сразу сообщим Вам о важных новостях. Не волнуйтесь, мы будем отправлять только самое главное.
Специальное предложение
Вверх