Алгоритмы решения задания 22 контрольных измерительных материалов единого государственного экзамена 2019 года по информатике и ИКТ (ознакомление с опытом работы учителя информатики С.С. Полякова МАОУ "Гимназия № 3" Фрунзенского района г. Саратов)
презентация к уроку по информатике и икт (11 класс)

Слайд 1

Государственное бюджетное общеобразовательное учреждение средняя школа № 4 имени В.П. Глушко А.В . Казакова Алгоритмы решения задания 22 КИМ ЕГЭ 2019 по информатике и ИКТ (Из опыта работы учителя информатики С.С . Полякова МАОУ "Гимназия № 3" Фрунзенского района г . Саратов)

Слайд 2

2

Слайд 3

Задание 22. ЕГЭ 2019 Тема: динамическое программирование. Что нужно знать: • динамическое программирование – это способ решения сложных задач путем сведения их к более простым задачам того же типа; • с помощью динамического программирования решаются задачи, которые требуют полного перебора вариантов: «подсчитайте количество вариантов…» «как оптимально распределить…» «найдите оптимальный маршрут …» (Материалы для подготовки к ЕГЭ-2019 , © К. Поляков, 2009-2018, http://kpolyakov.spb.ru ) 2

Слайд 4

3

Слайд 5

№ 73 Исполнитель Июнь 16 преобразует число на экране. У исполнителя есть три команды, которым присвоены номера: 1. Прибавить 1 2. Прибавить 2 3. Умножить на 2 Сколько существует программ, для которых при исходном числе 2 результатом является число 12 и при этом траектория вычислений содержит число 10? (Материалы для подготовки к ЕГЭ-2019 , © К. Поляков, 2009-2018, http://kpolyakov.spb.ru ) 4

Слайд 6

Соглашения: Обозначим за К( N) количество программ, которые приведут из числа N к числу N+1 . Алгоритм решения всегда реверсивный. Если алгоритм решения не содержит число М , то К(М)=0 . Всегда есть хотя бы одна программа, приводящая к конечному результату. 5

Слайд 7

Решение: 2 10 12 У исполнителя есть три команды, которым присвоены номера: 1. Прибавить 1 2 . Прибавить 2 3 . Умножить на 2 К(12) = 1 К(11)=К(11+1)+К(11+2)+К(11*2)=К(12)+К(13)+К(22)=1+0+0= 1 К(10)=К(10+1 )+ К(10+2 )+ К(10*2 )= К(11)+К(12)+К(20)=1+1+0= 2 Теперь в траектории вычислений не учитываются числа > 10 . К(9)=К(9+1 )+ К(9+2 )+ К(9*2 )= К(10)+К(11)+К(18)=2+ 0 + 0 = 2 К(8)=К(8+1 )+ К(8+2 )+ К(8*2 )= К(9)+К(10)+К(16)=2+2+ 0 = 4 К(7)=К(7+1 )+ К(7+2 )+ К(7*2 )= К(8)+К(9)+К(14)=4+2+ 0 = 6 К(6)=К(7)+К(8)+К(12)=6+4+ 0 = 10 К(5)=К(6)+К(7)+К(10)=10+6+2= 18 К(4)=К(5)+К(6)+К(8)=18+10+4= 32 К(3)=К(4)+К(5)+К(6)=32+18+10= 60 К(2)=К(3)+К(4)+К(4)=60+32+32= 124 Ответ: 124 программы 6

Слайд 8

Исполнитель Июнь17 преобразует число на экране. У исполнителя есть три команды, которым присвоены номера: 1. Прибавить 1 2. Прибавить 2 3. Прибавить 4 Сколько существует программ, для которых при исходном числе 2 результатом является число 13 и при этом траектория вычислений не содержит число 6? № 84 (Материалы для подготовки к ЕГЭ-2019 , © К. Поляков, 2009-2018, http://kpolyakov.spb.ru ) 7

Слайд 9

Решение: 2  6 13 У исполнителя есть три команды, которым присвоены номера: 1. Прибавить 1 2. Прибавить 2 3. Прибавить 4 К(13) = 1 К(12)=К(12+1)+К(12+2)+К(12+4)=К(13)+К(14)+К(16)=1+ 0 + 0 = 1 К(11)=К(11+1)+К(11+2)+К(11+4)=К(12)+К(13)+К(15)=1+1+ 0 = 2 К(10)=К(10+1 )+ К(10+2 )+ К(10+4 )= К(11)+К(12)+К(14)=2+1+ 0 = 3 К(9)=К(10)+К(11)+К(13)=3+2+1= 6 К(8)=К(9)+К(10)+К(12)=6+3+1= 10 К(7)=К(8)+К(9)+К(11)=10+6+2= 18 К(6)= 0 К(5)=К(6)+К(7)+К(9)= 0 +18+6= 24 К(4)=К(5)+К(6)+К(8)=24+ 0 +10= 34 К(3)=К(4)+К(5)+К(7)=34+24+18= 76 К(2)=К(3 )+К(4)+К(6)=76+34+ 0 = 110 8

Слайд 10

Исполнитель Июнь17 преобразует число на экране. У исполнителя есть три команды, которым присвоены номера: 1. Прибавить 1 2. Прибавить 2 3. Прибавить 4 Сколько существует программ, для которых при исходном числе 2 результатом является число 13 и при этом траектория вычислений не содержит число 6 ? Ответ: 110 № 84 9

Слайд 11

10 № 74 (Материалы для подготовки к ЕГЭ-2019 , © К. Поляков, 2009-2018, http://kpolyakov.spb.ru ) Исполнитель Июнь 16 преобразует число на экране. У исполнителя есть три команды, которым присвоены номера: 1. Прибавить 1 2. Прибавить 2 3. Умножить на 3 Сколько существует программ, для которых при исходном числе 2 результатом является число 16 и при этом траектория вычислений содержит число 14?

Слайд 12

12