Методика _23. Методическая разработка _Решение задач ЕГЭ по теме _Динамическое. Подготовка к кегэ по информатике в 2021 г. Учитель информатики

• Название: Подготовка к кегэ по информатике в 2021 г. Учитель информатики
• Анкор: Методика _23
• Дата: 12.10.2022
• Размер: 447.4 Kb.
• Имя файла: Методическая разработка _Решение задач ЕГЭ по теме _Динамическое.pptx
• Тип: Документы; #730703

Подготовка к КЕГЭ по информатике в 2021 г.

Учитель информатики

МБУ «Лицей №6» г.о. Тольятти

Серокурова А.А.

Мастер - класс

Разбор решения задания №23

Тольятти, 2021

Задание № 23 (повышенный уровень, время – 8 мин)

• Тема: динамическое программирование.
• Спецификация: Умение анализировать результат исполнения алгоритма

ЕГЭ-2020: % выполнения 56,0 %

Апробация-2021: % выполнения 9,9 %

Динамическое программирование

Что проверяется:

Умение анализировать результат исполнения алгоритма

• 1.6.2. Вычислимость. Эквивалентность алгоритмических моделей.
• 1.1.3. Умение строить информационные модели объектов, систем и процессов в виде алгоритмов.

Что нужно знать:

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

Типы заданий

Динамическое программирование:

• две команды
• три команды
• ограничение на траекторию
• ограничение на количество команд

(№ 3718) (А. Комков) Исполнитель Нолик преобразует число, записанное на экране в троичной системе счисления. У исполнителя есть две команды, которым присвоены номера:

• Вычесть 2
• Обнулить младший разряд

Первая команда уменьшает число на 2. Вторая команда обнуляет ненулевой младший разряд троичной записи числа. (Например, при выполнении этой команды число 21 преобразуется в число 20. Если в младшем разряде находится 0, то данная команда не выполняется).

Сколько существует программ, которые троичное число 212 преобразуют в троичное число 10?

Способ 1: Вручную таблицей

Переведем числа из троичной системы счисления в десятичную:

212 => 23 10 => 3

тогда команды будут такие:

1. Вычесть 2 2. Вычесть остаток от деления на 3

Ответ: 86

Способ 2: Программирование

С.С. Поляков:

L=[0]*24 L[23]=1 for x in range(23,2,-1): L[x-2] += L[x] if x % 3 != 0: L[(x//3)*3] += L[x] print(L[3])

А. Комков:

def f(start, end): if start < end: return 0 if start == end: return 1 if start % 3 == 0: return f(start - 2, end) return f(start - 2, end) + f(start- start % 3, end) print(f(23, 3))

(№ 3715) (А. Комков) Исполнитель Нолик преобразует двоичное число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:

1. Вычесть 1 2. Обнулить

Первая команда уменьшает число на 1. Вторая команда обнуляет все ненулевые разряды, кроме старшего (например, для исходного числа 11101 результатом работы команды будет число 10000), если таких разрядов нет, то данная команда не выполняется.
Сколько существует программ, которые исходное двоичное число 1100 преобразуют в двоичное число 100?

Ответ: 20

(№ 3105) У исполнителя Калькулятор две команды, которым присвоены номера:

1. прибавь 1 2. увеличь каждый разряд числа на 1

Например, число 23 с помощью команды 2 превратится в 34, а 29 в 39 (так как младший разряд нельзя увеличить). Если перед выполнением команды 2 какая-либо цифра равна 9, она не изменяется.

Сколько есть программ, которые число 25 преобразуют в число 51?

Ответ: 33

(№ 3719) (А. Комков) Исполнитель Нолик преобразует число, записанное на экране в четверичной системе счисления. У исполнителя есть три команды, которым присвоены номера:

Первая команда увеличивает число на 2. Вторая команда увеличивает число на 3. Третья команда приписывает к записи числа справа 0, например, для числа 123 результатом работы данной команды будет являться число 1230.

Сколько существует программ, которые число 1, записанное в четверичной системе счисления, преобразуют в четверичную запись 100?

Переведем числа из четверичной системы счисления в десятичную:

1 => 1 100 => 16

Команды (для сс=4):

1. Прибавить 2 2. Прибавить 3 3. Добавить справа 0

Ответ: 43

Динамическое программирование: ограничение на траекторию

(№ 2464) Исполнитель Калькулятор преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1 2. Прибавить 3

Программа для исполнителя Калькулятор – это последовательность команд.

Сколько существует программ, для которых при исходном числе 2 результатом является число 18, и при этом траектория вычислений содержит число 9 и не содержит число 14?

Способ 1, 2: Вручную таблицей, подобной таблицей в Excel

В D6: C8, в D8: =D6+D7

Способ 1:

«-» долго, легко ошибиться,

много писать, громоздко, много цифр, если опечатка, то легко ошибиться

«+» наглядно, легко проверить

Способ 2:

«-» также громоздко

«+» считается автоматически, наглядно

Ответ: 63

Способ 3: Программирование, массив

«-» необходимо хорошо разбираться в алгоритме, большая программа

«+» программа в сочетании с предыдущими способами исключают ошибку

Способы 1, 2, 3 отражают

одну и ту же технологию

решения

Ответ: 63

Способ 4: Дерево. От обратного

«-» если три команды или мало ограничений, то решение громоздкое

«+» меньше писать

Можно разбивать весь путь на отдельные участки

и перемножать их количество!!!

Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

• Прибавить 1
• Умножить на 2

Сколько существует программ, для которых при исходном числе 2 результатом является число 29 и при этом траектория вычислений содержит число 14 и не содержит числа 25?

Ответ: 13

«-» необходимо понимать алгоритм

«+» короткое решение

Ответ: 13

Способ 6: Средствами Excel

B4: =1

С4: =C2+C3

C3: = =ЕСЛИ(ОСТАТ(C1;2)=0;ПРОСМОТР(C1/2;$B$1:$N$1;$B$4:$N$4);0)

Добавление знака $ происходит автоматически после выделения диапазона и нажатия клавиши F4.

B9: =N4

P8: =ЕСЛИ(ОСТАТ(P6;2)=0;ПРОСМОТР(P6/2;$B$6:$Q$6;$B$9:$Q$9);0)

Ответ: 13

Динамическое программирование: ограничение на количество команд

(№ 3448) (С.С. Поляков) У исполнителя Калькулятор есть три команды, которым присвоены номера:

1. Прибавить 1 2. Прибавить 2 3. Умножить на 2

Сколько разных чисел на отрезке [34, 59] может быть получено из числа 1 с помощью программ, состоящих из 6 команд?

Способ 1: Таблица - граф

Способ 2: Программирование

• 's' - начало, 'x' - цель, 'l' - количество команд, 'count' - количество чисел

Python:

• def func(s,x,l): if x < s or l < 0: return 0 if x == s: return 1 K = func(s,x-1,l-1) K += func(s,x-2,l-1) if x % 2 == 0: K += func(s,x//2,l-1) return K count = 0 for i in range(34,60): if func(1,i,6) != 0: count += 1 print(count)

Спасибо за внимание!