ЕГЭ по информатике 2017 Задача 22 (Динамическое программирование)
материал для подготовки к егэ (гиа) по информатике и икт (10, 11 класс) на тему

Слайд 1

Консультационный центр по подготовке выпускников к Государственной (итоговой) аттестации Задание №22 Динамическое программирование Учитель информатики МАОУ «СОШ №80» Карпова Татьяна Александровна 2016 г.

Слайд 2

Основные понятия динамическое программирование – это способ решения сложных задач путем сведения их к более простым задачам того же типа с помощью динамического программирования решаются задачи, которые требуют полного перебор вариантов: «подсчитайте количество вариантов…» «как оптимально распределить…» «найдите оптимальный маршрут…»

Слайд 3

Задание №22 Проверяемые элементы : у мение анализировать результат исполнения алгоритма Уровень сложности: профильный Примерное время выполнения : 7 мин . Средний процент выполнения задания в 2016 г . – 38,2%

Слайд 4

У исполнителя Увеличитель две команды, которым присвоены номера: 1. прибавь 1, 2. умножь на 2. Первая из них увеличивает число на экране на 1, вторая – умножает его на 2. Программа для Увеличителя – это последовательность команд. Сколько есть программ, которые число 3 преобразуют в число 23? Краткая запись условия Команды 1) N= x+1 2) N= x*2 Начальное число 3 Конечное число 23 траектория Пример №1

Слайд 5

1 способ – выписать все нужные программы, построить дерево программ . 2 способ – подсчитать число программ, не выписывая их явно, а написав формулу, которая позволяет найти количество программ получения данного числа, если уже известно количество программ для получения меньших чисел ( при таком решении удобно заполнять таблицу ). Способы решения задания

Слайд 6

Дерево возможных путей вычислений 1 способ

Слайд 7

У исполнителя Увеличитель две команды, которым присвоены номера: 1. прибавь 1, 2. умножь на 2. Первая из них увеличивает число на экране на 1, вторая – умножает его на 2. Программа для Увеличителя – это последовательность команд. Сколько есть программ, которые число 3 преобразуют в число 23? 2 способ Краткая запись условия: 3  23 N= x + 1 N = x *2 Обратные команды : 1) x = N – 1 2) x = N/2

Слайд 8

N N-1 N/2 R(N) 3 1 4 3 - 5 4 - 6 5 3 7 6 - 8 7 4 9 8 - 10 9 5 11 10 - 12 11 6 13 12 - 14 13 7 15 14 - 16 15 8 1 1 1+1= 2 2 2 +1= 3 3 3 +1 =4 4 4+ 2 =6 6 6+ 2 =8 8 8+3 = 11 N N-1 N/2 R(N) 17 16 - 18 17 9 19 18 - 20 19 10 21 20 - 22 21 11 23 22 - 14+4=18 18 18+4=22 22 Ответ: 22 2 способ 14 11+3=14 11

Слайд 9

Исполнитель А12 S преобразует целое число, записанное на экране. У исполнителя три команды, каждой команде присвоен номер: 1. Прибавь 1 2 . Прибавь 2 3 . Прибавь предыдущее Первая команда увеличивает число на экране на 1, вторая увеличивает это число на 3, третья прибавляет к числу на экране число, меньшее на 1 (к числу 3 прибавляется 2, к числу 11 прибавляется 10 и т. д.). Программа для исполнителя А12 S – это последовательность команд. Сколько существует программ, которые число 3 преобразуют в число 10 ? 3  10 N= x + 1 N=x + 2 N=x + (x-1) Обратные команды: x = N – 1 X=N – 2 X=(N+1)/2 Пример 2 N N-1 N-2 (N+1)/2 R(N) 3 1 4 3 - - 1 5 4 3 3 3 6 5 4 - 4 7 6 5 4 4+3+1=8 8 7 6 - 8+4=12 9 8 7 5 12+8+3=23 10 9 8 - 23+12= 35 Проверить таблицу

Слайд 10

Исполнитель Июнь15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера: 1. Прибавить 1 2. Умножить на 2 Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Июнь15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 29 и при этом траектория вычислений содержит число 14 и не содержит числа 25? 2  29 Траектория: Содержит 14 Не содержит 29 N= x + 1 N=x *2 Обратные команды: x = N – 1 X=N/2 Пример 3

Слайд 11

N N-1 N / 2 R(N) 2 1 3 2 - 1 4 3 2 2 5 4 - 2 6 5 3 3 7 6 - 3 8 7 4 5 9 8 - 5 10 9 4 7 11 10 - 7 12 11 6 10 13 12 - 10 14 13 7 13 N N-1 N / 2 R(N) 14 13 15 14 - 13 16 15 - 13 17 16 - 13 18 17 - 13 19 18 - 13 20 19 - 13 21 20 - 13 22 21 - 13 23 22 - 13 24 23 - 13 25 0 26 25 13 0+0=0 27 26 - 0 28 27 14 0+13=13 29 28 - 13

Слайд 12

Список литературы В.Р. Лещинер «Методические рекомендации по некоторым аспектам совершенствования преподавания информатики ИКТ», Москва 2014г. http:// kpolyakov.spb.ru/school/ege.htm Разбор задания №22. Исполнитель. ЕГЭ по информатике 2015. Задание ФИПИ: https ://www.youtube.com/watch?v=ylEBbv6a4cw