Презентация на тему "Алгоритмы решения задания 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