Презентация, доклад выступления на заседании ГМО учителей информатики Алгоритмы решения задания 22 КИМ ЕГЭ 2019 по информатике и ИКТ

Казакова

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

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

(Материалы для подготовки к ЕГЭ-2019 , © К. Поляков, 2009-2018, http://kpolyakov.spb.ru)

2

команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 2
Сколько существует программ, для которых при исходном числе 2 результатом является число 12 и при этом траектория вычислений содержит число 10?

(Материалы для подготовки к ЕГЭ-2019 , © К. Поляков, 2009-2018, http://kpolyakov.spb.ru)

4

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

5

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

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

№ 84

(Материалы для подготовки к ЕГЭ-2019 , © К. Поляков, 2009-2018, http://kpolyakov.spb.ru)

7

Прибавить 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

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

№ 84

9

http://kpolyakov.spb.ru)

Исполнитель Июнь16 преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 3
Сколько существует программ, для которых при исходном числе 2 результатом является число 16 и при этом траектория вычислений содержит число 14?