Тема доклада «Методы решения заданий ЕГЭ по информатике»
Выполнил ученик 11 класса МБОУ СОШ с.Хондергей
Руководитель: Ховалыг Ш.Г., учитель информатики
Тема: «Методы решения задач ЕГЭ по информатике»
Проблема: Как успешно сдать ЕГЭ?
По окончанию школы каждый ученик должен сдать ЕГЭ. Немалые несдавшие ЕГЭ учащиеся не получают аттестаты. А для успешной сдачи ЕГЭ нужна тщательная подготовка. Поэтому вопрос «Как успешно сдать ЕГЭ?» остается актуальным для всех выпускников. Поэтому я выбрал тему «Методы решения задач ЕГЭ по информатике».
Цель: изучить методы решения заданий единого государственного экзамена по информатике
Собрать различные задания из тренировочных вариантов ЕГЭ;
Решить задачи ЕГЭ;
Выявить, сколькими разными способами можно решить данные задачи.
Если научиться решать задачи ЕГЭ по информатике с разными способами, то можно успешно сдать ЕГЭ по информатике.
Рассмотрим несколько заданий из ЕГЭ.
Сколько единиц в двоичной записи восьмеричного числа 345 8 ?
1 способ. Число из восьмеричной системы счисления перевести в десятичную. Из десятичной системы счисления перевести в двоичную.
345 8 = 3*8 2 + 4*8 1 + 5*8 0 = 192+32+5=229.
229 10 = 11100101 2 . Вычислить количество 1 в двоичной записи.
2 способ. Таблица соответствия.
3 способ. С помощью таблицы степени 2.
См. слайд 9. 1 1 1 0 0 1 0 1
Наибольшее число 128. Под таблицей отметим 1.
128 есть. Отметим 1.
64 есть – отметим 1.
32 есть – отметим 1.
4 есть. Отметим 1.
1 есть. Отметим 1.
В остальных случаях отметим 0.
Получилось двоичное число 11100101.
В двоичном числе количество единиц — 5. Ответ 5.
4 способ. С помощью позиции чисел.
Представим число с помощью степеней двойки
229 = 128+64+32+4+1 = 2 7 + 2 6 + 2 5 + 2 2 + 2 0 . Наибольший степень эта 7. Отметим позиции числе от 7 до 0.
Позиции: 7 6 5 4 3 2 1 0. Отмети если 2 7 есть, то под числом 7
1 1 1 0 0 1 0 1 отметим 1. Если 2 6 есть,то под числом
6 отметим 1. А если 2 3 нет среди
слагаемых, поставим 0 и т. д.
Получилось двоичное число 11100101. Количество единиц 5.
Правильность выполнения задания можно проверить с помощью калькулятора.
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, допускающий однозначное декодирование. Для букв А, Б, В и Г используются следующие кодовые слова: А — 10, Б — 00, В — 010, Г – 110. Укажите кратчайшее кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
1 способ: Посмотрим на таблицу. Нам понадобится восьмиричная СС. Между числами 010 и 110 лежит 3 числа. Среди них наименьшее 011.
2 способ графический. Построим дерево, у которого из корня и любой вершины выходят по две ветви. Сопоставим каждой левой ветки 0, а каждой правой 1.
Рассмотрим 3 случая:
Буква А встречается в слове ровно 1 раз.
Буква А встречается в слове ровно 2 раза.
Буква А встречается в слове не более двух раз.
1 случай. Саша составляет пятибуквенные слова, в которых есть только буквы А, Б, В, Г, Д, Е, причём в каждом слове буква А используется ровно 1 раз. Каждая из других допустимых букв может встречаться любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, необязательно осмысленная. Сколько существует таких слов, которые может написать Саша?
2 случай. Саша составляет четырехбуквенные слова, в которых есть только буквы Е, Д, А, Н и К, причём в каждом слове буква А используется ровно 2 раза. Каждая из других допустимых букв может встречаться любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, необязательно осмысленная. Сколько существует таких слов, которые может написать Саша?
3 случай . Саша составляет пятибуквенные слова, в которых есть только буквы А, Б, В, Г, причём в каждом слове буква А используется не более двух раз, и при этом может стоять только на первом или на последнем местах. Каждая из других допустимых букв может встречаться любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, необязательно осмысленная. Сколько существует таких слов, которые может написать Саша?
Запрос «или» вычисляется по этой формуле.
Ш|Т = Ш + Т – Ш&Т. Обозначили через Ш – количество страниц запроса «Шахматы».
Через Т – количество страниц запроса «Теннис».
Из этой формулы выразим количество страниц запроса «Шахматы».
Есть два способа решения задания:
1 способ – выписать все нужные программы, построить дерево программ .
2 способ – подсчитать число программ, не выписывая их явно, а написав формулу, которая позволяет найти количество программ получения данного числа, если уже известно количество программ для получения меньших чисел ( при таком решении удобно заполнять таблицу ).
Из числа 3 нужно получить 23.
Есть две команды.
Эти две команды записываем в обратными командами.
Х-1 (не прибавляем, а наоборот вычитаем 1)
х/2 (не умножаем, а делим на 2).
Получилось 2 новые команды.
Их записываем в таблицу.
На первом столбце таблицы записывали числа от 3 до 23. На 2 и 3 столбцах обратные команды. На последнем столбце количество программ.
1 строка. Проверяем первую команду. От трех вычитаем 1 получается 2. Число 2 не входит траекторию. Ничего не записываем. Проверяем вторую команду. 3 делим на 2. Единица получается, тоже не входит в траекторию. Ничего не записываем. Само число 3 это 1 программа.
2 строка. 4-1=3. Число 3 входит в траекторию. Поэтому 1 программа.
3 строка. 1 программа.
Таким образом, суммируются программы.
Научился решать задачи ЕГЭ.
Способы решения заданий ЕГЭ по информатике немного.
Информатика и ИКТ. Подготовка к ЕГЭ. Тренировочные варианты.
Интернет-ресурсы.
Видеоуроки.
«Яндекс» открыл доступ к нейросети «Балабоба» для всех пользователей
Как представляли себе будущее в далеком 1960-м году
Источник
Решение егэ по информатике способы решений
Длительность ЕГЭ по информатике составляет 3 часа 55 минут или 235 минут.
Задания выполняются с помощью компьютера. На протяжении всего экзамена будут доступны текстовый редактор, редактор электронных таблиц и системы программирования.
На ЕГЭ допустимо использование следующих языков программирования: С++, Java, C#, Pascal, Python, Школьный алгоритмический язык.
На экзамене будет разрешено использование программы Microsoft Windows «Калькулятор», а также графического редактора Microsoft Paint.
При проведении ЕГЭ по информатике выдача КИМ на бумажных носителях не планируется.
Кроме того, учащемуся будет предоставлен бумажный черновик для решения заданий «на бумаге». Но ответ необходимо внести в систему на компьютере.
Задания ЕГЭ по информатике делятся на два типа: с использованием заготовленных на компьютере файлов (для выполнения которых требуется использование специализированного программного обеспечения) и без использования таковых.
По уровню сложности: Базовый – 10 заданий (с № 1 по № 10), Повышенный – 13 (с № 11 по № 23), Высокий – 4 (с № 24 по № 27).
Максимальный первичный балл за работу – 30.
Общее время выполнения работы – 235 мин
Таблица перевода первичных баллов в тестовые баллы для проведения ЕГЭ:
Первич балл
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Тестов балл
8
15
22
29
37
43
46
48
50
53
55
57
60
62
65
67
69
71
Первич балл
19
20
21
22
23
24
25
26
27
28
29
30
Тестов балл
74
76
78
81
84
85
88
90
93
95
98
100
1 балл начисляется за выполнение заданий 1-24 2 балла начисляется за выполнение заданий 25-27
Источник
Разбор 23 задания ЕГЭ по информатике
23-е задание: «Динамическое программирование и анализ работы алгоритма» Уровень сложности — повышенный, Требуется использование специализированного программного обеспечения — нет, Максимальный балл — 1, Примерное время выполнения — 8 минут.
Проверяемые элементы содержания: Умение анализировать результат исполнения алгоритма
«Один из распространенных способов выполнения этого задания – выписать последовательность рекуррентных формул, определяющих, сколькими способами можно получить текущее число из ближайших предшественников, одновременно производя вычисления по этим формулам. «Ближайших» в данном случае означает тех, из которых текущее число получается в результате применения программы, состоящей из одной команды. Когда текущее число сравняется с заданным, количество таких способов и будет искомым числом программ»
Типичные ошибки и рекомендации по их предотвращению:
«Не стоит пытаться перечислить все пути в явном виде, это слишком трудоёмко и, скорее всего, в итоге приведёт к ошибке. Распространённая ошибка – экзаменуемые в процессе рекуррентных вычислений забывают о том, что траектория обязана содержать или не содержать указанные в условии числа»
Объяснение темы «Динамическое программирование»
Динамическое программирование – это способ или техника решения сложных задач путем приведения их к более простым подзадачам того же типа.
Динамическое программирование позволяет решать задачи, которые требуют полного перебора вариантов. Задание может звучать так:
«подсчитайте количество способов…»;
«как оптимально распределить…»;
«найдите оптимальный маршрут…».
Динамическое программирование позволяет увеличить скорость выполнения программы за счет эффективного использования памяти; полный перебор всех вариантов не требуется, поскольку запоминаются и используются решения всех подзадач с меньшими значениями параметров.
Более подробное знакомство с динамическим программированием доступно по ссылке.
Решение 23 заданий ЕГЭ по информатике
Плейлист видеоразборов задания на YouTube: Задание демонстрационного варианта 2022 года ФИПИ
Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
Сколько существует программ, для которых при исходном числе 3 результатом является число 37 и при этом траектория вычислений содержит число 18?
✍ Решение:
Результат: 28
Подробный разбор смотрите на видео:
Исполнитель Счетчик преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
Первая команда увеличивает число на экране на 5, вторая умножает его на 5. Программа для исполнителя Счетчик — это последовательность команд.
Сколько существует программ, для которых при исходном числе 5 результатом является число 250, и при этом траектория вычислений содержит число 35 и не содержит числа 105?
✍ Решение:
Так как общая траектория 5 -> 250 содержит в себе и те отрезки, которые должны быть удалены (содержащие 105), то разобьем ее на несколько отрезков, отображенных на луче:
5 -> 35 — обязательная часть, т.е. расчет количества программ по данной части траектории должен быть включен в результат;
35 -> 250 — отрезок, из которого нужно будет вычесть часть «ненужной» траектории («ненужная» траектория — которая включает число 105);
35 -> 105 — «ненужная» часть траектории;
105 -> 250 — тоже «ненужная» часть.
Чтобы вычислить результат, т.е. количество программ, необходимо:
Перед тем, как рассчитывать каждый отрезок, условимся брать только числа кратные 5, так как на траектории получения числа 250 из числа 5 командами умножить на 5 или прибавить 5 будут встречаться только числа кратные 5! (5+5=10, 5*5 = 25; 10+5 = 15, 10*5=50 и т.п.).
Кроме того, будем использовать метод решения с конца, т.е. двигаясь от наибольших подходящих чисел к наименьшим.
Расчет отрезка 1: 5 -> 35
Возьмем такое наименьшее число, кратное 5 и, находящееся в интервале от 5 до 35, для которого применима только одна команда:
Отобразим число 10 на графе, указав и саму команду и результат. Красным цветом обозначим количество команд для получения конкретного числа, а в круг будем обводить итоговое суммарное количество команд. То есть из 10 мы можем получить число 15, используя одну команду (10 + 5 = 15):
Далее рассмотрим следующее, меньшее десяти число: это 5. Для него можно использовать 2 команды (5+5=10 и 5*5=25):
Итого получили две программы.
Результат: 2
Расчет отрезка 2: 35 -> 250
Возьмем такое наименьшее число, кратное 5, и, находящееся в интервале от 35 до 250, для которого применима только одна команда:
Затем будем последовательно брать подходящие меньшие числа
Пояснение: поскольку это задача динамического программирования, то полученные в начале результаты, используются для дальнейших вычислений:
для числа 45 мы взяли результат, полученный для числа 50 (2);
для числа 40 мы взяли результат, полученный для числа 45 (3);
для числа 35 мы взяли результат, полученный для числа 40 (4);
Результат: 5
Расчет отрезка 3: 35 -> 105
Возьмем такое наименьшее число кратное 5 и находящееся в интервале от 35 до 105, для которого применима только одна команда:
Результат: 1
Расчет траектории 4: 105 -> 250
Результат: 1
Посчитаем результат, согласно полученной формуле:
Результат: 8
У исполнителя Увеличитель две команды, которым присвоены номера:
Первая из них увеличивает число на экране на 1, вторая умножает его на 4.
Программа для Увеличителя – это последовательность команд.
Сколько есть программ, которые число 3 преобразуют в число 44?
✍ Решение:
Возьмем такое наименьшее число, находящееся в интервале от 3 до 44, для которого применима только одна команда:
Отобразим число 12 на графе, указав и саму команду и результат. То есть для 12 можно использовать только одну команду (12 + 1 = 13):
Пояснение: Красным цветом будем выделять количество команд для получения конкретного числа, а в круг обводить итоговое суммарное количество команд.
Дальше будем использовать метод решения с конца, т.е. двигаясь от наибольших подходящих чисел (в конкретном случае с 12) — к наименьшим.
Пояснение: поскольку это задача динамического программирования, то полученные промежуточные результаты, используются для дальнейших вычислений:
для 11 взят результат, полученный для 12 (1);
для 10 взят результат, полученный для числа 11 (2);
для 9 взят результат, полученный для 10 (3);
и т.д.
Для последнего числа 3 получено 10 команд.
Результат: 10
Предлагаем посмотреть видео с решением данного 23 задания:
Исполнитель М17 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера: 1. Прибавить 1 2. Прибавить 2 3. Умножить на 3
Первая из них увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает на 3. Программа для исполнителя М17 – это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное число 2 в число 12 и при этом траектория вычислений программы содержит числа 8 и 10? Траектория должна содержать оба указанных числа.
✍ Решение:
Изобразим траекторию в виде луча, на котором отложим отрезки:
Поскольку 8 и 10 обязательно должны содержаться в расчете, то для поиска общего количества программ необходимо найти произведение количества программ отдельных отрезков:
Найдем отдельно количество программ каждого из отрезков:
2 -> 8 = 15
На интервале от 2 до 8 возьмем число, для которого исполнима только одна из команд:
Рассмотрим все числа интервала, двигаясь от большего к меньшему:
8 -> 10 = 2
очевидно, что это две программы:
10 -> 12 = 2
Выполним произведение полученных результатов:
Результат: 60
Подробное решение 23 (22) задания демоверсии ЕГЭ 2018 доступно на видео:
