Россия, Сургут
СДЕЛАЙТЕ СВОИ УРОКИ ЕЩЁ ЭФФЕКТИВНЕЕ, А ЖИЗНЬ СВОБОДНЕЕ
Благодаря готовым учебным материалам для работы в классе и дистанционно
Скидки до 50 % на комплекты
только до
Готовые ключевые этапы урока всегда будут у вас под рукой
Организационный момент
Проверка знаний
Объяснение материала
Закрепление изученного
Итоги урока
Была в сети 01.06.2024 11:44
Romanova Elvira Nikolaevna
учитель информатики
3 851
11 992 
Местоположение
Специализация
Динамическое программирование (задание 23, ЕГЭ по информатике)
Категория:
Информатика
10.01.2021 16:11
Просмотр содержимого документа
«Динамическое программирование (задание 23, ЕГЭ по информатике)»
ЕГЭ – ИНФОРМАТИКА: Задание 23
Динамическое программирование
Подготовила работу:
учитель МБОУ СОШ №7
Романова Э.Н.
Динамическое программирование – это способ решения сложных задач путём разбиения их на более простые подзадачи, сложность которых меньше исходной.
Общие сведения
Тема: Динамическое программирование
Сложность: повышенная
Максимальный балл за выполнение задания: 1 балл
Примерное время решения: 8 минут
Что проверяется: ум ение работать с графами, или с рядом чисел; умение анализировать результат исполнения алгоритма
Задание 23. ДЕМО - 2021 Открытый банк заданий ФИПИ
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
- Прибавь 1
- Умножь на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2.
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 1 результатом является число 20 , и при этом траектория вычислений содержит число 10 ?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например , для программы 121 при исходном числе 7 траектория будет состоять из чисел 8,16,17 .
Итак, мы имеем
Команды:
1. +1
2. *2
Траектория: 1 10 20
Надо определить: К ПР =?
Решение: 1. +1 2. *2 1 10 20 К ПР =?
1 способ:
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17
- 18 19 20
Ответ:
14
10
10
2
6
1
2
6
4
4
14
14
14
14
14
14
14
10
28
14
14
28
Решение: 1. +1 2. *2 1 10 20 К ПР =?
2 способ:
11
10
9
8
7
+1
*2
+1
*2
*2
+1
+1
*2
2
2
2
2
10
20
11
9
8
6
5
4
3
2
1
+1
*2
+1
*2
+1
*2
*2
+1
+1
*2
2
+1
*2
4
6
8
14
6
28
10
7
4
8
6
4
3
4
2
2
28
Ответ:
Решение: 1. +1 2. *2 1 10 20 К ПР =? 1) К ПР1 =?: 1 10 2) К ПР2 =?: 10 20 3) К ПР =К ПР1 *К ПР2
3 способ:
10
1
+1
*2
+1
*2
14
2
2
2
20
11
+1
*2
+1
1
7
3
4
12
+1
*2
4
+1
1
4
6
+1
…
*2
3
1
5
+1
+1
8
*2
2
20
6
1
1
10
+1
7
14*2=28
1
+1
8
1
+1
9
28
1
Ответ:
+1
10
Задание 23.
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
- Прибавь 1
- Умножь на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2.
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 1 результатом является число 20 , и при этом траектория вычислений НЕ содержит число 10 ?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например , для программы 121 при исходном числе 7 траектория будет состоять из чисел 8,16,17 .
Итак, мы имеем
Команды:
1. +1
2. *2
Траектория: 1 10 20
Надо определить: К ПР =?
Решение: 1. +1 2. *2 1 10 20 К ПР =?
1 способ:
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17
- 18 19 20
Ответ:
14
10
10
2
6
1
2
6
4
4
6
7
8
12
6
22
12
22
6
0
10
9
32
32
32
32
Решение: 1. +1 2. *2 1 10 20 К ПР =?
2 способ:
11
10
9
8
7
+1
*2
+1
*2
+1
*2
1
10
2
3
18
8
14
9
16
2
5
6
1
4
3
+1
+1
+1
+1
*2
*2
*2
*2
+1
*2
*2
+1
4
4
10
32
16
6
4
6
4
3
7
8
2
2
12
6
5
10
32
Ответ:
Задание 23. сайт К.Ю. Полякова https://kpolyakov.spb.ru/school/ege /
(№ 2463) Исполнитель Калькулятор преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1 2. Прибавить 3
Программа для исполнителя Калькулятор – это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 20 , и при этом траектория вычислений содержит число 10 и не содержит число 15 ?
Итак, мы имеем
Команды:
1. +1
2. +3
Траектория: 2 10 15 20
Надо определить: К ПР =?
Решение: 1. +1 2. +3 2 10 15 20 К ПР =?
1 способ:
2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17
- 18 19 20
11
12
13
4
1
6
1
9
3
1
2
13
10
19
20
26
13
39
13
65
26
16
17
15
156
91
65
156
Ответ:
Решение: 1. +1 2. +3 2 10 15 20 К ПР =?
2 способ:
16
15
14
18
17
12
13
+1
+1
+3
+3
+3
+1
+1
+3
+1
+3
2
3
2
5
5
17
19
17
20
14
18
16
15
13
15
9
11
8
10
7
6
+1
+1
+3
+3
+1
+1
+3
+3
+1
+3
+3
+1
24
12
36
12
7
12
13
12
11
9
8
11
14
10
12
7
9
10
5
4
3
2
+1
+3
+3
+3
+1
+1
+1
+3
72
48
108
156
8
5
6
7
4
6
5
3
156
Ответ:
Решение: 1. +1 2. +3 2 10 15 20 К ПР =? Найдем: 1) К ПР1 =?: 2 10 2) К ПР2 =?: 10 15 20 3) К ПР =К ПР1 *К ПР2
2 способ:
8
2
5
6
7
3
4
+1
+3
+3
+3
+3
+1
+1
+1
+1
+3
+3
+1
13
4
9
6
2
3
6
5
7
6
3
10
4
7
8
8
5
9
16
18
15
14
17
13
+1
+3
+3
+3
+1
+3
+1
+1
2
5
3
2
20
15
18
16
17
17
19
14
12
10
11
12 * 13 = 156
+1
+3
+3
+3
+1
+1
5
7
12
15
12
13
14
11
13
156
Ответ:
Тренировочная работа Статград ЕГЭ по информатике от 22.10.20
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1 2. Умножить на 3
Программа для исполнителя – это последовательность команд.
Сколько существует программ, которые преобразуют исходное число 1 в число 70 , и при этом траектория вычислений содержит число 22 ?
Траектория вычислений – это последовательность результатов выполнения всех команд программы.
Итак, мы имеем
Команды:
1. +1
2. *3
Траектория: 1 22 70
Надо определить: К ПР =?
Решение: 1. +1 2. *3 2 22 70 К ПР =? Найдем: 1) К ПР1 =?: 2 22 2) К ПР2 =?: 22 70 3) К ПР =К ПР1 *К ПР2
2 способ:
5
3
8
6
4
7
+1
*3
*3
+1
*3
+1
*3
+1
+1
*3
4
2
5
3
6
5
15
12
7
18
6
21
8
4
9
2
1
К ПР1 =15
+1
+1
*3
*3
15
9
3
3
2
6
К ПР2 =3
К ПР =15*3=45
23
24
22
*3
+1
*3
+1
2
3
24
66
69
23
45
Ответ:
Образовательный портал для подготовки к экзаменам СДАМ ГИА : РЕШУ ЕГЭ У исполнителя Удвоитель-Утроитель три команды, которым присвоены номера:
№ 5064
1. прибавь 1
2. умножь на 2
3. умножь на 3.
Первая из них увеличивает на 1 число на экране, вторая увеличивает это число в 2 раза, третья - в 3 раза.
Программа для Удвоителя-Утроителя — это последовательность команд. Сколько существует программ, которые число 1 преобразуют в число 13?
Итак, мы имеем
Команды:
1. +1
2. *2
3. *3
Траектория: 1 13
Надо определить: К ПР =?
Решение: 1. +1 2. *2 3. *3 1 13 К ПР =?
1
3 способ:
+1
38
2
*2
*3
+1
15
3
2
3
*3
*2
+1
8
4
4
6
*2
+1
*3
5
6
5
*2
+1
9
3
*3
6
8
*2
+1
2
7
12
*2
10
+1
1
8
12
1
+1
…
1
38
+1
Ответ:
13
Возможные проблемы :
- В неверном определении начальных условий Главная, возможная, проблема (ловушка) - невнимательность. Держим внимание!
- В неверном определении начальных условий
- Главная, возможная, проблема (ловушка) - невнимательность.
- Держим внимание!
И тогда «Они НЕ будут так страшны, как могут показаться)».
НАДО ПРОСТО БОЛЬШЕ ТРЕНИРОВАТЬСЯ
Спасибо за внимание!
Вебинар для учителей
Свидетельство об участии БЕСПЛАТНО!
Полезное для учителя
Реализация образовательных программ осуществляется с применением исключительно электронного обучения и ДОТ
