informaticsSimilar presentations:
Алгоритмы решения задания 22 КИМ ЕГЭ 2019 по информатике и ИКТ
1.
Государственное бюджетноеобщеобразовательное учреждение
средняя школа № 4
имени В.П. Глушко
А.В. Казакова
Алгоритмы решения задания 22
КИМ ЕГЭ 2019 по информатике и ИКТ
(Из опыта работы учителя информатики
С.С. Полякова
МАОУ "Гимназия № 3"
Фрунзенского района г. Саратов)
2.
23.
Тема: динамическое программирование.Что нужно знать:
• динамическое программирование – это способ решения
сложных задач путем сведения их к более простым задачам того
же типа;
• с помощью динамического программирования решаются
задачи, которые требуют полного перебора вариантов:
«подсчитайте количество вариантов…»
«как оптимально распределить…»
«найдите оптимальный маршрут…»
(Материалы для подготовки к ЕГЭ-2019 , © К. Поляков, 2009-2018, http://kpolyakov.spb.ru)
2
4.
35.
(Материалы для подготовки к ЕГЭ-2019 , © К. Поляков, 2009-2018, http://kpolyakov.spb.ru)Исполнитель Июнь16 преобразует число на экране.
У исполнителя есть три команды, которым
присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 2
Сколько существует программ, для которых при
исходном числе 2 результатом является число 12 и
при этом траектория вычислений содержит число
10?
4
6.
1) Обозначим за К(N) количествопрограмм, которые приведут из числа
N к числу N+1.
2) Алгоритм решения всегда
реверсивный.
3) Если алгоритм решения не содержит
число М, то К(М)=0.
4) Всегда есть хотя бы одна программа,
приводящая к конечному результату.
5
7.
У исполнителя есть три команды, которым присвоены номера: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.
(Материалы для подготовки к ЕГЭ-2019 , © К. Поляков, 2009-2018, http://kpolyakov.spb.ru)Исполнитель Июнь17 преобразует число на экране.
У исполнителя есть три команды, которым
присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Прибавить 4
Сколько существует программ, для которых при
исходном числе 2 результатом является число 13 и
при этом траектория вычислений
не содержит число 6?
7
9.
У исполнителя есть три команды, которым присвоены номера: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
8
К(2)=К(3)+К(4)+К(6)=76+34+0=110
10.
Исполнитель Июнь17 преобразует число на экране.У исполнителя есть три команды, которым
присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Прибавить 4
Сколько существует программ, для которых при
исходном числе 2 результатом является число 13 и
при этом траектория вычислений
не содержит число 6?
Ответ: 110
9
11.
(Материалы для подготовки к ЕГЭ-2019 , © К. Поляков, 2009-2018, http://kpolyakov.spb.ru)Исполнитель Июнь16 преобразует число на экране. У
исполнителя есть три команды, которым присвоены
номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 3
Сколько существует программ, для которых при
исходном числе 2 результатом является число 16 и
при этом траектория вычислений содержит число 14?
10